Rekursioonipuu uurija

Vali rekursiivne eeskiri, määra n ja uuri tehtavate väljakutsete arvu. Näed ka, kui mitu korda lahendatakse uuesti juba lahendatud ülesannet.

Näidisarvutus — Rekursioonipuu uurija

Tehtud väljakutsed	25
Erinevad alamülesanded	7
Väljakutseid alamülesandele	3,6
Suurim sügavus	5
Saavutatud baasjuhud	13
Kombineerimissammud	12

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Rekursioonipuu uurija

Rekursioonipuu sisaldab iga väljakutse kohta ühte sõlme. Juur on esialgne väljakutse ja sõlme lapsed on tema enda tehtud uued väljakutsed. Puust saab lugeda kolme arvu. Sõlmede koguarv annab tööaja "ühe väljakutse" ühikutes. Puu kõrgus näitab pinu sügavust. Erinevate sõlmede arv aga näitab tööaega olukorras, kus iga vastus jäetakse kohe esimesel leidmisel meelde.

Kuidas nähtut lugeda

Leht avaneb algolekus fib(6) peal. Selle puu on kogu ulatuses joonistamiseks piisavalt väike: 25 sõlme, millest 7 tähistavad vastava alamülesande esimest esinemist. Seetõttu näitabki erinevate alamülesannete lahter arvu 7 ja väljakutseid alamülesandele näitab 3,6. Suurim sügavus on 5, mis kulgeb mööda ahelat fib(6) → fib(5) → … → fib(1). Kõigist 25 väljakutsest 13 jõuavad baasjuhuni, ülejäänud 12 aga liidavad igaüks kaks tagastatud väärtust.

Ei kehti, kui: Näitaja väljakutseid alamülesandele annab lubaduse puhverdamise kasulikkuse kohta. Hanoi torni korral see lubadus murdub. Hanoi n = 20 juures annab 2 097 151 väljakutse peale vaid 21 erinevat alamülesannet. See teeb 99 864,3 väljakutset alamülesandele, mis on 95,8 korda suurem näitaja kui Fibonaccil sama n-i korral. Puhverdamine ei säästa siin midagi praktilist. Väljakutse hanoi(20) vastus on 1 048 575 liigutusest koosnev nimekiri. Varem meelde jäetud nimekirja tagastamine nõuab sama palju ressurssi kui selle uuesti genereerimine. Puhvertabel tasub end ära siis, kui vastus on lühike ja puu on suur. Fibonacci vastus on üksainus täisarv. Hanoi vastuseks on aga terve lahtikirjutatud puu ise.

Fibonacci jada arvutamine ühtesid loendades 🖖

Võtame n-i väärtuseks 20. Puus on 21 891 väljakutset. Neist 10 946 jõuavad baasjuhuni, ülejäänud 10 945 on lihtsalt liitmised. Ainult fib(1) tagastab väärtuse 1 ning fib(0) tagastab 0. Seega on 6 765 lehe väärtuseks 1 ja 4 181 lehte ei panusta summasse midagi. F(20) on 6 765, mis vastab täpselt leitud ühtede arvule. Iga rekursioonist saadud väärtus on teatava hulga ühtede summa. See tõsiasi ei sõltu kuidagi n-ist. Baasjuhtude lahtris seisab alati F(n+1) ja ühtesid on nende hulgas alati F(n).

Kaks 21 891 väljakutsega puud, millest vaid üks kordab ennast 🖖

Naiivne fib(20) ja mestimissort 10 946 elemendil teevad täpselt sama arvu väljakutseid. Mõlema 21 891 väljakutset jagunevad 10 946 baasjuhuks ja 10 945 kombineerimissammuks. Kuuest näidikust kolm langevad kokku. Mõlemad eeskirjad hargnevad igas sisemises sõlmes kaheks, seega erinevus ei peitu harunemises. Erinevate alamülesannete näidik paljastab tõe: 21 versus 21 891. Puhvertabel kahandab Fibonacci puu 21 tööühikuni ja jätab mestimissordi puu 21 891 ühiku peale. Mestimissordi puhul on jaotused sama massiivi erinevad lõigud. Salvestatud vastus "5 473 elemendi jadale" tähistaks täiesti valesid 5 473 elementi.

Üksainus lahutatud 1 eraldab φⁿ ja 2ⁿ 🖖

Nii Hanoi kui ka Fibonacci rekursioon hargneb kaheks ja saavutab pea sama sügavuse, vastavalt 20 ja 19. Hanoi teeb n = 20 juures 2 097 151 väljakutset. Fibonacci piirdub 21 891 väljakutsega, mida on 95,8 korda vähem. Ainus erinevus koodis peitub teises rekursiivses argumendis. Hanoi kutsub end argumendiga n−1 välja kaks korda, Fibonacci kasutab argumente n−1 ja seejärel n−2. See üksainus lahutamistehe alandab eksponentsiaalfunktsiooni aluse 2 pealt väärtusele φ = 1,618. Käärid muudkui avanevad. Juba n = 30 korral on suhe 2 147 483 647 ja 2 692 537, mis annab erinevuseks 798 korda.

Ülesanded täielikult lahendatud

Kutsete arvu suletud kuju, kui naiivne fib(10) teeb 177 kutset 6 sammu
Tööriist näitab, et naiivne fib(10) teeb 177 väljakutset ja fib(11) teeb 287. Leia väljakutsete arvu kinnine kuju ja tõesta see. Seejärel arvuta, kui kaugele jõuab naiivne Fibonacci ühe sekundiga masinal, mis suudab teha 10⁸ väljakutset sekundis.
1. Liida kummalegi arvule üks. Saad 178 ja 288. Mõlemad on paarisarvud ja nende pooled on 89 ning 144, mis vastavad jada liikmetele F₁₁ ja F₁₂. Püstitame hüpoteesi, et C(n) = 2F(n+1) − 1, kusjuures F(1) = F(2) = 1.
  
  $C (10) = 177, C (11) = 287 ⟹ \frac{178}{2} = 89 = F_{11}, \frac{288}{2} = 144 = F_{12}$
2. Puu selgitab, kust selline kahekordistumine pärineb. Iga sisemine sõlm teeb täpselt kaks väljakutset ja iga leht ei tee ühtegi. Seega on L lehega puus L − 1 sisemist sõlme ja kokku 2L − 1 sõlme. Tööriist näitab n = 10 korral 89 baasjuhtu ja 2 × 89 − 1 = 177.
  
  $N = 2 L - 1 ⟹ 2 \times 89 - 1 = 177$
3. Vaatame esmalt baasjuhte. fib(0) ja fib(1) tagastavad väärtuse ilma rekursioonita, seega C(0) = C(1) = 1. Mõlemad avaldised 2F(1) − 1 ja 2F(2) − 1 annavad samuti väärtuseks 1.
  
  $C (0) = C (1) = 1, 2 F_{1} - 1 = 2 F_{2} - 1 = 1$
4. Nüüd teeme induktsioonisammu. Eeldame, et valem kehtib n − 1 ja n − 2 korral. Väljakutse n juures moodustab ühe sõlme koos oma kahe alampuuga. Nende all olevad kaks Fibonacci arvu liituvad jada definitsiooni enda põhjal. Võttes n = 11 saame 2 × 144 − 1 = 287, mida trükib välja ka tööriist.
  
  $C (n) = 1 + C (n - 1) + C (n - 2) = 1 + (2 F_{n} - 1) + (2 F_{n - 1} - 1) = 2 F_{n + 1} - 1$
5. Jätame puu nüüd kõrvale. Binet' valem annab F(m) = (φ^m − ψ^m)/√5, kus φ = 1,6180 ja |ψ| < 1. Seega on F(m) φ^m/√5 ümardatuna lähima täisarvuni ja C(n) ≈ 2φⁿ⁺¹/√5. Üks sekund kiirusel 10⁸ väljakutset sekundis lubab teha 10⁸ väljakutset. See fikseerib φⁿ⁺¹ väärtuseks 1,1180 × 10⁸.
  
  $C (n) \approx \frac{2 φ ^{n + 1}}{5} = 1 0^{8} ⟹ φ^{n + 1} = \frac{1 0 ^{8} 5}{2} = 1.1180 \times 1 0^{8}$
6. Võtame logaritmid. ln(1,1180 × 10⁸) = 18,5323 ja ln φ = 0,4812. Seega n + 1 = 38,51 ning n = 37,5. Ümardame allapoole, sest murdosaga väljakutse ei jõua lõpule.
  
  $n + 1 = \frac{ln ( 1.1180 \times 1 0 ^{8} )}{ln φ} = \frac{18.5323}{0.4812} = 38.51$
Vastus

n = 37. Tööriist kinnitab kahte naabrit: 78 176 337 väljakutset n = 37 korral ja 126 491 971 väljakutset n = 38 korral. Sealt edasi kahekordistab iga järgmine 1,44 n-i väärtuses tehtava töö, sest ln 2 / ln φ = 1,44. Samal ajal näitab erinevate alamülesannete lahter n = 37 juures arvu 38. Seitsekümmend kaheksa miljonit väljakutset kolmekümne kaheksale küsimusele vastamiseks ongi kogu dünaamilise planeerimise argument ühte lausesse kokku võetuna.
Kolm haru, mis kasvavad aeglasemalt kui kaks 6 sammu
Kolme sammuga trepp kutsub end igas sõlmes kolm korda, Hanoi torn kaks. Laadi Trepp, kolm haru, n=20, arvuta välja, kumb kahest puust kiiremini kasvab, ja otsusta, mida hargnemistegur juhisena väärt on.

Ava see ülesanne tööriistas
1. Loe rekurrents definitsioonist, mitte pildilt. Üks väljakutse sõlme enda jaoks, siis veel kolm kohtades n − 1, n − 2 ja n − 3, ja kõik, mis on 2 või vähem, tagastab ilma rekursioonita.
  
  $C (n) = 1 + C (n - 1) + C (n - 2) + C (n - 3), C (0) = C (1) = C (2) = 1$
2. Eelda, et arv kasvab geomeetriliselt, C(n) ≈ A xⁿ, ja asenda. Jaga läbi x-iga astmes n − 3 ning ees seisev 1 jääb madalamat järku mürana maha, alles jääb kuupvõrrand. Selle ainus reaalarvuline lahend on 1,8392868, tribonacci konstant.
  
  $C (n) \sim A x^{n} ⟹ x^{3} = x^{2} + x + 1 ⟹ x = 1.8392868$
3. Sama retsept ülejäänud kahel definitsioonil. Fibonacci kutsub end kohtades n − 1 ja n − 2, seega x² = x + 1 ja juur on φ = 1,6180340. Hanoi kutsub end kaks korda kohas n − 1, seega x = 2 ja lahendada pole midagi.
  
  $fib : x^{2} = x + 1 \Rightarrow φ = 1.6180340; hanoi : C (n) = 1 + 2 C (n - 1) \Rightarrow x = 2$
4. Kontrolli, ära usu. Sea n 29 peale, loe väljakutsete kaarti, sea n 30 peale, loe uuesti, jaga. Trepp annab 1,83929, Fibonacci 1,61803, Hanoi täpselt 2. Viis kohta pärast koma kõigil kolmel.
  
  $\frac{C ( 30 )}{C ( 29 )} : \frac{56 , 843 , 233}{30 , 905 , 041} = 1.83929, \frac{2 , 692 , 537}{1 , 664 , 079} = 1.61803, \frac{2 ^{31} - 1}{2 ^{30} - 1} = 2.00000$
5. Mida juur sulle ei anna, on kogus ise. 1,8393²⁰ on 196 331, kaart aga näitab 128 287, seega istub ees tegur 0,65; Hanoi väljakutseid on täpselt 2ⁿ⁺¹ − 1, tegur 2. Baasjuhud määravad selle konstandi ja rekurrents määrab juure, ning ainult juur otsustab, kes lõpuks võidab.
  
  $1.839286 8^{20} = 196, 331 against 128, 287 ⟹ A = 0.6534; hanoi : C (n) = 2^{n + 1} - 1, A = 2$
6. Lõpp jõuab siin kiiresti kätte. n = 20 juures teeb Hanoi 16,3 korda rohkem väljakutseid kui trepp ja n = 30 juures 37,8 korda rohkem. Suhe kahekordistub iga 8,3 sammu järel, sest ln 2 jagatuna ln(2 ÷ 1,8393)-ga on 8,27.
  
  $\frac{2 ^{21} - 1}{128 , 287} = 16.3, \frac{2 ^{31} - 1}{56 , 843 , 233} = 37.8, \frac{ln 2}{ln ( 2/1.8393 )} = 8.27$
Vastus

Hanoi kasvab kiiremini, 2 versus 1,8393, ja kolmas haru ei maksa trepile midagi, mida ta endale lubada ei suudaks. Hargnemistegur on kasvukiiruse ülemine tõke ja see saavutatakse ainult siis, kui iga laps on täpselt ühe sammu võrra väiksem. Trepp kulutab kaks kolmest väljakutsest argumentidele, mis on 2 ja 3 võrra väiksemad, ja need alampuud on nii odavad, et nad ei liitu kunagi selleks haruks, mille trepp näiliselt juurde sai.

Retsept on see osa, mida hoida, sest ta töötab definitsioonil, mida keegi pole sinu eest juba lahendanud. Loenda lapsed, pane tähele, kui palju igaüks argumenti kahandab, kirjuta x suurima kahanemise astmes ülejäänud kahanemiste x-astmete summana ja võta suurim reaalarvuline juur. Üks hoiatus käib sellega kaasas: see on fakt naiivse puu kohta ja naiivne puu ei ole see, mida keegi kirjutaks. Erinevate alamülesannete kaart näitab trepi puhul n = 20 juures 21 ja Hanoi puhul samuti 21, seega kaotab memo eksponendi sootuks ja kasvukiirus lakkab midagi tähendamast.

$x^{k} = j \sum m_{j} x^{k - j} (m_{j} children at n - j, k = max j) : 1.8393 < 2$

Õpitee

Loe tööd, mitte sekundeid

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.