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
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.
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(); // teljes sor beolvasása
a = Integer.parseInt(sor.split(" ")[0]); // darabolás szóközök mentén
b = Integer.parseInt(sor.split(" ")[1]);
r = a % b; // maradékos osztás
while( r > 0){
a = b;
b = r;
r = a % b;
}
System.out.print("LNKO(a,b)= ");
System.out.println(b);
}
}
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(); // teljes sor beolvasása
a = Integer.parseInt(sor.split(" ")[0]); // darabolás szóközök mentén
b = Integer.parseInt(sor.split(" ")[1]);
r = a % b; // maradékos osztás
while( r > 0){
a = b;
b = r;
r = a % b;
}
System.out.print("LNKO(a,b)= ");
System.out.println(b);
}
}