Programozás‎ > ‎

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. Az alábbiakban Euklidesz maradékos osztáson alapuló algoritmusát fogjuk ismertetni.

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);
            
    }
}