Know-how, előadás, rekurzív szubrutinok
A rekurzív algoritmusok helyett iteratív
Mivel új kontextus jön létre minden alkalommal, amikor a rekurzív szubrutin (amely még mindig nem fejeződik be) újraindul, a számítógép memóriája nagyon gyorsan elfogy. Ezért a rekurzió minden tisztaságát nem lehet a programozás gazdaságos módszereinek tulajdonítani. Van még egy speciális tudomány - dinamikus programozás. a rekurzív algoritmusok megfelelő iteratív algoritmusokkal való helyettesítésének módszereinek tanulmányozása. Nem fogjuk beavatkozni a dinamikus programozás elveinek bemutatásába, hanem korlátozzuk magunkat a rekurzív programok nem rekurzív átalakításának példáihoz.
Ha a szubrutin végrehajtása ugyanazon szubrutin egy hívását eredményezi, akkor ez a rekurzió lineárisnak mondható. A lineáris rekurzió meglehetősen könnyű helyettesíteni egy iteratív algoritmussal. Például végrehajthatja a faktoriális függvényt. a "Rekurzió" bekezdés elején meghatározott kétféleképpen.
Ha a szubrutin minden egyes példánya többször is hívható, akkor a rekurzió nemlineáris vagy "elágazó". Annak érdekében, hogy ez a rekurzió egy iteratív algoritmusává váljon, sok erőfeszítést igényel, és talán még változtathat a feldolgozott adatszerkezetben is. Az "elágazó" rekurzió példája az a folyamat, amelynek során egy számot a fentiekben tárgyalt tényezőkre bomlanak.
Példa egy rekurzív és nem rekurzív algoritmus összehasonlítására
A feladat. Két barát úgy döntött, hogy kempingezni, összegyűjteni és mérlegelni minden szükséges dolgot. Hogyan osztják meg a tárgyak egy részét két részre a legőszintébb módon?
(Természetes számok vannak, talán ismétléssel, két alcsoportra kell osztani, így a súlyösszegek közötti különbség minimális.)
Rekurzív algoritmus
Egy adott súlycsoport minden lehetséges részhalmazát meg kell vizsgálni. A probléma megoldásához számos klasszikus algoritmus létezik, a legegyszerűbbet használjuk, amelyet "teljes bust" -nak nevezünk. Teljes névvel összhangban, ez az algoritmus végigmegy a készletek összes lehetséges változatán.
Rekurzív algoritmus végrehajtása
Teljes keresés a vágással
A fenti program sok felesleges munkát igényel. Például nincs szükség folytatni a következő készlet létrehozását, miután az aktuális különbség már meghaladta a korábban megállapított minimumot. Ezen túlmenően, ha egy bizonyos időpontban a minimum hirtelen 1 vagy 0 értékű lesz (a bemeneti adatok paritásától függően), további erőfeszítésekre is szükségtelen lesz, mivel nem lehet kevesebb.
Ezekkel a megjegyzésekkel javítható a program szövege. Ezt a kényelmetlen munkát hagyjuk a hajlandóságra.
Nem rekurzív algoritmus
Itt további indoklásra és lineáris tömbre van szükség.
A program legfontosabb része az algoritmus ismétlõdõ megvalósítása minden olyan lehetséges változat teljes kereséséhez, amely megfelel a bemeneti korlátoknak. Fő rekurzív eltérése a kis mennyiségű memória használata az aktuális adatok tárolásához. Minden információt tárolnak a tömbökben. vegye és diff. A számításokhoz csak ezt az információt használjuk minden lépésben. Ez a megközelítés elkerüli a folyamatos rekalculációkat, amelyek a rekurzív algoritmus "súlyosságának" okai.
Tehát a program első részében a bemeneti elemek számlálását és elrendezését kell figyelembe venni súlyuk csökkenő sorrendjében. A helytakarékosság érdekében nem adunk részletesen ennek a blokknak a végrehajtását: mindenféle rendezési mód alkalmas erre (lásd 4. előadás). Fontos, hogy a válogatás eredményeképpen minden bemeneti adat két, k hosszúságú lineáris tömbben (a különböző súlyok száma) legyen megírva.
Most úgy véljük, hogy a tömbök a tárgyak különböző súlyait tárolják, csökkenő sorrendben rendezve, és a kol csoport az egyes súlyok objektumainak száma.
Ezenkívül az adatbevitel során az összes tárgy súlyát összegezzük, ez a teljes tömeg a változó összegbe kerül. Igaz, akkor ugyanaz a változó nem tárolja a teljes összsúlyt, de csak a felét (figyelembe véve az eredeti összeg paritását) - a további összehasonlítás kényelméért.
Nem adjuk meg a program szövegét és a min () függvény végrehajtását - mint nem különösebben érdekes.