kleines Tetris

15.01.2007, 00:15	MatheNici	Auf diesen Beitrag antworten »
kleines Tetris hallo, ich habe eine aufgabe angefangen zu lösen und wollt mal fragen ob ich auf dem richtigen weg bin. Aufgabe: - An ist die Anzahl der Belegungen eines 2 x n Rechtecks mit 1 x 2 Dominosteinen. - Anzahl der Belegungen bedeutet Anzahl der Möglichkeiten das Rechteck voll zu belegen (bsp. A2=2 usw.) Die Rekusion soll für An bestimmt und berechnet werden. Also ich hab mir erstmal ein paar Rechtecke aufgemalt: http://www.oertelserv.de/Tetris.JPG So das hat ein wenig zeit gekostet Wenn die Anzahl der Möglichkeiten stimmen, dann kam mir die Reihe irgendwie bekannt vor. 1,2,3,5... So wie es aussieht ist das doch die Fibonacci Reihe, hmm war jetzt zu faul das auch noch für 2x5 aufzumalen. Also ist doch An=A(n-1) + A(n-2) für n>2. Is das soweit richtig? Is das die Rekursion? Wie soll ich An denn berechnen? Oder soll man da die geschlossene Form von der Rekusion bilden?
15.01.2007, 02:26	20_Cent	Auf diesen Beitrag antworten »
laut wikipedia ist die geschlossene darstellung der fibonacci-folge folgendes: $\begin{eqnarray} f_n=\frac{1}{\sqrt{5}}\left[\;{\left(\frac{1+ \sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\;\right] \end{eqnarray}$ ich hab allerdings keine ahnung, ob deine überlegungen richtig sind mfG 20
15.01.2007, 13:01	MatheNici	Auf diesen Beitrag antworten »
hmmm ja, aber wäre schon gut wenn mir das jemand bestätigen könnte.. bzw. wie man auf die geschlossene Form kommt
15.01.2007, 13:53	AD	Auf diesen Beitrag antworten »
Wenn du Bestätigung brauchst, sollst du sie haben: Ja, die Formel ist richtig. Wie man drauf kommt? Das Erklären dauert ein wenig lange und ist hier im Forum bestimmt auch schon irgendwann geschehen, such mal die diversen Fibonacci-Threads danach durch. Es sei erstmal nur soviel gesagt, dass man mit dem Ansatz $\begin{eqnarray} f_n=\lambda^n \end{eqnarray}$ zu Werke geht und dann Linearkombinationen solcher Basislösungen betrachtet.
15.01.2007, 14:38	MatheNici	Auf diesen Beitrag antworten »
hmm okay, muss ich das irgendwie beweisen das für das Tetris die fibonacci folge gilt, oder reicht meine ausführung?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »