ALG"5

9.1. Programowanie typu „dziel-i-rządź’' 225

zastosowaniem omawianej metody warto wziąć do ręki kartkę i ołówek, aby przekonać się, czy w ogóle warto zasiadać do klawiatury!

Oto formalny zapis metody zaprezentowany przy pomocy pseudo-języka programowania:

dziel_i_rządż(N)

(

jeśli N wystarczająco mały zwróć Przypadek_Elementarny(N); w przeciwnym wypadku <

„Podziel" Pb(N) i:a mniejsze egzemplarze:

Pb (N,), Pb (Ni)... Pb (N_k) ; dla i-1... k

oblicz wynik cząstkowy w₁=dziel_i_rzadź(N_L);

zwróć KOMBfwi, w_z, • • . w*) ;

ł

)

Określenie właściwego znaczenia sformułowań „wystarczająco mały” „przypadek elementarny” będzie ściśle związane z rozważanym problemem i trudno tu podać dalej posuniętą generałizację. Ewentualne niejasności powinny się wyjaśnić podczas analizy przykładów znajdujących się w następnych paragrafach.

9.1.1 .Odszukiwanie minimum i maksimum w tablicy liczb

Z metodą „dziel-i-rządź” mieliśmy już w tej książce do czynienia w sposób niejawny i odnalezienie algorytmów, które mogą się do niej zakwalifikować, zostaje pozostawione Czytelnikowi jako test na „spostrzegawczość i orientację” (kilka odnośników zostanie jednak pod koniec podanych).

Jako pierwszy' przykład przestudiujemy dość prosty problem odnajdywania elementów: największego i najmniejszego w tablicy. Problem raczej banalny, ale o pewnym znaczeniu praktycznym. Przykładowo wyobraźmy sobie, że chcemy wykreślić na ekranie przebieg funkcji y=J(xJ. W tym celu w pewnej tablicy zapamiętujemy obliczane N wartości tej funkcji dla przedziału, powiedzmy, \j... Xp Mając zestaw punktów musimy przeprowadzić jego „rzut” na ekran komputera, tak aby zmieścić na nim tyle punktów, by otrzymany wykres nie przesunął się w niewidoczne na ekranie obszary. Z osią OX nie ma problemów: możemy się umówić, że x_d odpowiada współrzędnej 0, a x_e - odpowiednio maksymalnej rozdzielczości poziomej. Aby jednak przeprowadzić skalowanie na osi OY konieczna jest znajomość ekstremalnych wartości funkcji f(x). Dopiero wówczas możemy być pewni, że wykres istotnie zmieści się w strefie widocznej ekranu!