Obkladové obdélníky
Máte dvě hádanky. Kolika způsoby můžete vyplnit obdélník 1 x n kombinací čtverců 1 x 1 a obdélníků 1 x 2? Kolika způsoby můžete vyplnit obdélník 2 x n obdélníky 1 x 2?
VÝZVA
Proč tyto dva hádanky dávají stejné odpovědi? Jaké jsou odpovědi, když jsou vyplňované obdélníky dlouhé 10? A co když jsou dlouhé 20?
PRŮZKUM
V čem jsou si tyto dva problémy podobné a starším hádankám? Jak se věci změní v hádance 1 krát n, když použijeme dílky 1 krát 1 a 1 krát 3? Jak se věci změní v hádance 1 krát n, když použijeme dílky 1 krát 1, 1 krát 2 a 1 krát 3?
Poznámky
VÝZVA
Vidět, jak aplikovat dřívější výsledky na část nebo celou novou skládačku, je silná dovednost.
Tyto dva hlavolamy jsou si naprosto podobné. Svislé dílky v obdélníku 2 x n odpovídají dílkům o rozměrech 1 x 1 v obdélníku 1 x n a vodorovné dílky v obdélníku 2 x n odpovídají dílkům o rozměrech 1 x 2 v obdélníku 1 x n. Mezi těmito dvěma hlavolamy tedy není žádný rozdíl.
Také obdélníková hádanka 1 x n je přesně jako hádanka s kroky ve hře „Fibonacci – 2“. Postupovat krok za krokem je jako vkládat čtverec 1 x 1 a postupovat krok za krokem je jako vkládat obdélník 1 x 2. Obě hádanky jsou stejné, takže analýza a výsledky jsou stejné.
PRŮZKUM
Pokud použijeme obdélníky 1 x 1 a 1 x 3, hodně se změní. Podívejte se na prvních několik hodnot a zvažte, jak se vypočítávají. Pro prvních několik hodnot dostaneme 1, 1, 2, 3, 4, 6 a 9. Obecně je další hodnota součtem aktuální hodnoty a hodnoty o dva kroky dříve. Výpočet je poměrně jednoduchý, ale už se nejedná o Fibonnaciho posloupnost.
Pokud použijeme 1 krát 1, 1 krát 2 a 1 krát 3, věci se změní ještě dramatičtěji. Prvních několik hodnot je nyní dáno čísly 1, 2, 4, 7, 13 a 24. Další hodnota v posloupnosti je součtem předchozích tří hodnot.
Posloupnosti, jako je tato, které definují své další členy pomocí definovaného vzorce zahrnujícího předchozí členy, se nazývají rekurzivní posloupnosti. Fibonacciho čísla nejsou jedinou rekurzivní posloupností, ale jsou pravděpodobně nejznámější.