Algorytm Euklidesa: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(Utworzył nową stronę „(* Algorytm Euklidesa inaczej *) (* Dane: n>0 i m>0 liczby naturalne *) (* Wynik: nwd(n,m) *) '''while''' n ≠ m '''do''' :r:=0; :'''while''' r ≠n '''and''' r...”)
 
 
(Nie pokazano 11 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
(* Algorytm Euklidesa inaczej *)
+
(* Algorytm Euklidesa inaczej, zauważ, że w tym algorytmie jedyną operacją jest dodaj jeden, jedynym predykatem jest równość. *)
(* Dane: n>0 i m>0 liczby naturalne *)
+
 
(* Wynik:  nwd(n,m)  *)
+
(* Dane: x>0 i y>0 liczby naturalne *)
 +
::{A1} <math>\color{blue}\mathbf{Deklaracje: }\ typ(x, y, n, m, r, q, max)=\mathbb{N}\ \land\ typ(n\_mniejsze)=Boolean  </math>
 +
(* Wynik:  nwd(x,y)  *)
 +
 
 +
n:=x; m:=y;
  
 
'''while''' n ≠ m  
 
'''while''' n ≠ m  
 
'''do'''
 
'''do'''
 +
::<math>\color{red}\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 10: Linia 15:
 
::r:=r+1
 
::r:=r+1
 
:'''od''';
 
:'''od''';
:'''if''' r=n '''then''' nmiejsze:=true; max:=m '''else''' nmniejsze:=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 16: Linia 22:
 
::r:= r+1; q:=q+1
 
::r:= r+1; q:=q+1
 
:'''od''';
 
:'''od''';
:'''if''' nmniejsze '''then''' m:=q '''else''' n := q '''fi'''
+
::<math>\color{blue}\mathbf{Stwierdzenie}\ q = |m-n| \land (1 \leq q < max(n,m))\land r=max(n,m) </math>
 +
:'''if''' n_mniejsze '''then''' m:=q '''else''' n := q '''fi'''
 +
::<math>\color{blue}\mathbf{Stwierdzenie}\ max(n,m) < \color{red}l </math>
 
'''od'''
 
'''od'''
 
( ''wynik'' = n)
 
( ''wynik'' = n)
 +
 +
 +
::::::::::przejdź do [[analiza algorytmu Euklidesa|analizy algorytmu Euklidesa]]

Aktualna wersja na dzień 07:03, 29 lis 2017

(* Algorytm Euklidesa inaczej, zauważ, że w tym algorytmie jedyną operacją jest dodaj jeden, jedynym predykatem jest równość. *)

(* Dane: x>0 i y>0 liczby naturalne *)

{A1} [math]\color{blue}\mathbf{Deklaracje: }\ typ(x, y, n, m, r, q, max)=\mathbb{N}\ \land\ typ(n\_mniejsze)=Boolean [/math]

(* Wynik: nwd(x,y) *)

n:=x; m:=y;

while n ≠ m do

[math]\color{red}\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 (1 \leq q \lt max(n,m))\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 \color{red}l [/math]

od ( wynik = n)


przejdź do analizy algorytmu Euklidesa