Programozás‎ > ‎

Algoritmusok tervezése: finomítás felülről lefelé

A módszert egy példán keresztül mutatjuk be.

A FELADAT

Keressük meg egy és egymillió között a tökéletes számokat! (A tökéletes szám olyan pozitív egész, amely egyenlő a nála kisebb pozitív osztói összegével.)

1. SZINT

Ciklus n=1-től 1000000-ig 
    Ha n tökéletes akkor KI(n) 
Ciklus vége

2. SZINT

Ciklus n:=1-től 1000000-ig 
    d := n valódi osztóinak összege 
    Ha d = n akkor KI(n) 
Ciklus vége

3. SZINT

Ciklus n:=1-től 1000000-ig 
    d := 0 
    Ciklus k := 1-től (n-1)-ig 
        Ha k | n akkor d := d + k 
    Ciklus vége 
    Ha d = n akkor KI(n) 
Ciklus vége

KÓDOLÁS

Java

class tokeletes {
    public static void main(String[] args){
        for(int n = 1; n <= 1000000; n++){
            int d = 0;
            for(int k = 1; k<n; k++){
                if( n % k ==0) d += k;
            }
            if(d == n)
                System.out.println(n);
        }
    }
}


MEGJEGYZÉS A HATÉKONYSÁGRÓL

A fenti program futtatásához nagy-nagy türelem szükséges. Az algoritmus négyzetes, a lépésszám nagyjából egymillió négyzetének fele, ami 1011 nagyságrendű.