Przykłady realizacja algorytmów w języku Pascal. ................................................................................................ 2
Algorytmy liniowe .............................................................................................................................................. 2
Algorytmy rozgałęzione:..................................................................................................................................... 3
Algorytmy iteracyjne: ......................................................................................................................................... 4
Algorytmy iteracyjne z określoną liczbą powtórzeń. .......................................................................................... 4
Algorytm wyszukujący najmniejszą z N liczb z tablicy T[1..N]..................................................................... 4
Algorytm obliczania wartości wielomianu za pomocą schematu Hornera...................................................... 5
Algorytmy iteracyjne w których liczba powtórzeń nie jest z góry określona ................................................. 7
Algorytm Euklidesa obliczania NWD............................................................................................................. 7
Jednoczesne wyszukiwanie min i max z tablicy T[1..N] metodą dziel i zwyciężaj ........................................ 9
Generowanie liczb Fibonacciego .................................................................................................................. 10
Sortowanie ............................................................................................................................................................ 11
Sortowanie przez wybór.................................................................................................................................... 11
Sortowanie bąbelkowe ...................................................................................................................................... 13
Algorytmy rekurencyjne. ...................................................................................................................................... 14
Definicje rekurencyjne ...................................................................................................................................... 14
Przykład rekurencyjnej definicji rysowania płotka: ...................................................................................... 14
Przykład rekurencyjnejdefinicji obliczania sumy z kolejnych liczb naturalnych od i do J ........................... 15
Realizacja algorytmów rekurencyjnych w postaci procedur i funkcji rekurencyjnych ..................................... 16
Procedura rysująca płotek wg. definicji z wcześniejszych przykładów: ....................................................... 16
Funkcja obliczająca sumę kolejnych liczb naturalnych z zakresu i..j wg. definicji z wcześniejszych
przykładów .................................................................................................................................................... 16
Definicja rekurencyjna n! i odpowiadająca jej funkcja ................................................................................. 16
Definicja rekurencyjna schematu Hornera i odpowiadająca jej funkcja ....................................................... 17
Przykłady realizacja algorytmów w języku Pascal.
Algorytmy liniowe
Algorytm obliczania pola trójkąta za pomocą wzoru Herona.
Dane wejściowe: długości boków trójkąta a, b, c
Dane wyjściowe (wyniki): pole trójkąta p
program Heron;
zmienne a,b,c, p, pole :rzeczywiste;
zacznij
czytaj(a, b, c);
p := (a+b+c)/2
pole := sqrt(p*(p-a)*(p-b)*(p-c))
drukuj pole;
zakończ.
realizacja algorytmu w postaci programu
program Heron;
var
a,b,c, p, pole: real;
begin
Writeln('Program oblicza pole trójkąta o podanych długościach boków
a, b, c');
writeln('podaj długości boków a, b, c');
readln(a, b, c);
p := (a+b+c)/2;
pole := sqrt(p*(p-a)*(p-b)*(p-c))
writeln('pole = ', pole:4:2);
end.
zadanie: wykonaj schemat blokowy tego algorytmu. Zapisz w postaci schematu blokowego, i programu algorytm
obliczający średnią Avg i sumę Sum z trzech wczytanych liczb a, b, c
Algorytmy rozgałęzione:
Algorytm wyszukujący minimum z trzech liczb a, b, c
Specyfikacja:
Dane wejściowe: liczby a, b, c
Dane wyjściowe: (wynik): najmniejsza z liczb a, b, c
program minabc;
zmienne a, b, c: liczby rzeczywiste;
rozpocznij
czytaj(a, b, c;)
jeśli (a < b) i (a min := a
w przeciwnym razie
jeśli b min := b
w przeciwnym razie
min := c
zakończ.
Realizacja algorytmu w postaci programu
program MinABC;
var
a,b,c, min: integer;
begin
writeln('Program znajduje min z trzech liczb a,b,c');
write('Podaj wartości liczb a, b, c: ');
readln(a, b, c);
if (a < b) and (a < c) then
min := a
else
if b < c then
min := b
else
min := c;
write('min = ', min);
end.
Zadanie: Narysuj schemat blokowy algorytmu minabc. Uzupełnij algorytm Herona o kontrolę wprowadzonych
danych: jeżeli nie są poprawne niech wyświetli komunikat "z odcinków a, b, c nie można zbudować trójkąta"
Napisz program obliczający wartość x spełniającego równanie kwadratowe ax2+bx+x=0 przy danych a, b, c. Do
obliczenia delty i pierwiastków x1 i x2 utwórz odpowiednie funkcje.
Algorytmy iteracyjne:
Algorytmy iteracyjne z określoną liczbą powtórzeń.
Algorytm wyszukujący najmniejszą z N liczb z tablicy T[1..N]
dane wejściowe: N - liczba elementów tablicy T, T[1..N] - N- elementowa tablica liczb całkowitych
dane wyjściowe: min wartość najmniejszego elementu z tablicy T
program minT;
stałe: N;
zmienne: min, i N: liczby całkowite;
T[1..N] tablica liczb całkowitych;
zacznij
czytajtablicęT;
min := T[1];
dla i := 2 do N wykonuj
jeśli T[i]zakończ.
Realizacja algorytmu w postaci programu.
Program MinT;
const
n = 5;
var
min, i: integer;
T: array[1..n] of integer;
procedure czytajT;
begin
writeln('podawaj wartości elementów tablicy');
for i := 1 to n do
begin
write('T[', i, ']');
readln(T[i]);
end;
end;
begin
..writeln('program szuka min z tablicy T[', n, ']');
min:= T[1];
for i := 2 to n do
if T[i] < min then min := T[i]
writeln('min = ', min);
end.
Zadanie: napisz algorytm obliczający w = xn dla danych wejściowych x i n, napisz algorytm obliczający w = n!
dla danej wejściowej n. Napisz algorytm iteracyjny obliczający w=xn dla danych wejściowych x i n.
Algorytm obliczania wartości wielomianu za pomocą schematu Hornera
wielomianem nazywamy wyrażenie postaci:
anxn + an-1xn-1 + an-2xn-2... + a2x2 + a1x +a0
wez
my wielomian:
a4x4 + a3x3 + a2x2 + a1x +a0
Wyłączając x przed nawias możemy go sprowadzić do postaci
x(a4x3 + a3x2 + a2x + a1) +a0
postępując podobnie możemy przekształcać wielomian nadal do kolejnych postaci
x(x(a4x2 + a3x + a2) + a1) +a0
x(x(a4x2 + a3x + a2) + a1) +a0
x(x(x(a4x + a3) + a2) + a1) +a0
x(x(x(x(a4) + a3) + a2) + a1) +a0
aby obliczyć wartość W wielomianu j.w. korzystając z tej postaci możemy postępować jak niżej obliczając
kolejne wartości od najbardziej wewnętrznych nawiasów i korzystając z nich w następnych obliczeniach.
W := a4
W := x*W+a3
W := x*W+a2
W := x*W+a1
W: = x*W+a0
W ogólnym przypadku możemy zapisać wielomian w postaci:
x(...x((x(an)+an-1)+an-2) ...)+a1)+a0
i obliczyć jego wartość jak niżej:
W := an
W := x*W+an-1
W := x*W+an-2
.
.
.
W := x*W+a0
specyfikacja algorytmu:
dane wejściowe: stopień wielomianu  n, wartości współczynników ai wielomianu anxn+an-1xn-1+...+a1x+a0,
wartość x
dane wyjściowe: w  wartość wielomianu jak wyżej.
algorym:
program Horner;
stałe
n = 5;
zmienne
a: tablica [1..n] liczb całkowitych;
rozpocznij
w := a[n]
Dla i := n zmniejszając do 0 wykonuj W := x*W+a[i]
zakończ.
Realizacja algorytmu w postaci programu.
program Horner;
const
nmax = 5;
var
x, i, n: integer;
a: array[1..nmax] of integer;
procedure czytaja;
begin
for i := 0 to n do
begin
write('a[', i, '] = ');
readln(a[i]);
end;
end;
begin
writeln('program oblicza wartość wielomianu')
write('podaj nie większy od ', n, 'stopień wielomianu n: ');
readln(n);
czytaja;
w := a[n];
writeln('podaj wartość x :');
readln(x);
for i := n to 0 downto w := x*w + a[i];
write('wartość wielomianu wynosi: ', w);
end.
 Algorytmy iteracyjne w których liczba powtórzeń nie jest z góry
określona
Algorytm Euklidesa obliczania NWD
przykład obliczania NWD wg schematu Euklidesa dla liczb większej W i mniejszej M
W schemacie Euklidesa korzystamy ze szczególnej własności liczb mających wspólny dzielnik: jeżeli liczby
mają wspólny dzielnik podzielna przez ten dzielnik jest liczba mniejsza, większa i reszta z dzielenia liczby
większej przez mniejszą (zastanów się dlaczego).
Schemat ten można opisać za pomocą listy kroków jak niżej:
1. Podziel liczbę większą W przez mniejszą M, oblicz resztę z dzielenia
R
2. jeżeli R > 0 to
większa z liczb M i R staje się liczbą większą W;
mniejsza z liczb M i R staje się liczbą M
3. jeżeli R <> 0 wróć do kroku 1.
4. NWD staje się równe M
5. zakończ
przykłady:
81 : 12 = 6 r 9
12 : 9 = 9 r 3
9 : 3 = 3 r 0
NWD = 3
54 : 16 = 3 r 6
16 : 6 = 2 r 4
6 : 4 = 1 r 2
4 : 2 = 2 r 0
NWD = 2
Specyfikacja algorytmu:
Dane wejściowe: A, B  liczby całkowite
Dane wyjściowe: NWD  największy wspólny dzielnik A i B
algorytm w pseudokodzie
program szukanieNWD;
Zmienne A, B, W, M, R: całkowite;
rozpocznij
R:= 0;
czytaj(A, B)
jeżeli A > B to
rozpocznij W := A; M := B zakończ
w przeciwnym razie
rozpocznij W := B; M := A zakończ;
powtarzaj
R := A  (B*(A div B));
jeżeli R > 0 to
jeżeli B > R to
rozpocznij W := B; M := R; zakończ;
dopóki nie R = 0
NWD = M
zakończ.
realizacja algorytmu w Pascal'u
program szukanieNWD;
uses crt;
var
A, B, R, M, W, NWD: integer;
begin
clrscr;
R:= 0;
Write('program szuka NWD liczb A i B, podaj te liczby : '); read(A, B);
if A > B then
begin W := A; M := B; end
else
begin W := B; M := A; end;
repeat
R := W - (M*(W div M));
if R > 0 then
if M > R then
begin W := M; M := R; end;
until R = 0;
NWD := M;
write('NWD = ', NWD);
end.
Zadanie: narysuj schemat blokowy algorytmu j.w.
Jednoczesne wyszukiwanie min i max z tablicy T[1..N] metodą dziel i
zwyciężaj
Metoda polega na kolejnym porównywaniu ze sobą elementów T[1] z T[2], T[3] z T[4] itd. Większy z
elementów staje się kandydatem do maksimum mniejszy kandydatem do minimum.
Specyfikacja algorytmu:
dane wejściowe: N całkowite, T[1..N]  tablica liczb całkowitych
dane wyjściowe: min, max  najmniejszy i największy element tablicy T
algorytm:
program MinMax;
zmienne
N, i, max, min: całkowite;
T[1..100] tablica liczb całkowitych;
rozpocznij
czytaj(N);
dla i := 1 do N wykonuj czytaj(T[i]);
min := T[1]; max := T[1]
jeżeli (N mod 2) = 1 to
rozpocznij N = N + 1; T[N] = T[N-1]
kiedy i <= N-1 wykonuj
rozpocznij
jeżeli T[i] > T[i+1] to
rozpocznij
zakończ
w przeciwnym razie
rozpocznij
jeżeli T[i+1] > max to max := T[i+1]
jeżeli T[i] < min to min := T[i]
zakończ
zakończ
zakończ.
zadanie: sprawdz
poprawność algorytmu i napisz program w oparciu o ten algorytm.
Generowanie liczb Fibonacciego
Początkowo rodzi się para królików, która po miesiącu osiąga dojrzałość i po następnym miesiącu wydaje na
świat parę królików. Z kolei każda nowa para co miesiąc osiąga dojrzałość i po każdym następnym miesiącu
również wydaje na świat kolejną parę królików itd.
Narysuj drzewo obrazujące rozmnażanie się królików:
Oznaczmy liczbę par królików miesiącu
D  ilość królików dorosłych
M  ilość królików młodych
Liczbę urodzin par królików
U := liczba urodzin par królików
Liczba królików w momencie rozpoczęcia eksperymentu
D := 0
M := 1
U := 0
Zmiany po miesiącu
U := D {Liczba królików dorosłych w poprzednim miesiącu}
D := D + M {młode króliki z poprzedniego miesiąca dorastają zwiększając liczbę królików dorosłych}
M := U {liczba królików młodych jest równa liczbie urodzin }
Zmiany po miesiącu
U := D {Liczba królików dorosłych w poprzednim miesiącu}
D := D + M {młode króliki z poprzedniego miesiąca dorastają zwiększając liczbę królików dorosłych}
M := U {liczba królików młodych jest równa liczbie urodzin }
itd.
Napisz algorytm (schemat blokowy) i program obliczający liczbę par królików w poszczególnych miesiącach.
Sortowanie
Sortowanie przez wybór
Ta odmiana sortowania polega wybieraniu elementów dla kolejnych pozycji.
T[1] T[2] T[3] T[4] T[5]
2 3 1 4 0
Zajmijmy 1 pozycją: Na pozycji 1 powinna się znajdować najmniejsza z liczb znajdujących się w na pozycjach
od 1..5. Szukamy więc najmniejszej liczby z pozycjach 1..5  jest nim liczba na pozycji 5. Zamieniamy więc
miejscami liczby z pozycji 1 i 5.
T[1] T[2] T[3] T[4] T[5]
0 3 1 4 2
Na pozycji 1 znajduje się już właściwa liczba.
Zajmijmy się więc kolejną pozycją czyli pozycją 2: Na pozycji 2 powinna się znajdować najmniejsza z liczb
znajdujących się w na pozycjach od 2..5. Szukamy więc najmniejszej liczby z pozycji 2..5  jest nim liczba z
pozycji 3. Zamieniamy więc miejscami liczby z pozycji 2 i 3.
T[1] T[2] T[3] T[4] T[5]
0 1 3 4 2
Na pozycji 2 znajduje się już właściwa liczba.
Zajmijmy się więc kolejną pozycją czyli pozycją 3: Na pozycji 3 powinna się znajdować najmniejsza z liczb
znajdujących się w na pozycjach od 3..5. Szukamy więc najmniejszej liczby z pozycji 3..5  jest nim liczba z
pozycji 5. Zamieniamy więc miejscami liczby z pozycji 3 i 5.
T[1] T[2] T[3] T[4] T[5]
0 1 2 4 3
Na pozycji 3 znajduje się już właściwa liczba.
Zajmijmy się więc kolejną pozycją czyli pozycją 4: Na pozycji 4 powinna się znajdować najmniejsza z liczb
znajdujących się w na pozycjach od 4..5. Szukamy więc najmniejszej liczby z pozycji 4..5  jest nim liczba z
pozycji 5. Zamieniamy więc miejscami liczby z pozycji 4 i 5.
T[1] T[2] T[3] T[4] T[5]
0 1 2 3 4
Na pozycji 4 znajduje się już właściwa liczba. Właściwa liczba znajduje się też na pozycji 5 (zastanów się
dlaczego).
Algorytm w pseudokodzie:
Program SortPrzezWybór;
zmienne
n, i, j, zp: całkowita; {n  ilość elementów do sortowania}
T: array [1..100] of całkowita;
Funkcja PozMin(OdElem, DoElem: całkowita): całkowita;
var i, min: integer;
zacznij
min := T[odelem];
i := odelem+1 to dokąd wykonuj
zacznij
jeżeli T[i] < min to
zacznij
min := T[i];
PozMin := i;
zakończ;
zakończ;
zakończ;
Procedura czytajtablicę;
zacznij
.
.
zakończ;
Procedura czytajtablicę;
zacznij
.
.
zakończ;
rozpocznij
czytajtablicę
dla i := 1 do n wykonuj
rozpocznij
ZP := T[i];
j := PozMin(i,n);
T[i] := T[j];
T[j] := ZP;
zakończ
zakończ.
Zadanie: zapisz algorytm j.w. w postaci programu.
Sortowanie bąbelkowe
Sortowanie bąbelkowe polega na porównywaniu parami kolejnych liczb i przestawianiu ich jeśli występują w
niewłaściwej kolejności.
przykład:
T[4] 4
T[3] 3 T[1] 3
T[2] 5 T[2] 4
T[1] 1 T[3] 5
Porównujemy element pierwszy i drugi element. T[4] 1
Drugi jest mniejszy od pierwszego więc powinien Porównujemy elementy trzeci i czwarty. Czwarty
występować przed pierwszym, wobec tego jest mniejszy od trzeciego, powinien się więc
zamieniamy je miejscami. znajdować przed czwartym elementem, wobec tego
zamieniamy je miejscami.
T[1] 3
T[2] 4 T[1] 3
T[3] 5 T[2] 4
T[4] 1 T[3] 1
Porównujemy elementy drugi i trzeci. Trzeci nie T[4] 5
jest mniejszy od drugiego, powinien się więc nadal Porównaliśmy dwa ostatnie elementy. Zaczynamy
znajdować za drugim elementem. nowy cykl przestawiania ponownie zaczynając od
elementów pierwszego i drugiego.
Przestawianie należy kontynuować dotąd kiedy nie można wykonać żadnego przestawienia w cyklu. Wówczas
porządek będzie właściwy.
Przykładowy program:
Program BubleSort;
.
.
procedure zamień(var a, b integer);
var zp: integer;
begin
zp := a;
a := b;
b := zp;
end;
.
.
begin
zamieniono := false
repeat
for i := 1 to n-1 do
begin
if T[i] < T[i+1] then
begin
zamień(T[i], T[i+1]);
zamieniono := true
end;
end;
until not(zamieniono)
end.
Zadanie: Dokończ program j.w. Uzupełnij go o niezbędne procedury do czytania i wyświetlania. Odpowiedz na
pytanie: jaką rolę spełnia var w deklaracji parametrów procedury zamień.
Algorytmy rekurencyjne.
Definicje rekurencyjne
Definicją rekurencyjną nazywamy taką definicję w której przedmiot definiowany jest definiowany za pomocą
samego siebie.
Przykład rekurencyjnej definicji rysowania płotka:
Zauważmy że płotek z n  sztachetek składa się z sztachetki i płotka z n  1 sztachetek
I I I I I I I I "=" I I I I I I I I
Definicję rysowania płotka możemy więc zapisać jak niżej:
Rysuj płotek z n  sztachetek "=" rysuj sztachetkę "+" rysuj płotek z n  1 sztachetek
Przykład rysowania płotka wg definicji rekurencyjnej j.w.:
Rysuj płotek z 3 sztachetek "=" rysuj sztachetkę "+" rysuj płotek z (3-1) sztachetek
I + Rysuj płotek z 2 sztachetek
Rysuj płotek z 2 sztachetkami "=" rysuj sztachetkę "+" rysuj płotek z (2-1) sztachetek
I I + rysuj płotek z 1 sztachetek
Rysuj płotek z 1 sztachetkami "=" rysuj sztachetkę "+" rysuj płotek z (1-1) sztachetek
I I I + rysuj płotek z 0 sztachetek
Rysuj płotek z 0 sztachetkami "=" rysuj sztachetkę "+" rysuj płotek z (0-1) sztachetek
I I I I+ rysuj płotek z -1 sztachetek
Jak widać narysowana już została jedna sztachetka za dużo i nie zanosi się na to aby rekurencja miała się
kiedykolwiek zakończyć. Mamy tutaj do czynienia z definicją rekurencyjną w której brak jest warunku
zakończenia rekurencji. Wykonywanie takiej definicji rekurencyjnej nigdy się nie kończy.
Zobaczmy jak wygląda poprawnie zdefiniowane rysowanie płotka z n  sztachetek
jeżeli n > 1 Rysuj płotek z n  sztachetek "=" rysuj sztachetkę "+" rysuj płotek z n  1 sztachetek
Jeżeli n = 1 Rysuj płotek z n  sztachetek "=" rysuj sztachetkę
Rysuj płotek z 3 sztachetek "=" rysuj sztachetkę "+" rysuj płotek z (3-1) sztachetek
I + Rysuj płotek z 2 sztachetek
Rysuj płotek z 2 sztachetkami "=" rysuj sztachetkę "+" rysuj płotek z (2-1) sztachetek
I I + rysuj płotek z 1 sztachetek
Rysuj płotek z 1 sztachetkami "=" rysuj sztachetkę
I I I
Jak widać po dodaniu warunku zakończenia rekurencji definicja funkcjonuje już poprawnie.
Przykład rekurencyjnejdefinicji obliczania sumy z kolejnych liczb
naturalnych od i do J
przypatrzmy się takiej sumie
i j =
2+3+4+5+6 = 2 + (3+4+5+6)
suma(i..j) =i + suma(i+1..j)
możemy więc zapisać:
suma(i, j) = i + suma(i, j)
Jak już wiemy z wcześniejszego przykładu taka definicja bez warunku zakończenia rekurencji nigdy się nie
zakończy.
Poprawna definicja z warunkiem zakończenia rekurencji wygląda jak niżej:
jeżeli i < j to suma(i, j) = i + suma(i+1,j)
Jeżeli i = j to suma = j
Przykład obliczania sumy wg definicji j.w.
suma(1, 4) = 1 + suma(2, 4)
wyrażenie po prawej stronie "=" musi czekać na obliczenie suma(2, 3)
suma(2, 3) = 2 + suma(3, 4)
wyrażenie po prawej stronie "=" musi czekać na obliczenie suma(3, 4)
suma(3, 4) = 3 + suma(4, 4)
wyrażenie po prawej stronie "=" musi czekać na obliczenie suma(4, 4)
suma(4, 4) = 4
wartość suma(4, 4) mamy już policzoną
sytuacja w tej chwili wygląda jak niżej: suma(3, 4) = 3 + 4 = 7
w tej chwili czekają na obliczenie:
suma(1, 4) = 1 + suma(2, 4) wstawiamy policzoną wartość suma(3, 4) do
suma(2, 4) = 2 + suma(3, 4) czekającego wyrażenie. W tym momencie sytuacja
suma(3, 4) = 3 + suma(4, 4) wygląda następująco:
jest policzona w tej chwili czekają na obliczenie:
suma(4, 4) = 4 suma(1, 4) = 1 + suma(2, 4)
jest policzona
wstawiamy policzoną wartość suma(4, 4) do suma(2, 4) = 2 + 7 = 9
czekającego wyrażenie. W tym momencie sytuacja wstawiamy policzoną wartość suma(3, 4) do
wygląda następująco: czekającego wyrażenie. W tym momencie sytuacja
w tej chwili czekają na obliczenie: wygląda następująco:
suma(1, 4) = 1 + suma(2, 4) w tej chwili czekają na obliczenie:
suma(2, 4) = 2 + suma(3, 4) suma(1, 4) = 1 + suma(2, 4)
jest policzona jest policzona
suma(3, 4) = 3 + 4 = 7 suma(2, 4) = 2 + 7 = 9
wstawiamy policzoną wartość suma(2, 4) do
wstawiamy policzoną wartość suma(3, 4) do czekającego wyrażenia. W tym momencie sytuacja
czekającego wyrażenie. W tym momencie sytuacja wygląda następująco:
wygląda następująco: jest policzona
w tej chwili czekają na obliczenie: suma(1, 4) = 1 + 9
suma(1, 4) = 1 + suma(2, 4) Wykonywanie definicji jest zakończone
suma(2, 4) = 2 + suma(3, 4)
jest policzona
Realizacja algorytmów rekurencyjnych w postaci procedur i funkcji
rekurencyjnych
Procedura rysująca płotek wg. definicji z wcześniejszych przykładów:
definicja:
jeżeli n > 1 Rysuj płotek z n  sztachetek "=" rysuj sztachetkę "+" rysuj płotek z n  1 sztachetek
Jeżeli n = 1 Rysuj płotek z n  sztachetek "=" rysuj sztachetkę
odpowiadająca jej procedura:
procedure RysujPlotek(n: integer);
begin
if n > 1 then
Begin
Write("I "); {rysuj sztachetę}
RysujPlotek(n  1)
End;
if n = 0 then Write("I "); {rysuj sztachetę}
end;
Funkcja obliczająca sumę kolejnych liczb naturalnych z zakresu i..j wg.
definicji z wcześniejszych przykładów
definicja:
jeżeli i < j to suma(i, j) = i + suma(i+1,j)
Jeżeli i = j to suma = j
odpowiadająca jej funkcja:
function Suma(i, j: integer): integer;
begin
if i < j then suma := i + suma(i,j);
if i = j then suma := j;
end.
Definicja rekurencyjna n! i odpowiadająca jej funkcja
Przyjrzyjmy się jak oblicza się n!:
5! = 1*2*3*4*5
Można zauważyć że:
5! = 5 * (1*2*3*4)
A to możemy zapisać jako:
5! = 5 * (4)! lub 5! = 5 * (5-1)!
Dla ogólnego przypadku możemy więc napisać
n! = n * (n-1)!
Jak wiemy z poprzednich rozważań aby obliczenia wg takiej definicji nie trwały w nieskończoność konieczny
jest warunek zakończenia rekurencji.
cała więc definicja wygląda więc jak niżej:
jeżeli n > 0 to n! = n * (n-1)!
jeżeli n = 0 to n! = 1
funkcja realizująca definicję j.w.
function silnia(n: integer): integer;
begin
if n > 0 then silnia := n * silnia(n-1);
if n = 0 then silnia = 1;
end;
Definicja rekurencyjna schematu Hornera i odpowiadająca jej funkcja
W ogólnym przypadku możemy zapisać wielomian w postaci:
W(n) = x(...x((x(an)+an-1)+an-2) ...)+a1)+a0
i obliczyć jego wartość postępując jak niżej:
wielomian:
W := an
W := x*W+an-1
W := x*W+an-2
.
.
.
W := x*W+a0
ponumerujmy kolejno obliczane wielomiany i odwróćmy ich kolejność:
Wn := x*Wn-1+a0
.
.
.
W3 := x*W2+an-2
W2 := x*W1+an-1
W0 := an
można więc napisać następująca definicję rekurencyjną schematu Hornera
jeżeli i = 0 to W(i) = an
jeżeli i > 0 to W(i) = x*W(i-1)+a(n-i)
realizująca ją funkcja:
function wielomian(var a: array[1..5] of integer; x; i, n: integer): integer;
begin
if i = 0 then W(i) := a[n];
if n>0 then W(i) := x*W(i-1)+a[n-i];
end;
Zadania: policz wartości liczone przez definicje rekurencyjne z tego działu, uruchom programy rekurencyjne z
tego działu, napisz definicje i procedury lub funkcje rekurencyjne podnoszące x do potęgi n, liczące min z
tablicy i sortujące tablicę poprzez prosty wybór.