Két rekurzív függvényt adunk meg. Rekurziós és rekurzív algoritmusok

Rekurzió az, amikor egy szubrutin felhívja magát. Amikor először találkozik egy ilyen algoritmikus konstrukcióval, a legtöbb ember bizonyos nehézségeket tapasztal, de egy kis gyakorlat és rekurzió érthető és nagyon hasznos eszközzé válik a programozási arzenálban.

1. A rekurzió lényege

Egy eljárás vagy funkció tartalmazhat más eljárásokra vagy funkciókra történő hívásokat. Beleértve az eljárást is hívhatja magát. Itt nincs paradoxon - a számítógép csak egymás után hajtja végre azokat a parancsokat, amelyekkel a programban találkozik, és ha eljáráshívással találkozik, egyszerűen elkezdi végrehajtani ezt az eljárást. Nem számít, melyik eljárás adta meg a parancsot.

Példa egy rekurzív eljárásra:

Rec eljárás (a: egész szám); kezdődik, ha a\u003e

Fontolja meg, hogy mi történik, ha egy hívás a főprogramba kerül, például a Rec (3) formában. Az alábbiakban egy blokkvázlat mutatja az utasítások végrehajtásának sorrendjét.

Ábra: 1. A rekurzív eljárás blokkvázlata.

A Rec eljárást az a \u003d 3 paraméterrel hívják meg. Ez tartalmazza a Rec eljárás hívást az a \u003d 2 paraméterrel. Az előző hívás még nem fejeződött be, így elképzelhető, hogy egy másik eljárás készül, és az első még nem fejezi be a munkáját, mielőtt befejezné a munkáját. A hívási folyamat akkor ér véget, amikor az a \u003d 0. paraméter. Ebben a pillanatban az eljárás négy példányát hajtják végre egyidejűleg. Az egyszerre végrehajtott eljárások számát hívjuk meg rekurzió mélysége.

A negyedik hívott eljárás (Rec (0)) kinyomtatja a 0 számot, és befejezi a munkáját. Ezt követően a vezérlő visszatér az őt meghívó eljáráshoz (Rec (1)), és kinyomtatja az 1. számot. A kezdeti hívás négy számot nyomtat: 0, 1, 2, 3.

Egy másik vizuális képet arról, hogy mi történik, az 1. ábra mutatja. 2.

Ábra: 2. A Rec eljárás végrehajtása a 3. paraméterrel abból áll, hogy végrehajtja a Rec eljárást a 2. paraméterrel, és kinyomtatja a 3. számot. Viszont a Rec eljárás végrehajtása a 2. paraméterrel a Rec eljárás végrehajtásáról az 1. paraméterrel és a 2. szám kinyomtatásából áll.

Önálló gyakorlatként vegye fontolóra, hogy mit kap, amikor felhívja a Rec (4) -et. Fontolja meg azt is, hogy mi történik, amikor az alábbiakban ismertetett Rec2 (4) eljárást hívja meg, ahol az utasítások megfordulnak.

Rec2 eljárás (a: egész szám); kezdődik writeeln (a); ha a\u003e 0, akkor Rec2 (a-1); vége;

Vegye figyelembe, hogy a fenti példákban a rekurzív hívás egy feltételes utasításon belül van. Ez a rekurzió végének előfeltétele. Vegye figyelembe azt is, hogy az eljárás más paraméterrel hívja meg magát, mint azzal, amellyel meghívták. Ha az eljárás nem használ globális változókat, akkor erre is szükség van, hogy a rekurzió ne folytatódjon a végtelenségig.

Lehetséges egy kissé összetettebb séma: az A függvény meghívja a B függvényt, ez pedig meghívja az A. Ezt hívják komplex rekurzió... Kiderült, hogy az első leírt eljárásnak meg kell hívnia a még le nem írt eljárást. Ezt fel kell használni, hogy ez lehetséges legyen.

A eljárás (n: egész szám); (Az első eljárás előre leírása (címe)) B eljárás (n: egész szám); (A második eljárás részletes leírása) A eljárás (n: egész szám); (Az A eljárás teljes leírása) begin writeln (n); B (n-1); vége; B eljárás (n: egész szám); (A B eljárás teljes leírása) kezdődik writeln (n); ha n

A B eljárás elõzetes leírása lehetõvé teszi az A eljárás elõhívását. Az A eljárás elõzetes leírása ebben a példában nem szükséges, esztétikai okokból kerül hozzáadásra.

Ha egy közönséges rekurziót mi hasonlíthatunk egy mioboroszunkhoz (3. ábra), akkor egy komplex rekurzió képét le lehet rajzolni egy jól ismert gyermekversből, ahol "Farkasok a félelemtől ették egymást". Képzelje el, hogy két farkas eszik egymást, és megérti a komplex rekurziót.

Ábra: 3. Ouroboros egy kígyó, amely felfalja a saját farkát. Theodore Pelekanos (1478) "Synosius" alkímiai értekezéséből származik.

Ábra: 4. Komplex rekurzió.

3. Egy hurok szimulálása rekurzióval

Ha egy eljárás önmagát hívja meg, akkor ez valójában a benne lévő utasítások ismételt végrehajtásához vezet, ami hasonló egy hurok munkájához. Egyes programozási nyelvek egyáltalán nem tartalmaznak ciklusos konstrukciókat, így a programozók hagyják, hogy az ismétléseket rekurzióval szervezzék (például Prolog, ahol a rekurzió a fő programozási technika).

Szimuláljuk például a for loop munkáját. Ehhez szükségünk van egy lépésszámláló változóra, amelyet például eljárásparaméterként lehet megvalósítani.

1. példa

Eljárás LoopImitation (i, n: egész szám); (Az első paraméter a lépésszámláló, a második paraméter a lépések teljes száma) begin writeeln ("Hello N", i); // Itt vannak olyan utasítások, amelyek megismétlődnek, ha i

Egy olyan hívás eredménye, mint a LoopImitation (1, 10), tízszer hajtja végre az utasításokat, ellenszámváltással 1-ről 10-re. Ebben az esetben a következőt nyomtatja ki:

Helló N 1
Helló N 2
…
Szia N 10

Általában nem nehéz belátni, hogy az eljárási paraméterek a korlátok a számlálóértékek megváltoztatásához.

Felcserélheti a rekurzív hívást és az ismételni kívánt utasításokat, a következő példa szerint.

2. példa

Eljárás LoopImitation2 (i, n: egész szám); kezdődik, ha én

Ebben az esetben az eljárást rekurzív módon hívják meg, mielőtt az utasítások végrehajtása megkezdődne. Az eljárás új példánya mindenekelőtt egy másik példányt is hív, és így tovább, amíg el nem érjük a maximális számláló értéket. Csak ezután hajtja végre az utoljára meghívott eljárások az utasításait, az utolsó előtti pedig az utasításokat stb. A LoopImitation2 (1, 10) hívása fordított sorrendben kinyomtatja az üdvözleteket:

Szia N 10
…
Helló N 1

Ha rekurzívnak nevezett eljárások láncolatát képzeljük el, akkor az 1. példában átmegyünk a korábban hívott eljárásoktól a későbbiekig. A 2. példában, fordítva, későbbről elejére.

Végül rekurzív hívást lehet tenni az utasítások két blokkja közé. Például:

Eljárás LoopImitation3 (i, n: egész szám); kezdődik writeeln ("Hello N", i); (Az utasítások első blokkja itt található), ha i

Itt az első blokk utasításait egymás után hajtják végre, majd a második blokk utasításait fordított sorrendben hajtják végre. Amikor meghívjuk a LoopImitation3 (1, 10) -t, a következőket kapjuk:

Helló N 1
…
Szia N 10
Szia N 10
…
Helló N 1

Egyszerre két ciklusra lesz szükség ahhoz, hogy ugyanezt rekurzió nélkül végezzük.

Használható az a tény, hogy ugyanazon eljárás egyes részeinek végrehajtása időben el van osztva. Például:

3. példa: Szám konvertálása bináris rendszerré.

Mint tudják, egy bináris szám számjegyeinek megszerzése úgy történik, hogy egy maradékkal elosztjuk a 2-es számrendszer alapjával. Ha van szám, akkor bináris ábrázolásának utolsó számjegye

Ha az egész részt elosztjuk 2-vel:

olyan számot kapunk, amelynek ugyanaz a bináris reprezentációja, de az utolsó számjegy nélkül. Így elég megismételni a fenti két műveletet, amíg a következő osztási mezőben megkapjuk az egész számot 0-val. Rekurzió nélkül így fog kinézni:

Míg x\u003e 0 kezdődik c: \u003d x mod 2; x: \u003d x div 2; írja (c); vége;

A probléma itt az, hogy a bináris ábrázolás számjegyeit fordított sorrendben számoljuk (először az utolsókat). A szám normál formában történő kinyomtatásához emlékeznie kell a tömbelemek összes számára, és külön hurokban kell megjelenítenie őket.

Rekurzióval a tömb és a második hurok nélkül könnyű a kimenetet a megfelelő sorrendbe állítani. Ugyanis:

Eljárás BinaryRepresentation (x: egész szám); var c, x: egész szám; begin (Első blokk. Az eljáráshívások sorrendjében hajtjuk végre) c: \u003d x mod 2; x: \u003d x div 2; (Rekurzív hívás), ha x\u003e 0, akkor BinárisReprezentáció (x); (Második blokk. Fordított sorrendben végrehajtva) write (c); vége;

Általánosságban elmondható, hogy nem kaptunk nyereményt. A bináris ábrázolás számai helyi változókban vannak tárolva, amelyek a rekurzív eljárás minden futó példányánál eltérőek. Vagyis nem lehetett memóriát spórolni. Éppen ellenkezőleg, sok memóriát pazarolunk el x sok helyi változó tárolására. Ennek ellenére ez a megoldás számomra gyönyörűnek tűnik.

4. Ismétlődési viszonyok. Rekurzió és iteráció

Azt mondják, hogy egy vektor szekvenciát megismétlődési reláció ad meg, ha megadjuk a kezdő vektorot és a következő vektor funkcionális függését az előzőtől

A megismétlődési relációkkal kiszámított mennyiség egyszerű példája a faktoriális

A következő tényező kiszámítható az előzőből:

A jelölés beírása után megkapjuk az arányt:

Az (1) képlet vektorai változó értékek halmazaként értelmezhetők. Ezután a szekvencia szükséges elemének kiszámítása értékeik ismételt frissítéséből áll. Konkrétan a faktoriálhoz:

X: \u003d 1; i esetén: \u003d 2-től n-ig x: \u003d x * i; writeln (x);

Minden ilyen frissítést (x: \u003d x * i) meghívunk ismétlés, és az iterációk megismétlésének folyamata az iterációval.

Megjegyezzük azonban, hogy az (1) reláció pusztán rekurzív definíciója a szekvenciának, és az n-edik elem kiszámítása valójában az f függvény többszörös felvétele önmagából:

Különösen a faktoriálhoz írhat:

Funkciótényező (n: egész szám): egész; kezdődik, ha n\u003e 1, akkor faktoriális: \u003d n * faktoriális (n-1) más tényező: \u003d 1; vége;

Meg kell érteni, hogy a függvények hívása további többletköltségekkel jár, így a faktoriális kiszámításának első lehetősége valamivel gyorsabb lesz. Általában az iteratív megoldások gyorsabban működnek, mint a rekurzív megoldások.

Mielőtt áttérne olyan helyzetekre, ahol a rekurzió hasznos, fontoljon meg még egy példát, ahol nem szabad használni.

Vizsgáljuk meg a megismétlődési relációk egy speciális esetét, amikor a sorozat következő értéke nem egy, hanem egyszerre több korábbi értéktől függ. Példa erre a jól ismert Fibonacci-szekvencia, amelyben minden következő elem a két előző összege:

"Head-on" megközelítéssel a következőket írhatja:

Funkció Fib (n: egész): egész; kezdődik, ha n\u003e 1, akkor Fib: \u003d Fib (n-1) + Fib (n-2) else Fib: \u003d 1; vége;

A Fib minden egyes hívása egyszerre két példányt hoz létre, mindegyik másolatot még kettőt stb. A tranzakciók száma a számmal együtt növekszik n exponenciálisan, bár iteratív megoldással, lineárisan n műveletek száma.

Valójában a fenti példa nem arra tanít minket MIKOR rekurziót nem szabad használni, és ez MINT nem szabad használni. Végül is, ha van gyors iteratív (hurok alapú) megoldás, akkor ugyanaz a hurok rekurzív eljárás vagy függvény segítségével valósítható meg. Például:

// x1, x2 - kezdeti feltételek (1, 1) // n - a szükséges Fibonacci számfüggvény száma Fib (x1, x2, n: egész szám): egész; var x3: egész szám; kezdődik, ha n\u003e 1, akkor kezdődik x3: \u003d x2 + x1; x1: \u003d x2; x2: \u003d x3; Fib: \u003d Fib (x1, x2, n-1); vége más Fib: \u003d x2; vége;

Ennek ellenére az iteratív megoldásokat részesítik előnyben. A kérdés az, hogy ebben az esetben mikor kell használni a rekurziót?

Bármely rekurzív eljárás és funkció, amely csak egy rekurzív hívást tartalmaz önmagában, könnyen helyettesíthető iteratív hurokkal. Ha olyan dolgot szeretne kapni, amelynek nincs egyszerű, nem rekurzív analógja, akkor tekintse meg azokat az eljárásokat és funkciókat, amelyek kétszer vagy többször hívják magukat. Ebben az esetben az elhívott eljárások halmaza már nem képez láncot, mint a 2. ábrán. 1, hanem egy egész fa. Széles körű probléma létezik, amikor a számítási folyamatot ilyen módon kell megszervezni. Számukra a rekurzió lesz a legegyszerűbb és legtermészetesebb megoldás.

5. Fák

A magukat többször nevező rekurzív függvények elméleti alapja a diszkrét matematika ága, amely a fákat tanulmányozza.

5.1. Alapvető meghatározások. A fák ábrázolásának módjai

Meghatározás: a véges halmaz Tegy vagy több csomópontból áll, amelyek:
a) Van egy speciális csomópont, ennek a fának a gyökere.
b) A többi csomópont (a gyökér kivételével) páronként elkülönülő részhalmazokban található, amelyek mindegyike viszont fa. A fákat hívják részfák ez a fa.

Ez a meghatározás rekurzív. Röviden: a fa egy gyökérből és a hozzá kapcsolódó alfákból álló halmaz, amelyek szintén fák. A fát önmagán keresztül határozzák meg. Ennek a meghatározásnak azonban van értelme, mivel a rekurzió véges. Minden alfa kevesebb csomópontot tartalmaz, mint az azt tartalmazó fa. Végül olyan részfákhoz érkezünk, amelyek csak egy csomópontot tartalmaznak, és ez már világos, mi ez.

Ábra: 3. Fa.

Ábrán. A 3. ábra egy fát mutat hét csomóval. Bár a közönséges fák alulról felfelé nőnek, szokás fordítva rajzolni őket. Ha diagramot rajzolunk kézzel, ez a módszer nyilvánvalóan kényelmesebb. Ezen következetlenség miatt néha zűrzavar lép fel, amikor azt mondják, hogy az egyik csomópont a másik felett vagy alatt helyezkedik el. Emiatt kényelmesebb a családfák leírásakor használt terminológiát használni, a csomópontokat közelebb hívni a gyökér őseihez és a távolabbi leszármazottakhoz.

A fa grafikusan ábrázolható más módon is. Közülük néhányat a 2. ábra mutat. 4. A definíció szerint a fa egy beágyazott halmazok rendszere, ahol ezek a halmazok vagy nem keresztezik egymást, vagy teljesen egymásba vannak foglalva. Az ilyen halmazokat síkbeli területekként ábrázolhatjuk (4a. Ábra). Ábrán. A 4b. Ábrán látható, hogy a beágyazott halmazok nem síkban helyezkednek el, hanem egy vonalban nyúlnak ki. Ábra: A 4b. Ábra néhány beágyazott zárójelet tartalmazó algebrai képlet diagramjaként is megtekinthető. Ábra: A 4c. Ábra a fa szerkezetének párkányként való ábrázolásának másik népszerű módját nyújtja.

Ábra: 4. A fa szerkezetek ábrázolásának egyéb módjai: a) beágyazott halmazok; b) beágyazott zárójelek; c) koncessziós lista.

A konkáv lista nyilvánvalóan hasonló a programkód formázásához. Valóban, a strukturált programozási paradigma keretein belül írt program beágyazott konstrukciókból álló faként ábrázolható.

Húzhat hasonlóságot a füles lista és a könyvekben a tartalomjegyzékek megjelenése között is, ahol a szakaszok alszakaszokat tartalmaznak, a szakaszok viszont alszakaszokat stb. Az ilyen szakaszok számozásának hagyományos módját (1. szakasz, 1.1. És 1.2. Alfejezet, 1.1.2. Alszakasz stb.) Dewey-féle tizedesrendszernek nevezzük. Ábra szerinti fára alkalmazva. 3. és 4. ábra:

1. A; 1,1 B; 1,2 C; 1.2.1 D; 1.2.2 E; 1,2,3 F; 1.2.3.1 G;

5.2. Elhaladó fák

A fa struktúrákkal társított összes algoritmus változatlanul ugyanazt az ötletet tartalmazza, mégpedig az ötletet elhaladó vagy fa bejárása... Ez a módszer a fa csomópontjainak meglátogatására, amelyben minden csomópont pontosan átjáródik. Ez a facsomók lineáris elrendezését eredményezi. Különösen három módja van: a csomókon előre, hátra és végben haladhat.

Előre haladó algoritmus:

A gyökérig,
Haladjon át az összes alfát balról jobbra közvetlen sorrendben.

Ez az algoritmus rekurzív, mivel egy fán való áthaladás tartalmaz áthaladó részfákat, és ezek viszont ugyanazon az algoritmuson haladnak.

Különösen az ábra fájának esetében. A 3. és 4. ábra szerint a közvetlen áthaladás csomópontok sorozatát adja: A, B, C, D, E, F, G.

Az eredményül kapott szekvencia megfelel a csomópontok egymást követő balról jobbra történő felsorolásának, ha egy fa beágyazott zárójelben és Dewey decimális rendszerben ábrázolja őket, valamint felülről lefelé halad, ha párkánylistaként jelenik meg.

Amikor ezt az algoritmust egy programozási nyelvben valósítják meg, a gyökér megütése megfelel bizonyos műveletek végrehajtásának az eljárás vagy a függvény által, az alfák bejárása pedig önmagának való rekurzív hívásoknak felel meg. Különösen egy bináris fa esetében (ahol minden csomópontból legfeljebb két részfa származik) a megfelelő eljárás így fog kinézni:

// Preorder Traversal - angol név a közvetlen rendelési eljáráshoz PreorderTraversal ((érvek)); begin // Séta a DoSomething ((érvek)) gyökérzeten; // A bal részfán haladjon, ha (A bal részfa létezik), akkor PreorderTransversal ((2. érv)); // Járjuk át a jobb részfát, ha (Van egy jobb részfa), akkor PreorderTransversal ((3. érv)); vége;

Vagyis először az eljárás hajtja végre az összes műveletet, és csak ezután következik be minden rekurzív hívás.

Fordított bejárási algoritmus:

Keresse meg a bal alfát,
A gyökérig,
Keresse meg a következő alfát a bal oldalon.
A gyökérig,
és így tovább, amíg a jobb szélső részfát be nem haladják.

Vagyis minden részfát balról jobbra haladunk, és a gyökérhez való visszatérés e hágók között helyezkedik el. Ábrán látható fához. A 3. és 4. ábrán látható csomópontok sorrendje: B, A, D, C, E, G, F.

A megfelelő rekurzív eljárás során a műveletek a rekurzív hívások közé kerülnek. Konkrétan egy bináris fára:

// Az Inorder Traversal az InorderTraversal ((érvek)) fordított sorrendű eljárás angol neve; begin // Lépjen át a bal részfán, ha (A bal részfa létezik), akkor InorderTraversal ((2. érv)); // Séta a DoSomething gyökéren ((érvek)); // Járjuk át a jobb részfát, ha (Van egy jobb részfa), akkor InorderTraversal ((3. érv)); vége;

Végpontok közötti átjárási algoritmus:

Keresse meg az összes alfát balról jobbra,
Menj a gyökérig.

Ábrán látható fához. A 3. és 4. ábrán látható csomópontok sorrendje: B, D, E, G, F, C, A.

A megfelelő rekurzív eljárásban a műveletek a rekurzív hívások után jelennek meg. Konkrétan egy bináris fára:

// A Postorder Traversal a PostorderTraversal ((érvek)) végrendelési eljárás angol neve; begin // Lépjen át a bal részfán, ha (A bal részfa létezik), akkor a PostorderTraversal ((2. érv)); // Járjuk át a jobb részfát, ha (Jobb részfa létezik), akkor a PostorderTraversal ((3. érv)); // Séta a DoSomething gyökéren ((érvek)); vége;

5.3. Fa nézet a számítógép memóriájában

Ha valamilyen információ a fa csomópontjaiban található, akkor annak tárolásához használhatja a megfelelő dinamikus adatszerkezetet. A Pascal-ban ez egy rekord (rekord) típusú változó segítségével történik, amely azonos típusú részfákra mutató mutatókat tartalmaz. Például egy bináris fa, ahol minden csomópont tartalmaz egy egész számot, tárolható egy PTree típusú változó segítségével, amelyet az alábbiakban ismertetünk:

Típus PTree \u003d ^ TTree; TTree \u003d rekord Inf: egész szám; LeftSubTree, RightSubTree: PTree; vége;

Minden csomópont PTree típusú. Ez egy mutató, vagyis minden csomópontot úgy kell létrehozni, hogy meghívjuk rajta az Új eljárást. Ha a csomópont levél, akkor a LeftSubTree és a RightSubTree mezőkhöz rendelik az értéket nulla... Ellenkező esetben a LeftSubTree és a RightSubTree csomópontokat az Új eljárás is létrehozza.

Az egyik ilyen rekordot sematikusan mutatjuk be. 5.

Ábra: 5. A TTree rekord sematikus ábrázolása. Egy rekordnak három mezője van: Inf - néhány szám, LeftSubTree és RightSubTree - mutató az azonos TTree típusú rekordokra.

Az ilyen rekordokból álló fa példája a 6. ábrán látható.

Ábra: 6. TTree rekordokból álló fa. Minden rekord számot és két mutatót tárol, amelyek bármelyiket tartalmazhatják nulla, vagy más, azonos típusú iratok címe.

Ha korábban nem dolgozott olyan struktúrákkal, amelyek olyan rekordokból állnak, amelyek linkeket tartalmaznak az azonos típusú nyilvántartásokhoz, akkor javasoljuk, hogy ismerkedjen meg a következővel kapcsolatos anyagokkal.

6. Rekurzív algoritmusok

6.1. Egy fa rajzolása

Figyeljük meg a fa rajzolásának algoritmusát, amely az 1. ábrán látható. 6. Ha minden sort csomópontnak tekintünk, akkor ez a kép meglehetősen megfelel a fa előző szakaszban megadott meghatározásának.

Ábra: 6. Kis fa.

A rekurzív eljárásnak nyilvánvalóan meg kell rajzolnia egy vonalat (törzs az első elágazás előtt), majd felhívnia kell magát két alfa megrajzolására. Az alfák eltérnek az őket tartalmazó fától a kiindulási pont koordinátáival, az elforgatási szöggel, a törzs hosszával és az általuk tartalmazott ágak számával (eggyel kevesebb). Mindezeket a különbségeket a rekurzív eljárás paramétereivel kell megtenni.

Az alábbiakban bemutatunk egy ilyen eljárást, amelyet a Delphi írt:

Eljárásfa (Vászon: TCanvas; // Vászon, amelyre a fát rajzolni fogják x, y: meghosszabbítva; // A gyök szöge koordinátái: kiterjesztett; // A fa növekedési szöge TrunkLength: meghosszabbítva; // Törzs n: egész szám / A villák száma (hány // rekurzív hívást kell még hívni)); var x2, y2: kiterjesztett; // A csomagtartó vége (elágazási pont) kezdődik x2: \u003d x + TrunkLength * cos (Angle); y2: \u003d y - TrunkLength * sin (Szög); Canvas.MoveTo (kerek (x), kerek (y)); Canvas.LineTo (kerek (x2), kerek (y2)); ha n\u003e 1, akkor kezdődik a fa (vászon, x2, y2, szög + Pi / 4, 0,55 * törzshossz, n-1); Fa (vászon, x2, y2, Angle-Pi / 4, 0,55 * törzshossz, n-1); vége; vége;

Ábra megszerzéséhez 6 ezt a rutint a következő paraméterekkel hívták meg:

Fa (Kép 1. Canvas, 175, 325, Pi / 2, 120, 15);

Ne feledje, hogy a rajzolás a rekurzív hívások előtt történik, vagyis a fa rajzolása közvetlen sorrendben történik.

6.2. Hanoi tornyok

A legenda szerint a Benarasi Nagy Templomban, a világ közepét jelző székesegyház alatt egy bronzkorong található, amelyre három gyémántrúd van rögzítve, egy köb magas és olyan vastag, mint egy méh. Régen, az idők legelején, ennek a kolostornak a szerzetesei voltak bűnösök Brahma isten előtt. Dühében Brahma három magas rudat emelt és az egyikre 64 tiszta arany korongot tett, és úgy, hogy mindegyik kisebb korong a nagyobbikra támaszkodik. Amint mind a 64 korong átkerül a rúdról, amelyre Brahma Isten rátette a világ megalkotásakor, egy másik rúdra, a torony a templommal együtt porrá válik, és a világ elpusztul a mennydörgések alatt.
A folyamat megköveteli, hogy a nagyobb lemez soha ne lépje túl a kisebbet. A szerzetesek nehézségekkel küzdenek, milyen sorrendben kell elvégezni az átutalást? Ennek a sorrendnek a kiszámításához szoftverrel kell felszerelni őket.

Brahmától függetlenül ezt a rejtvényt a 19. század végén Edouard Lucas francia matematikus javasolta. Az eladott változatban általában 7-8 lemezt használtak (7. ábra).

Ábra: 7. "Hanoi tornyai" puzzle.

Tegyük fel, hogy van megoldás n-1 lemez. Aztán váltásra n lemezek, kövesse az alábbiakat:

1) Váltás n-1 lemez.
2) Váltás na lemezt a fennmaradó szabad csaphoz.
3) Eltoljuk a köteget n-1 lemez, amelyet az (1) lépésben kaptunk nth lemez.

Mivel az esethez n \u003d 1, az eltolási algoritmus nyilvánvaló, akkor az (1) - (3) műveletek felhasználásával indukcióval tetszőleges számú lemezt tolhatunk.

Hozzunk létre egy rekurzív eljárást, amely kinyomtatja a teljes átvitelsorozatot egy adott számú lemezhez. Egy ilyen eljárásnak minden egyes hívásával ki kell nyomtatnia az információkat egy átadásról (az algoritmus 2. pontjából). Az (1) és (3) tételekből történő átvitel esetén az eljárás meghívja magát, a lemezek számával eggyel csökkentve.

// n - lemezek száma // a, b, c - pin számok. Az átvitel az a, // és a b érintkezők között történik a c segédcsappal. eljárás Hanoi (n, a, b, c: egész szám); kezdődik, ha n\u003e 1, akkor kezdődik Hanoi (n-1, a, c, b); writeln (a, "-\u003e", b); Hanoi (n-1, c, b, a); end else writeln (a, "-\u003e", b); vége;

Vegye figyelembe, hogy a rekurzív módon meghívott eljárások halmaza ebben az esetben fordított sorrendben áthaladó fát alkot.

6.3. Számtani kifejezések elemzése

Az elemzés feladata, hogy kiszámolja a kifejezés értékét a számtani kifejezést tartalmazó meglévő sztringből és a benne szereplő változók ismert értékeiből.

Az aritmetikai kifejezések kiszámításának folyamata bináris faként ábrázolható. Valójában a számtani operátorok mindegyikéhez (+, -, *, /) két operandus szükséges, amelyek szintén aritmetikai kifejezések lesznek, és ennek megfelelően részfának tekinthetők. Ábra: A 8. ábra egy olyan fa példáját mutatja, amely megfelel a kifejezésnek:

Ábra: 8. A (6) aritmetikai kifejezésnek megfelelő szintaxisfa.

Egy ilyen fában a végcsomópontok mindig változók lesznek (itt x) vagy numerikus állandók, és az összes belső csomópont számtani operátorokat tartalmaz. Egy operátor futtatásához először ki kell értékelnie annak operandusait. Így az ábra fáját végső sorrendben kell bejárni. Megfelelő csomópont-sorrend

hívott fordított lengyel jelölés számtani kifejezés.

Szintaxisfa készítésekor figyeljen a következő szolgáltatásra. Ha van például a kifejezés

és az összeadás és kivonás műveleteit olvassuk balról jobbra, akkor a helyes szintaxisfa plusz helyett mínuszt tartalmaz (9a. ábra). Valójában ez a fa megfelel a kifejezésnek, megkönnyítheti a fa felépítését a (8) kifejezés elemzésével, éppen ellenkezőleg, jobbról balra. Ebben az esetben egy fa fig. 9b, amely egyenértékű a 8a-val, de nem igényel karakterváltást.

Hasonlóképpen jobbról balra elemeznie kell a szorzás és osztás operátorait tartalmazó kifejezéseket.

Ábra: 9. Szintaxisfák a kifejezéshez a – b + c balról jobbra (a) és jobbról balra (b) olvasva.

Ez a megközelítés nem szünteti meg teljesen a rekurziót. Ez azonban lehetővé teszi, hogy csak egy hívást korlátozzon a rekurzív eljárásra, ami elegendő lehet, ha a motívum a maximális teljesítmény miatt aggódik.

7.3. Facsomópont meghatározása a száma alapján

Ennek a megközelítésnek az az ötlete, hogy a rekurzív hívásokat egy egyszerű hurokkal cseréljék le, amely annyiszor fog végrehajtani, ahányszor a rekurzív eljárások által létrehozott csomópontok vannak. Hogy pontosan mit fognak tenni az egyes lépéseknél, azt a lépésszám határozza meg. A lépésszám és a szükséges műveletek összehasonlítása nem triviális feladat, és minden esetben külön kell megoldani.

Tegyük fel például, hogy végrehajtani akarja k egymásba ágyazott hurkok n lépésenként:

I1 esetén: \u003d 0-tól n-1-ig tegye i2 esetén: \u003d 0-tól n-1-ig tegye i3-ig: \u003d 0-tól n-1 ig ...

Ha k előre nem ismert, lehetetlen őket kifejezetten megírni, amint azt a fentiek mutatják. A 6.5 szakaszban bemutatott technikával a rekurzív eljárás segítségével megszerezheti a szükséges számú beágyazott hurkot:

Eljárás NestedCycles (Indexek: egész tömb; n, k, mélység: egész); var i: egész szám; kezdődik, ha a mélység

Ahhoz, hogy megszabaduljon a rekurziótól és mindent egy hurokra redukáljon, vegye figyelembe, hogy ha megszámolja a radix lépéseit n, akkor minden lépésnek van egy száma, amely i1, i2, i3, ... számjegyekből vagy az Indexes tömb megfelelő értékeiből áll. Vagyis a számok megegyeznek a ciklusszámlálók értékeivel. Lépésszám a szokásos tizedesjegyzetben:

Az összes lépés lesz n k... Azáltal, hogy végigmennek a számukon a tizedes rendszerben, és mindegyiküket egy radix rendszerré fordítják n, megkapjuk az indexek értékeit:

M: \u003d kerek (IntPower (n, k)); mert i: \u003d 0-tól M-1-ig kezdődik Szám: \u003d i; p esetén: \u003d 0-tól k-1-ig kezdődik Indexek: \u003d Mod n szám; Szám: \u003d szám n n; vége; DoSomething (Indexek); vége;

Még egyszer megjegyezzük, hogy a módszer nem univerzális, és minden feladathoz ki kell találnia valami saját dolgot.

Ellenőrző kérdések

1. Határozza meg, hogy a következő rekurzív eljárások és funkciók mit fognak tenni.

a) Mit nyomtat a következő eljárás a Rec (4) meghívásakor?

Rec eljárás (a: egész szám); kezdődik writeeln (a); ha a\u003e 0, akkor Rec (a-1); writeln (a); vége;

(b) Mennyi lesz a Nod (78, 26) függvény értéke?

Funkciócsomópont (a, b: egész): egész; kezdődik, ha a\u003e b, akkor Nod: \u003d Nod (a - b, b) else, ha b\u003e a, akkor Nod: \u003d Nod (a, b - a) else Nod: \u003d a; vége;

A eljárás (n: egész szám); B eljárás (n: egész szám); A eljárás (n: egész szám); kezdje writeeln (n); B (n-1); vége; B eljárás (n: egész szám); kezdje writeeln (n); ha n

d) Mit nyomtat az alábbi eljárás a BT (0, 1, 3) hívásakor?

BT eljárás (x: valós; D, MaxD: egész szám); kezdődik, ha D \u003d MaxD, akkor writeeln (x) másként kezdődik a BT (x - 1, D + 1, MaxD); BT (x + 1, D + 1, MaxD); vége; vége;

2. Ouroboros - egy kígyó, amely a saját farkát emészti (14. ábra) kibontva, hosszú L, átmérője a fej közelében D, a hasfal vastagsága d... Határozza meg, hogy mennyi farok fér el magában, és hány rétegben fekteti le a farokot?

Ábra: 14. Kibontva mioboróinkat.

3. A fához az 1. ábrán. A 10a. Ábra a csomópontok látogatási sorrendjét mutatja az előre, hátra és végpontok közötti áthaladás sorrendjére.

4. Rajzolja be a fa grafikus ábrázolását beágyazott zárójelben: (A (B (C, D), E), F, G).

5. Rajzolja meg a következő számtani kifejezés szintaxisfáját:

Írja ezt a kifejezést fordított lengyel jelöléssel.

6. Az alábbi grafikonhoz (15. ábra) írja fel a szomszédsági mátrixot és az incidencia mátrixot.

Feladatok

1. Miután a tényezőt kellően sokszor (egymillió vagy több) kiszámította, hasonlítsa össze a rekurzív és az iteratív algoritmusok hatékonyságát. Hányszor különbözik a végrehajtási idő, és hogyan függ ez az arány a számtól, amelynek faktoriálját kiszámítják?

2. Írjon egy rekurzív függvényt, amely ellenőrzi a karakterlánc helyes zárójelét! Megfelelő elhelyezés esetén a következő feltételek teljesülnek:

a) a nyitó és záró zárójelek száma megegyezik.
(b) bármely nyitó párban - a megfelelő záró zárójelben - a zárójeleket helyesen helyezzük el.

Példák a helytelen elhelyezésre :) (, ()) (, ()) (() stb.

3. A sor zárójeleket tartalmazhat, zárójeleket és szögletes zárójeleket egyaránt. Minden nyitott zárójel megfelel egy azonos típusú zárónak (kerek - kerek, négyzet - négyzet). Írjon egy rekurzív függvényt annak ellenőrzésére, hogy a zárójelek helyesek-e ebben az esetben.

Példa a helytelen elhelyezésre: ([)].

4. A 6 hosszúságú helyes konzolszerkezetek száma 5: () () (), (()) (), () (()), ((()), (() ().
Írjon egy rekurzív programot az összes helyes 2 hosszúságú zárójelszerkezet előállításához n.

Jelzés: Helyes zárójeles szerkezet, minimális hosszúsággal "()". A rövidebb szerkezetekből a hosszabb struktúrákat kétféleképpen kapják meg:

a) ha a kisebb szerkezet zárójelben van,
(b) ha két kisebb szerkezetet írunk egymás után.

5. Hozzon létre egy rutint, amely kinyomtatja az összes lehetséges permutációt 1-től N-ig terjedő egész számokra.

6. Hozzon létre egy eljárást, amely kinyomtatja a halmaz összes részhalmazát (1, 2,…, N).

7. Hozzon létre egy eljárást, amely az N természetes szám összes lehetséges ábrázolását kinyomtatja más természetes számok összegeként.

8. Hozzon létre egy függvényt, amely a tömbelemek összegét a következő algoritmus szerint számítja ki: a tömböt felére osztjuk, az egyes felekben lévő elemek összegét megszámoljuk és összeadjuk. A tömb felének elemeinek összegét ugyanazon algoritmus segítségével számoljuk ki, vagyis ismét felére osztva. Az osztódások mindaddig történnek, amíg a tömb kapott darabjain nincs egy elem, és az összeg kiszámítása triviálissá válik.

Megjegyzés: Ez az algoritmus egy alternatíva. A valós értékű tömbök esetében ez általában kisebb kerekítési hibákat tesz lehetővé.

10. Készítsen eljárást, amely megrajzolja a Koch görbét (12. ábra).

11. Reprodukálja az 1. ábrát. 16. Az ábrán minden egyes következő iterációnál a kör 2,5-szer kisebb (ez az együttható paraméterként megadható).

Irodalom

1. D. Knut. A számítógépes programozás művészete. v. 1. (2.3. szakasz: "Fák").
2. N. Wirth. Algoritmusok és adatszerkezetek.

A „Rekurzív algoritmusok” című előadás azért jött létre, hogy felkészítse a hallgatókat az informatika és az IKT egységes államvizsgájára. A tanulmány figyelembe veszi a rekurzió meghatározását, példákat mutat be rekurzívan definiált grafikus objektumokról. Az előadás a 11. feladat megoldásának módjait tartalmazza az informatika Unified State Exam - 2015 demo verziójának tervezetéből. Az első módszer egy hívásfa felépítését jelenti, a második módszer a problémát a helyettesítési módszerrel oldja meg. 4 feladat példáját tekintjük meg mindkét módszerrel. Ezenkívül az előadás 25 feladatot tartalmaz a képzéshez Konstantin Polyakov webhelyének válaszaival.

Letöltés:

Előnézet:

A prezentációk előnézetének használatához hozzon létre magának egy Google-fiókot (fiókot), és jelentkezzen be: https://accounts.google.com

Diák feliratai:

11. feladat: USE (alapszint, idő - 5 perc) Rekurzív algoritmusok. Szerző - Korotun O. V., informatikatanár, MOU "71. számú középiskola"

Amit tudnia kell: Rekurzió - egy objektum vagy folyamat meghatározásában, leírásában, ábrázolásában ebben az objektumban vagy folyamatban, vagyis olyan helyzetben, amikor az objektum része önmagának. Embléma Orosz Föderáció rekurzívan definiált grafikai objektum: a rajta ábrázolt kétfejű sas jobb mancsában egy jogart szorítanak be, amelyet a címer kicsinyített másolata koronáz meg. Mivel ennek az emblémának a sas jobb mancsában is van egy jogar, végtelen rekurziót kapunk. Rekurzív orosz címer

A programozás során a rekurzió egy önmagából származó függvényhívás, közvetlenül vagy más funkciók révén, például az A funkció meghívja a B és a B funkciókat. A funkciót vagy eljárást beágyazott hívások számát rekurziós mélységnek nevezzük. rekurziós példa: Ha zsíros folt van a ruháján, ne aggódjon. Az olajfoltokat benzinnel távolítják el. A benzinfoltokat lúgos oldattal. A lúgokat esszenciával távolítják el. Dörzsölje le az esszenciát a lényegről. Nos, hogyan lehet eltávolítani az olajfoltokat, már tudja!

Példa feladat: Adott rekurzív algoritmus: F eljárás (n: egész szám); kezdje writeeln (n); ha n

Példa feladat: Adott rekurzív algoritmus: F eljárás (n: egész szám); kezdje writeeln (n); ha n 9. dia

Példa feladat: Adott rekurzív algoritmus: F eljárás (n: egész szám); kezdje writeeln (n); ha n 10. dia

Példa feladat: Adott rekurzív algoritmus: F eljárás (n: egész szám); kezdje writeeln (n); ha n 11. dia

15 2. példa: Adott rekurzív algoritmus: F eljárás (n: egész szám); kezdje writeeln (n); ha n

2. példa: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n 13. dia

3. példa: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-2); F (n div 2) vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? * A "csillagok" számát kiszámítva 21-et kapunk. Ebben a példában nem az n paraméter értékei jelennek meg, hanem a * * * * * * * * * * * * * * * * * * * * * *

3. példa: Adott rekurzív algoritmus: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-2); F (n div 2) vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? Oldjuk meg a problémát fa nélkül. Legyen S (n) az F (n) hívásakor megjelenő "csillagok" száma. Ekkor 1 + S (n-2) + S (n div 2), n\u003e 0 1, n S (7) -et tudnunk kell. S (7) \u003d 1 + S (5) + S (3) S (5) \u003d 1 + S (3) + S (2) S (3) \u003d 1 + S (1) + S (1) S ( 2) \u003d 1 + S (0) + S (1) \u003d 1 + 1 + S (1) \u003d 2 + S (1) S (1) \u003d 1+ S (-1) + S (0) \u003d 1 + 1 + 1 \u003d 3 Fordítsa fordítva: S (2) \u003d 2 + 3 \u003d 5 S (3) \u003d 1 + 3 + 3 \u003d 7 S (5) \u003d 1 + 7 + 5 \u003d 13 S (7) \u003d 1 + 13 + 7 \u003d 21 S (n) \u003d

4. példa: F eljárás (n: egész szám); kezdődik, ha n 18. dia

4. példa: F eljárás (n: egész szám); kezdődik, ha n 19. dia

4. példa: F eljárás (n: egész szám); kezdődik, ha n

Képzési feladatok

1. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-2); F (n div 2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (5) hívásakor? Válasz: 34

2. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-2); F (n-2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (6) hívásakor? Válasz: 58

3. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-3); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? Válasz: 15

4. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-3); F (n-2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? Válasz: 55

5. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdődik F (n-3); F (n-2); F (n div 2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (6) hívásakor? Válasz: 97

6. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdje az írást ("*"); F (n-2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? Válasz: 31

7. feladat: Rekurzív algoritmus adott: F eljárás (n: egész); begin writeln ("*"); ha n\u003e 0, akkor kezdje az írást ("*"); F (n-2); F (n div 2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? Válasz: 81.

8. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); begin writeln ("*"); ha n\u003e 0, akkor kezdje az írást ("*"); F (n-2); F (n-2); F (n div 2); vég vége; Hány csillagot nyomtat a képernyő az F (6) hívásakor? Válasz: 77

9. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdődik, ha n\u003e 0, akkor kezdődik F (n-2); F (n-1); F (n-1); vége; writeln ("*"); vége; Hány csillagot nyomtat a képernyő az F (5) hívásakor? Válasz: 148

10. feladat: Adott rekurzív algoritmus: F eljárás (n: egész szám); kezdődik, ha n\u003e 0, akkor kezdje az írást ("*"); F (n-2); F (n-1); F (n-1); vége; writeln ("*"); vége; Hány csillagot nyomtat a képernyő az F (5) hívásakor? Válasz: 197

11. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdődik, ha n\u003e 1, akkor kezdődik F (n-2); F (n-1); F (n div 2); vége; writeln ("*"); vége; Hány csillagot nyomtat a képernyő az F (7) hívásakor? Válasz: 88

12. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje el, ha n\u003e 2, akkor kezdje az írást ("*"); F (n-2); F (n-1); F (n div 2); vége; writeln ("*"); vége; Hány csillagot nyomtat a képernyő az F (6) hívásakor? Válasz: 33

13. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

14. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

15. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

16. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

17. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

18. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

19. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

20. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

21. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

22. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

23. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

24. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

25. feladat: Rekurzív algoritmus adott: F eljárás (n: egész szám); kezdje writeeln (n); ha n

Devizaárfolyamok