NézetNyomtat

Algoritmusleíró eszközök

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 ) // Feltesszük, hogy "a" nagyobb...
    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(); // 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);
            
    }
}