Obkladanie obdĺžnikov
Máte dve hádanky. Koľkými spôsobmi môžete vyplniť obdĺžnik s rozmermi 1 x n kombináciou štvorcov 1 x 1 a obdĺžnikov 1 x 2? Koľkými spôsobmi môžete vyplniť obdĺžnik s rozmermi 2 x n obdĺžnikmi 1 x 2?
VÝZVA
Prečo tieto dve hádanky dávajú rovnaké odpovede? Aké sú odpovede, keď majú vypĺňané obdĺžniky dĺžku 10? A čo keď majú dĺžku 20?
PRIESKUM
V čom sú si tieto dva problémy podobné a predchádzajúcim hádankám? Ako sa veci zmenia v hádanke 1 x n, ak použijeme dieliky 1 x 1 a 1 x 3? Ako sa veci zmenia v hádanke 1 x n, ak použijeme dieliky 1 x 1, 1 x 2 a 1 x 3?
Poznámky
VÝZVA
Vedieť, ako aplikovať skoršie výsledky na časť alebo celú novú hádanku, je silná zručnosť.
Tieto dve hádanky sú si úplne rovnaké. Zvislé dieliky v obdĺžniku 2 x n zodpovedajú dielikom 1 x 1 v obdĺžniku 1 x n a vodorovné dieliky v obdĺžniku 2 x n zodpovedajú dielikom 1 x 2 v obdĺžniku 1 x n. Takže medzi týmito dvoma hádankami nie je žiadny rozdiel.
Obdĺžniková hádanka 1 x n je presne ako hádanka s krokmi v hre „Fibonacci – 2“. Postupovať krok za krokom je ako vkladať štvorec 1 x 1 a postupovať krok za krokom je ako vkladať obdĺžnik 1 x 2. Tieto dve hádanky sú rovnaké, takže analýza a výsledky sú rovnaké.
PRIESKUM
Ak použijeme obdĺžniky 1 x 1 a 1 x 3, veľa sa zmení. Pozrite sa na prvých niekoľko hodnôt a zvážte, ako sa vypočítavajú. Pre prvých niekoľko hodnôt dostaneme 1, 1, 2, 3, 4, 6 a 9. Vo všeobecnosti je ďalšia hodnota súčtom aktuálnej hodnoty a hodnoty o dva kroky vyššie. Výpočet je dosť jednoduchý, ale už to nie je Fibonnaciho postupnosť.
Ak použijeme 1 x 1, 1 x 2 a 1 x 3, veci sa zmenia ešte dramatickejšie. Prvých niekoľko hodnôt je teraz daných číslami 1, 2, 4, 7, 13 a 24. Ďalšia hodnota v postupnosti je súčtom predchádzajúcich troch hodnôt.
Takéto postupnosti, ktoré definujú svoje ďalšie členy pomocou stanoveného vzorca zahŕňajúce predchádzajúce členy, sa nazývajú rekurzívne postupnosti. Fibonacciho čísla nie sú jedinou rekurzívnou postupnosťou, ale sú pravdepodobne najznámejšie.