A perfekt kód vajon lehetséges?

"Ilyen nincs. Ilyen nem lehet. Ilyen dilemmába nem eshet senki." Pedig már estek páran. És itt most nem a megfelelő adatszerkezetek helyes megválasztásáról van szó, amiről írtál (persze az is fontos).

Hozok neked egy példát:

Van N számod. Szeretném, ha meghatároznád páronként a legnagyobb közös osztójukat.

Azaz minden számnak meg kell határozni a maradék N-1 számmal vett legnagyobb közös osztóját.

Hogyan oldanád meg?

Adná magát, hogy először mind az N számnak határozzuk meg az összes osztóját és tároljuk el a memóriában. Így minden szám osztóit csak egyszer kell meghatározni. Később amikor az adott szám osztóira van szükséged (ez ugye pontosan N-1-szer fog megtörténni minden számnál) csak kiolvasod a memóriából.

Kétségen kívül ez egy gyors megoldás lesz.

Na de ha sok számunk van és ráadásul nagy számok, amiknek potenciálisan sok osztójuk van, mi meg kevés memóriával gazdálkodunk, akkor könnyen előfordulhat, hogy nem férnek el a memóriában. Ez esetben kénytelenek leszünk minden számnak mind az N-1 alkalommal kiszámolni az összes osztóját (vagy oké, ha már tudjuk mivel keressük a legnagyobb közös osztóját, akkor elég csak a számok egy kisebb részét vizsgálni). Ehhez jóval kevesebb memóriára van szükség, de kétségtelenül lassabb lesz.

Az ilyen és ehhez hasonló esetekről beszélek.