Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2010 mgr
Jerzy Wałaszek |
Problem jest następujący. W zbiorze n elementowym należy wyszukać największą wartość elementu. Zadanie rozwiązujemy następująco:
Za chwilowo największy element przyjmujemy pierwszy element zbioru. Następnie kolejno przeglądamy elementy zbioru poczynając od drugiego do ostatniego. Jeśli któryś z przeglądanych elementów jest większy od elementu chwilowo największego, to za nowy chwilowy element największy przyjmujemy ten element zbioru. Gdy przeglądniemy wszystkie elementy element chwilowo największy będzie zawierał największą wartość znalezioną w zbiorze.
Dane wejściowe:
n - liczba elementów
T[] - tablica n elementowa zawierająca przeszukiwane elementy. Elementy
są numerowane od 0 do n-1.
Dane wyjściowe:
vmax - największa wartość w zbiorze
Dane pomocnicze:
i - indeksy elementów T[]
Lista kroków:
Krok 1: vmax ← T[0]
Krok 2: Dla i = 1,2,...,n-1 wykonuj krok 3
Krok 3: Jeśli
T[i] > vmax,
to vmax ← T[i]
Krok 4: Zakończ
Przykładowe dane dla programu:
Pierwsza liczba n określa ilość elementów w zbiorze. Następne n liczb definiuje n kolejnych elementów. Liczby zbioru są rzeczywiste.
100
309.58 122.55 -378.83 222.614 100.78 281.21 479.2 -67.17 -190.11 -355.854
-452.88 -14.33 -290.82 -382.94 491.62 -114.23 43.68 -165.22 -57.14 451.944
-81.21 429.24 -104.91 147.35 64.24 -420.34 -403.92 -335.13 -307.073 57.658
63.37 -165.96 -322.86 418.46 -63.72 245.47 69.957 435.526 489.225 41.146
311.06 -361.61 369.82 496.097 333.34 248.82 -197.91 -452.55 34.52 370.28
59.767 -50.481 265.92 -35.345 14.21 -161.67 -498.86 -386.22 -124.5 -222.74
319.1 -307.25 -68.49 -489.31 195.34 171.28 -361.22 -493.12 171.47 -409.77
398.42 58.692 378.22 -95.74 297.55 -204.4 362.496 111.386 -220.78 45.943
-199.874 -20.92 410.52 387.28 -221.11 179.67 -327.87 -178.77 176.25 -31.21
-75.48 278.5 -335.4 439.25 -382.8 303.405 207.925 -60.527 -481.694 -29.104
Program znajdowania największej wartości w zbiorze n elementowym
// Wyszukiwanie max // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> using namespace std; int main() { double * T,vmax; int i,n; // odczytujemy liczbę elementów cin >> n; // tworzymy tablicę dynamiczną o n elementach T = new double[n]; // wczytujemy elementy do tablicy for(i = 0; i < n; i++) cin >> T[i]; // szukamy max vmax = T[0]; for(i = 1; i < n; i++) if(T[i] > vmax) vmax = T[i]; // wyświetlamy wynik cout << endl << vmax << endl; // usuwamy tablicę dynamiczną delete [] T; return 0; } |
// Wyszukiwanie min // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> using namespace std; int main() { double * T,vmin; int i,n; // odczytujemy liczbę elementów cin >> n; // tworzymy tablicę dynamiczną o n elementach T = new double[n]; // wczytujemy elementy do tablicy for(i = 0; i < n; i++) cin >> T[i]; // szukamy min vmin = T[0]; for(i = 1; i < n; i++) if(T[i] < vmin) vmin = T[i]; // wyświetlamy wynik cout << endl << vmin << endl; // usuwamy tablicę dynamiczną delete [] T; return 0; } |
Jednoczesne wyszukiwanie wartości najmniejszej i największej w zbiorze wymaga w powyższym algorytmie wykonania 2n-2 porównań - pętla szukająca wykonuje n-1 obiegów, a w każdym obiegu wykonujemy dwa porównania - jedno dla vmin a drugie dla vmax.
// Wyszukiwanie min i max // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> using namespace std; int main() { double * T,vmin,vmax; int i,n; // odczytujemy liczbę elementów cin >> n; // tworzymy tablicę dynamiczną o n elementach T = new double[n]; // wczytujemy elementy do tablicy for(i = 0; i < n; i++) cin >> T[i]; // szukamy max vmin = vmax = T[0]; for(i = 1; i < n; i++) { if(T[i] < vmin) vmin = T[i]; if(T[i] > vmax) vmax = T[i]; } // wyświetlamy wynik cout << endl << vmin << endl << vmax << endl; // usuwamy tablicę dynamiczną delete [] T; return 0; } |
Okazuje się, iż stosując zasadę dziel i zwyciężaj (ang. divide and conquer) możemy zmniejszyć liczbę porównań, jeśli interesuje nas jednoczesne znalezienie wartości min i max w zbiorze. Zasada jest następujące:
Zbiór dzielimy na dwa równe zbiory, elementów mniejszych i większych. Podziału dokonujemy biorąc ze zbioru po dwa elementy i porównując je ze sobą. Element mniejszy zaliczymy do zbioru elementów mniejszych, a element większy zaliczymy do zbioru elementów większych. Operacja ta wymaga, aby zbiór posiadał parzystą liczbę elementów (jeśli ma nieparzystą liczbę elementów, to ostatni element dublujemy). Ponieważ bierzemy po dwa elementy, wykonamy n/2 porównań. Teraz w zbiorze elementów mniejszych szukamy min. Operacja ta wymaga n/2 - 1 porównań, ponieważ elementy te tworzą tylko połowę elementów wejściowego zbioru. Podobnie w zbiorze elementów większych szukamy max. Ta operacja również wymaga n/2 - 1 porównań. W efekcie otrzymujemy:
n/2 + n/2 - 1 + n/2 - 1 = 3/2n - 2 porównań, co jest mniejsze od 2n-2!
Dane wejściowe:
n - liczba elementów, musi być parzysta.
T[] - tablica n elementowa zawierająca przeszukiwane elementy. Elementy
są numerowane od 0 do n-1.
Dane wyjściowe:
vmin - najmniejsza wartość w zbiorze
vmax - największa wartość w zbiorze
Dane pomocnicze:
i - indeksy elementów T[]
Lista kroków:
Krok 1: | Jeśli T[0] > T[1], to idź do kroku 5 |
Krok 2: | vmin ← T[0] |
Krok 3: | vmax ← T[1] |
Krok 4: | Idź do kroku 7 |
Krok 5: | vmin ← T[1] |
Krok 6: | vmax ← T[0] |
Krok 7: | Dla i = 2,4,...,n-2: wykonuj kroki 8...14 |
Krok 8: | Jeśli T[i] > T[i+1], to idź do kroku 12 |
Krok 9: | Jeśli T[i] < vmin, to vmin ← T[i] |
Krok 10: | Jeśli T[i+1] > vmax, to vmax ← T[i+1] |
Krok 11: | Wykonaj następny obieg pętli |
Krok 12: | Jeśli T[i] > vmax, to vmax ← T[i] |
Krok 13: | Jeśli T[i+1] < vmin, to vmin ← T[i+1] |
Krok 14: | Wykonaj następny obieg pętli |
Krok 15: | Zakończ |
Program jednoczesnego znajdowania min i max w zbiorze n elementowym
// Wyszukiwanie min i max // (C)2010 I LO w Tarnowie //------------------------ #include <iostream> using namespace std; int main() { double * T,vmin,vmax; int i,n; // odczytujemy liczbę elementów cin >> n; // tworzymy tablicę dynamiczną o n + 1 elementach T = new double[n+1]; // wczytujemy elementy do tablicy for(i = 0; i < n; i++) cin >> T[i]; // dublujemy ostatni element, gdyby n było nieparzyste T[n] = T[n-1]; // bierzemy dwa pierwsze elementy, mniejszy do vmin, a większy do vmax if(T[0] > T[1]) { vmin = T[1]; vmax = T[0]; } else { vmin = T[0]; vmax = T[1]; } // szukamu min i max wśród pozostałych elementów for(i = 2; i < n; i += 2) if(T[i] > T[i+1]) { if(T[i] > vmax) vmax = T[i]; if(T[i+1] < vmin) vmin = T[i+1]; } else { if(T[i+1] > vmax) vmax = T[i+1]; if(T[i] < vmin) vmin = T[i]; } // wyświetlamy wynik cout << endl << vmin << endl << vmax << endl; // usuwamy tablicę dynamiczną delete [] T; return 0; } |
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe