Algoritmus tervezés felülről lefelé történő finomítással
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
Pascal
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);
}
}
}
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 $10^{11}$ nagyságrendű.