4962385659

2 Wprowadzenie

2.1    Algorytm Euklidesa

•    Dane wejściowe: dwie liczby naturalne m,n> 0.

•    Wynik: NWD(m,n).

Opis algorytmu. Odejmuj liczbę większą od mniejszej aż do wyrównania liczb. Zapis algorytmu.

a:=m; b:=n;

dopóki a<> b wykonuj {NWD(a,b)=NWD(m,n), a,b>=l} jeśli a<b to b:=b-a w przeciwnym przypadku a:=a-b wypisz(a)

W algorytmie użyliśmy następujących operacji elementarnych:

1.    cztery instrukcje przypisania;

2.    iteracja nieograniczona (pętla while);

3.    instrukcja warunkowa;

4.    instrukcja wejścia wyjścia.

W nawiasach { } zapisaliśmy niezmiennik pętli, tzn. takie zdanie które jeśli jest prawdziwe przy wejściu do pętli to pozostaje prawdziwe po każdym pełnym wykonaniu pętli.

Czy program robi to co chcemy? Tak:

1.    Po każdym wykonaniu pętli prawdziwy jest niezmiennik pętli NWD(a,b) = NWD(m, n), a,b> 1.

2.    Po wyjściu z pętli a = b. Zatem a = NWD(a, b).

3.    Pętla wykonuje się co najwyżej m+n —2 razy (w szczególności nie może działać w nieskończoność).

Ad 1. Wystarczy pokazać, że jeśli a > b to NWD(a,b) = NWD(a — b,b). W tym celu wystarczy pokazać, że liczba k dzieli a i b wiw gdy dzieli (a — b) i b.

Ad 2. Oczywiste.

Ad 3. Każde wykonanie instrukcji warunkowej zmniejsza sumę a+b o co najmniej 1. Z drugiej strony mamy a > 1, b > 1. Zatem instrukcja warunkowa może być wykonana co najwyżej m + n — 2 razy.

2.2    Problem algorytmiczny

Problem (zadanie) algorytmiczny polega na

•    scharakteryzowaniu wszystkich poprawnych danych wejściowych;

•    scharakteryzowaniu oczekiwanych wyników jako funkcji danych wejściowych.

4