matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikRekursion
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Diskrete Mathematik" - Rekursion
Rekursion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Rekursion: Antwort
Status: (Antwort) fertig Status 
Datum: 14:12 Fr 20.04.2007
Autor: angela.h.b.


> 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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]