Algorytm Euklidesa: Różnice pomiędzy wersjami
Z Lem
| Linia 7: | Linia 7: | ||
'''while''' n ≠ m | '''while''' n ≠ m | ||
'''do''' | '''do''' | ||
| + | ::<math>\color{blue}\mathbf{Oznaczenie}\ niech\ l=max(n,m) </math> | ||
:r:=0; | :r:=0; | ||
:'''while''' r ≠n '''and''' r ≠m | :'''while''' r ≠n '''and''' r ≠m | ||
| Linia 13: | Linia 14: | ||
:'''od'''; | :'''od'''; | ||
:'''if''' r=n '''then''' n_miejsze:=true; max:=m '''else''' n_mniejsze:=false; max:=n '''fi'''; | :'''if''' r=n '''then''' n_miejsze:=true; max:=m '''else''' n_mniejsze:=false; max:=n '''fi'''; | ||
| + | ::<math>\color{blue}\mathbf{Stwierdzenie}\ (n<m \wedge m=max(n,m) \vee m<n \wedge n=max(n,m)) </math> | ||
:q:=0; | :q:=0; | ||
:'''while''' r≠max | :'''while''' r≠max | ||
| Linia 18: | Linia 20: | ||
::r:= r+1; q:=q+1 | ::r:= r+1; q:=q+1 | ||
:'''od'''; | :'''od'''; | ||
| + | ::<math>\color{blue}\mathbf{Stwierdzenie}\ q = |m-n| \land q\geq 1\land r=max(n,m) </math> | ||
:'''if''' n_mniejsze '''then''' m:=q '''else''' n := q '''fi''' | :'''if''' n_mniejsze '''then''' m:=q '''else''' n := q '''fi''' | ||
| + | ::<math>\color{blue}\mathbf{Stwierdzenie}\ max(n,m) < l </math> | ||
'''od''' | '''od''' | ||
( ''wynik'' = n) | ( ''wynik'' = n) | ||
| − | + | ::::::::::przejdź do [[analiza algorytmu Euklidesa|analizy algorytmu Euklidesa]] | |
Wersja z 14:06, 15 lut 2013
(* Algorytm Euklidesa inaczej *)
(* Dane: n>0 i m>0 liczby naturalne *)
(* Wynik: nwd(n,m) *)
while n ≠ m do
- [math]\color{blue}\mathbf{Oznaczenie}\ niech\ l=max(n,m) [/math]
- r:=0;
- while r ≠n and r ≠m
- do
- r:=r+1
- od;
- if r=n then n_miejsze:=true; max:=m else n_mniejsze:=false; max:=n fi;
- [math]\color{blue}\mathbf{Stwierdzenie}\ (n\ltm \wedge m=max(n,m) \vee m\ltn \wedge n=max(n,m)) [/math]
- q:=0;
- while r≠max
- do
- r:= r+1; q:=q+1
- od;
- [math]\color{blue}\mathbf{Stwierdzenie}\ q = |m-n| \land q\geq 1\land r=max(n,m) [/math]
- if n_mniejsze then m:=q else n := q fi
- [math]\color{blue}\mathbf{Stwierdzenie}\ max(n,m) \lt l [/math]
od ( wynik = n)
- przejdź do analizy algorytmu Euklidesa
