MIW Lekcja nr 21

Materiały » Lekcje

LEKCJA 20

LEKCJA 22

LEKCJA 21

Wieża Hanoi

WSTĘP

Wieżę Hanoi wymyślił francuski matematyk Édouard Lucas dla zabawy w 1883 roku. Édouard Lucas jest również autorem wzoru na n-ty wyraz ciągu Fibonacciego.

ZASADY GRY

Wieża składa się z trzech słupków: początkowy, końcowy, pomocniczy (tzw.bufor). Naszym zadaniem jest przenieść wszystkie krążki z początkowego słupka na końcowy z zachowaniem tego samego kształtu wieży, pomagając sobie słupkiem pomocniczym i stosując następujące zasady:

Można układać tylko mniejszy na większy krążek
Można przekładać tylko jeden krążek jednocześnie
Można brać tylko krążek z samej góry

Na początek spróbuj rozwiązać łamigłówkę samodzielnie, wybierając różną ilość krążków.

GRA - WIEŻA HANOI

<p>Twoja przeglądarka nie obsługuje ramek</p>

Jeżeli masz problem z ułożeniem krążków, możesz obejrzeć symulację rozwiązania dla poszczególnych ilości krążków, wybierając odpowiednią opcję w grze.

WZÓR REKURENCYJNY

WZÓR REKURENCYJNY na obliczenie ilości potrzebnych ruchów w zależności od ilości krążków:

Uzasadnienie wzoru rekurencyjnego:

WZÓR OGÓLNY:

Dowód indukcyjny z wykorzystaniem wzoru rekurencyjnego.

Twierdzenie:

Dowód:

Sprawdzenie dla n=1 f(1) = 2^1-1=1

Istotnie tyle trzeba ruchów do przeniesienia jednopiętrowej wieży, zatem twierdzenie jest prawdziwe dla n=1

Założenie indukcyjne. Zakładamy, że twierdzenie jest prawdziwe dla pewnej dodatniej liczby naturalnej k

f(k) = 2^k-1 $k\in N_+$

Teza indukcyjna. Twierdzenie dla

$f(k+1) = 2^{(k+1)}-1$

Krok indukcyjny. Pokażemy, że jeśli twierdzenie jest prawdziwe dla k, to jest prawdziwe także dla k+1

Przekształcając wzór rekurencyjny f(n) = 2f(n-1)+1 dla n=m+1 otrzymujemy f(m+1) = 2f(m)+1

Podstawiając na miejsce f(m) wzór z założenia indukcyjnego otrzymujemy:

$f(m+1) = 2(2^m-1)+1 = 2^{m+1}-2+1 = 2^{m+1}-1$

Otrzymaliśmy tezę indukcyjną, więc wzór jest poprawny.

Wyprowadzenie wzoru ogólnego:

$f(n) = 2f(n-1) + 1   \;\;\;\ |+1$

f(n) + 1 = 2f(n-1) + 2 = 2(f(n-1) + 1)

Niech: g(n) = f(n) + 1

Wtedy: g(n) = f(n) + 1 = 2(f(n-1) + 1) = 2g(n-1)

g(n) = 2g(n-1)

Czyli otrzymaliśmy równanie określające ciąg geometryczny.

Wiedząc, że f(1) = 1 , to g(1) = f(1) + 1 = 1 + 1 = 2
$g(2) = 2g(1) = 2\cdot 2 = 4$
g(3) = 8
…
g(n) = 2^n

Po powrocie do f(n) otrzymujemy: f(n) = g(n)-1= 2^n- 1

LEGENDA

Jak głosi stara hinduska legenda, przy stworzeniu świata, w jego środku, pod dachem świątyni, umieszczone zostały trzy diamentowe pałeczki. Na jedną z nich nałożonych było 64 złotych krążków o zmniejszających się średnicach tworząc złoty stożek. Dzień i noc, zmieniając się bezustannie, mnisi przekładali krążki na trzecią pałeczkę. Musieli jednak zachować pewne zasady. Mogli posiłkować się drugą pałeczką, jednakże nie wolno było im przenosić więcej niż jeden krążek i umieszczać większego na mniejszym. Gdy wykonają swoje zadanie - nastąpi koniec świata!

OBLICZMY WIĘC DATĘ KOŃCA ŚWIATA ZGODNIE Z LEGENDĄ

Podstawiając do wzoru otrzymujemy: $2^{64}-1=18 446 744 073 709 551 615$ (blisko 18 i pół tryliona) sekund, co daje około 584 542 mld lat, a wszechświat ma około 13,7 mld lat.

LEKCJA 20

LEKCJA 22

LEKCJA 21