Lektionsindhold -- Tastaturgenvej: 'u'  Forrige side: Towers of Hanoi (3) -- Tastaturgenvej: 'p'  Næste side: Quicksort [Section] -- Tastaturgenvej: 'n'  Forelæsningsnoter - alle slides sammen  Alfabetisk indeks  Hjælp om disse noter  Kursets hjemmeside    Rekursion - slide 21 : 27

Towers of Hanoi (4)

Det er let at se at antallet af flytninger F(n) vokser eksponentielt med antallet af diske i tårnet.

Mere præcist ser vi at F(n) = 2 n - 1.

n 2n 10-9 · 2n 10-3 · 2n
5 32 3.2 · 10-8 sek 3.2 · 10-2 sek
25 3.4 · 107 0.03 sek 9.3 timer
50 1.1 · 1015 13 dage 35702 år
65 3.7 · 1019 1170 år 1.17 · 109 år
80 1.2 · 1024 3.8 · 107 år 3.8 · 1013 år
100 1.2 · 1039 4.0 · 1013 år 4.0 · 1020 år