Rekursion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:33 Fr 20.04.2007 | | Autor: | bobie |
| Aufgabe | Es sei [mm] a_{n} [/mm] die Anzahl der Pflasterungen eines n*2 Feldes mit 1*2 Dominosteinen. Bestimmen Sie eine homogene, lineare Rekursion zweiter Ordnung für [mm] a_{n}. [/mm]
Hinweis: Betrachten Sie die Dominosteine am rechten Ende des Feldes. |
Wie bestimme ich eine soclche Rekursion?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Es sei [mm]a_{n}[/mm] die Anzahl der Pflasterungen eines n*2 Feldes
> mit 1*2 Dominosteinen. Bestimmen Sie eine homogene, lineare
> Rekursion zweiter Ordnung für [mm]a_{n}.[/mm]
> Hinweis: Betrachten Sie die Dominosteine am rechten Ende
> des Feldes.
> Wie bestimme ich eine soclche Rekursion?
Hallo,
zunächst - vor irgendwelchen Rekursionen - ist es wichtig, daß Du verstehst, was Du tun sollst, worum es geht.
Um Pflasterungen.
Was soll nun gepflastert werden? ein Weg, welcher zwei Einheiten breit und n Einheiten lang ist.
Womit soll gepflastert werden? Es stehen Steine zur Verfügung, die das Maß 2E x 1E haben, wie die erwähnten Dominosteine. (Die Steine sollen beim Pflasterungsprozeß nicht zerteilt werden, was die Anzahl der möglichen Pflasterungen glücklicherweise einschränkt.
Wenn Du Dir nun Kästchenpapier nimmst, ein Feld, welches 2 Kästchen breit ist und z.B. 15 Kästchen lang markierst, und dieses mit 1x2 "Steinchen" ausfüllst, hast Du eine Pflasterung gefunden für ein Feld der Länge 15. Die Frage ist: wieviele verschiedene Pflasterungen gibt es?
Wieviele Möglichkeiten habe ich für einen Weg der Länge n?
Wenn die Aufgabe klar geworden ist, kann's losgehen:
[mm] \underline{n=1}: [/mm] das zu pflasternde Feld ist ein 1x2 Feld.
Hier hat man natürlich nur eine Möglichkeit, seinen Stein hinzulegen.
[mm] \underline{n=2}: [/mm] das zu pflasternde Feld ist ein 2x2 Feld.
Hier kannst Du zwei Steine nebeneinander "hochkant" oder "quer" verlegen, also gibt's 2 Möglichkeiten.
[mm] \underline{n=3}: [/mm] das zu pflasternde Feld ist ein 3x2 Feld.
Nun kann der Tip zum Tragen kommen. Entweder liegt am rechten Rand ein Stein hochkant. Dann bleibt ein 2x2 Feld auszufüllen, die Anzahl der Möglichkeiten hierfür kennst Du bereits.
Oder es liegen am rechten Rand 2 Steine "quer". Es bleibt ein 1x2 Feld, die Anzahl der Möglichkeiten kennst Du.
Insgesamt: ...+...=... Möglichkeiten.
[mm] \underline{n=4}: [/mm] das zu pflasternde Feld ist ein 1x4 Feld.
Entweder liegt am rechten Rand ein Stein hochkant. Dann bleibt ein 3x2 Feld auszufüllen, die Anzahl der Möglichkeiten hierfür kennst Du bereits.
Oder es liegen am rechten Rand 2 Steine "quer". Es bleibt ...
usw.
Sicher weißt Du bald, wie der Hase läuft, wie man die Anzahl der Möglichkeiten für ein 2xn Feld findet.
Die entsprechende Formel ist dann natürlich noch zu beweisen. (Das geht per Induktion wie oben für den Fall n=4 angedeutet.)
Gruß v. Angela
|
|
|
|
