Algorytmika - Znajdowanie najmniejszej liczby
Algorytmika - Znajdowanie najmniejszej liczby
Utwórz algorytm znajdowania najmniejszej liczby ze zbioru 10 dowolnych liczb.
-
Pawelek91
- Użytkownik
- Posty: 56
- Rejestracja: 23 lis 2008, o 14:54
- Płeć: Mężczyzna
- Lokalizacja: Wyszogród
- Podziękował: 1 raz
- Pomógł: 4 razy
Algorytmika - Znajdowanie najmniejszej liczby
1. wprowadz liczby
2. \(\displaystyle{ min}\)=pierwsza liczba
3. od\(\displaystyle{ i=2}\) do \(\displaystyle{ 10}\) wykonuj
4. jesli \(\displaystyle{ i}\)-ta liczba < \(\displaystyle{ min}\) to \(\displaystyle{ min}\) = \(\displaystyle{ i}\)-ta liczba
5.wypisz \(\displaystyle{ minimum}\)
6.konic
7. dziekuje
2. \(\displaystyle{ min}\)=pierwsza liczba
3. od\(\displaystyle{ i=2}\) do \(\displaystyle{ 10}\) wykonuj
4. jesli \(\displaystyle{ i}\)-ta liczba < \(\displaystyle{ min}\) to \(\displaystyle{ min}\) = \(\displaystyle{ i}\)-ta liczba
5.wypisz \(\displaystyle{ minimum}\)
6.konic
7. dziekuje
Algorytmika - Znajdowanie najmniejszej liczby
Ewentualnie, możesz to zrealizować za pomocą kopca typu min.
Wówczas sytuacja wygląda tak, że na szczycie tego kopca masz zawsze element minimalny spośród wszystkich dostępnych. Zatem czas pobrania tego elementu jest stały , bo po prostu pobierasz element z wierzchołka kopca.
To jest sposób dużo szybszy i bardziej opłacalny dla dużej ilości danych w porównaniu z przeglądaniem za każdym razem całej listy elementów (jednak troszkę trudniejszy w implementacji).
AVE!
Wówczas sytuacja wygląda tak, że na szczycie tego kopca masz zawsze element minimalny spośród wszystkich dostępnych. Zatem czas pobrania tego elementu jest stały , bo po prostu pobierasz element z wierzchołka kopca.
To jest sposób dużo szybszy i bardziej opłacalny dla dużej ilości danych w porównaniu z przeglądaniem za każdym razem całej listy elementów (jednak troszkę trudniejszy w implementacji).
AVE!
-
Althorion
- Użytkownik
- Posty: 4541
- Rejestracja: 5 kwie 2009, o 18:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 9 razy
- Pomógł: 662 razy
Algorytmika - Znajdowanie najmniejszej liczby
Dla dziesięciu liczb? I tylko jednego zapytania?
a) algorytm naiwny:
dokonuje dziewięciu porównań, pierwszej z drugą, trzeciej z minimum itd. aż do dziesiątej z minimum
b) kopcowanie:
Utworzenie kopca zajmuje już więcej porównań - najpierw sufit z \(\displaystyle{ \log_2 10}\) czyli pięć na pierwszy rząd (pierwszą z drugą, trzecią z czwartą itd.). Potem sufit z \(\displaystyle{ \log_2 5}\) - czyli trzy, dalej dwa i jedno, łącznie 11 porównań.
Zgodziłbym się, gdyby chciano od nas uporządkowania tego zbioru. Ale nie w tym zadaniu. Pierwszy algorytm ma złożoność typu \(\displaystyle{ O(n)}\), drugi - \(\displaystyle{ O(n\log n)}\).
a) algorytm naiwny:
dokonuje dziewięciu porównań, pierwszej z drugą, trzeciej z minimum itd. aż do dziesiątej z minimum
b) kopcowanie:
Utworzenie kopca zajmuje już więcej porównań - najpierw sufit z \(\displaystyle{ \log_2 10}\) czyli pięć na pierwszy rząd (pierwszą z drugą, trzecią z czwartą itd.). Potem sufit z \(\displaystyle{ \log_2 5}\) - czyli trzy, dalej dwa i jedno, łącznie 11 porównań.
Zgodziłbym się, gdyby chciano od nas uporządkowania tego zbioru. Ale nie w tym zadaniu. Pierwszy algorytm ma złożoność typu \(\displaystyle{ O(n)}\), drugi - \(\displaystyle{ O(n\log n)}\).