Algoritmusleíró eszközök
A példákhoz használt matematikai probléma
Egy 2300 éves algoritmikus probléma: határozzuk meg két pozitív egész legnagyobb közös osztóját!
Példa
$a = 360, b = 150$ esetén a legnagyobb közös osztó
$(a,b) = 30$.
Iskolás módszer és ókori módszer
Középiskolában ezt úgy tanítják, hogy a számok prímtényezős felbontásából kell kiindulni, de Euklidesz annak idején egy ennél hatékonyabb eljárást adott, ami nagyon nagy számokra is jól működik, szemben a prímfelbontásos eljárással.
A megoldás matematikája
Az algoritmus mondatszerű leírással
BE( a, b )
r := a MOD b
Ciklus amíg r > 0
a := b
b := r
r := a MOD b
Ciklus vége
KI( b )
Az algoritmus folyamatábrával
Az algoritmus struktorgrammal
Megvalósítás Pascal nyelven
program lnko;
var a, b, r: longint;
begin
writeln('a,b= ');
readln(a,b);
r := a MOD b;
while r > 0 do
begin
a := b;
b := r;
r := a MOD b;
end;
write('LNKO(a,b)=');
writeln(b);
end.
Megvalósítás Java nyelven
import java.io.*;
public class lnko {
public static void main (String args[]) throws IOException {
int a,b,r;
System.out.println("a,b= ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String sor = br.readLine();
a = Integer.parseInt(sor.split(" ")[0]);
b = Integer.parseInt(sor.split(" ")[1]);
r = a % b;
while( r > 0){
a = b;
b = r;
r = a % b;
}
System.out.print("LNKO(a,b)= ");
System.out.println(b);
}
}
