pascal ROZDZ 10.doc

10.  PODSTAWOWE ALGORYTMY

10.1. Algorytm znajdowania największego wspólnego dzielnika (NWD)

Zadanie to ma wiele rozwiązań.

1. Pierwsze, nazwiemy je siłowym, jest skuteczne ale bardzo czasochłonne i nieoptymalne.

Polega ono na kolejnych działaniach:

Począwszy od mniejszej liczby, a skończywszy na znalezionym rozwiązaniu sprawdzamy, czy liczba dzieli A i B bez reszty. Jeżeli tak - to mamy wynik, a jeżeli nie - pomniejszamy liczbę o 1 i sprawdzamy dalej. Innymi słowy, sprawdzamy podzielność liczb A i B (załóżmy że B jest mniejsze) przez B, potem przez B-1, B-2 i tak do skutku ... Algorytm na pewno da pozytywny wynik (w najgorszym przypadku zatrzyma się na liczbie 1, która na pewno jest podzielnikiem liczb A i B). W najgorszym przypadku będzie musiał wykonać 2B dzieleń i B odejmowań.

To zadanie da się i należy rozwiązać lepiej.

2. Algorytm Euklidesa

Polega na przetwarzaniu cyklu następujących operacji:

·         podziel większą z liczb przez mniejszą (z resztą)

·         do dalszej działalności wybierz dzielnik i znalezioną resztę

·         operacja jest powtarzana tak długo, aż resztą będzie 0.

·         Szukanym największym wspólnym dzielnikiem liczb A i B jest dzielnik z ostatniej operacji dzielenia.

Oto przykład (szukamy największego podzielnika liczb 12 i 32):

·         32/12 = 2 reszty 8

·         12/8 = 1 reszty 4

·         8/4 = 2 reszty 0

Szukanym największym wspólnym dzielnikiem, liczb 12 i 32 jest 4. Jak widać zamiast sprawdzania 9 liczb (12, 11, 10, 9, 8, 7, 6, 5, 4), z wykonaniem dwóch dzieleń dla każdej z nich, jak miałoby to miejsce w przypadku rozwiązania siłowego wystarczyły nam tylko trzy dzielenia.

3. Modyfikacja algorytmu Euklidesa

Algorytm ten nie wymaga ani jednego dzielenia. Jeżeli liczby są różne szukamy ich różnicy (od większej odejmując mniejszą). Odrzucamy większą z liczb i czynimy to samo dla mniejszej
z nich i wyniku odejmowania. Na końcu, kiedy liczby będą sobie równe, będą jednocześnie wynikiem naszych poszukiwań. Na przykład z liczbami 32 i 12 będzie się przedstawiał następująco:

·         32-12 = 20

·         20-12 = 8

·         12 - 8 =4

·         8 - 4 =4

·         4=4

Znowu znaleziono poprawny wynik czyli 4. Operacji jest co prawda więcej, ale warto zwrócić uwagę że są to jedynie odejmowania, a nie dzielenia. Koszt operacji dodawania i odejmowania jest znacznie mniejszy, niż dzielenia i mnożenia (pisząc "koszt" mamy na myśli czas pracy procesora, niezbędny do wykonania działania).

10.2.  Algorytm znajdowania najmniejszej wspólnej wielokrotności (NWW) liczb naturalnych A i B.

Jak widać do rozwiązania tego problemu wykorzystujemy poprzedni algorytm (algorytm Euklidesa).

10.3.  Algorytm obliczania potęgi

Rozwiązanie to otrzymamy korzystając ze wzoru matematycznego:

Obie funkcje oraz są w Pascalu dostępne.

10.4.  Algorytm obliczania silni

Silnia liczby jest iloczynem wszystkich liczb naturalnych mniejszych od niej lub jej równych, tzn.:

                            gdzie

przykład:

10.4.1.  Algorytm iteracyjny

Polega on na wykonaniu następujących kroków:

·         wczytaj n

·         silnia:=1, i:=0

·         jeżeli i≥n , wypisz wynik (silnia)

·         w przeciwnym wypadku i:=i+1, silnia:=silnia*i

Schemat blokowy tego algorytmu ma postać:

START

Czytaj n

silnia:=1
i:=0

i:=i+1
silnia:=silnia*i

i≥n ?

              N

T

STOP

wypisz silnia

10.4.2.  Algorytm rekurencyjny

Przykład:

Przy obliczaniu 4! tą metodą otrzymamy ciąg obliczeń:

4! = 4*3!

4! = 4*(3*2!)

4! = 4*(3*(2*1!))

4! = 4*(3*(2*(1*0!)))

4! = 4*(3*(2*(1*1)))

4! = 4*(3*(2*1))

4! = 4*(3*2)

4! = 4*6

4! = 24

Schemat blokowy tego algorytmu ma postać:

START

STOP

wypisz silnia

silnia:=1

Czytaj n

policz:=silnia
silnia:=n*policz

n=0 ?

              N                                         

              T                 

Jak widać metoda ta polega na definiowaniu funkcji za pomocą niej samej. Nosi ona nazwę rekurencji.

10.5.  Algorytm określania czy n jest liczbą pierwszą

1.      Pierwsze rozwiązanie (liniowe):

·         dla każdej liczby od 2 do n-1, sprawdzamy czy nie dzieli n

·         jeżeli liczba n nie była podzielna przez 2, to eliminujemy liczby parzyste, bo i tak nie jest przez nie podzielna

·         jeżeli któraś z liczb dzieli n, wtedy n nie jest liczbą pierwszą

2.      Rozwiązanie wykładnicze

·         dla każdej liczby od 2 do , sprawdzamy czy nie dzieli n (jeżeli liczba n nie ma podzielników do liczby , to poza nią też ich na pewno nie ma)

·         jeżeli liczba n nie była podzielna przez 2, to eliminujemy liczby parzyste, bo i tak nie jest przez nie podzielna

·         jeżeli któraś z liczb dzieli n, wtedy n nie jest liczbą pierwszą

10.6.  Funkcję rekurencyjną (rekursję) nazywamy taką funkcję która wywołuje samą siebie. Funkcja taka musi posiadać warunek zakończenia rekurencji. Jeżeli takiego warunku by nie posiadała funkcja wywoływała by siebie bez końca. Jej dziedziną, mogą być tylko liczby naturalne. Funkcja taka jest wykonywana trochę wolniej niż funkcja nierekurencyjna, ale kod jest zdecydowanie krótszy i prostszy w niektórych wypadkach. Podprogramy rekurencyjne pozwalają na zgrabny i przejrzysty zapis algorytmu takich problemów, w których wynik końcowy jest złożeniem wielu wyników cząstkowych. Najlepszym przykładem na funkcję rekurencyjną jest silnia.

n! zapisuje się w następujący sposób: n!=n*(n-1)! Ze wzoru tego wynika, że aby obliczyć np. 4!, należy najpierw obliczyć 3!. Ale żeby obliczyć 3! trzeba obliczyć 2! itd. aż dojdziemy do 0!, które jak wiemy wynosi 1. Sposób obliczenia 4! wygląda więc następująco:

4!=4*3!=4*3*2!=4*3*2*1!=4*3*2*1*0!=4*3*2*1*1=24

Inaczej pokazując ten problem możemy zilustrować wywołanie rekurencyjne funkcji silnia(n):

Np. wywołujemy funkcję silnia(4):

                        Silnia(4)

4*

Silnia(3)

3*

Silnia(2)

2*

Silnia(1)

1...