Kombinatorik Frosch |
| 21.04.2012, 10:21 | MatheMathosi | Auf diesen Beitrag antworten » | ||
| Kombinatorik Frosch The frog Leo wants to advance on a strip of paper which is numbered by 1,2,3,...,n. He can do that by either jumping two spaces or just one space. How many different ways of getting to the field with number n does he have, if he starts on the field with the number 1 ? Meine Ideen: Die Frage bitte auf deutsch beantworten =). Wenn ich mir dies für n=2,3,4,5 ansehe sind die jeweiligen Möglichkeiten gerade die Folgenglieder der Fibonaccifolge Also für n=2 1 Möglichkeit, für n=3 2 Möglichkeiten, für n=4 3 Möglichkeiten usw. Wie ich hier aber allgemein die Möglichkeiten bestimme ist mir nicht ganz klar. Für eure Hilfe schonmal Danke im Voraus ! |
||||
| 21.04.2012, 19:13 | Huggy | Auf diesen Beitrag antworten » | ||
| RE: Kombinatorik Frosch Deine Zahlen stimmen nicht, Richtig ist: n = 1: 1: 1 Möglichkeit n = 2: 1-1, 2: 2 Möglichkeiten n = 3: 1-1-1, 1-2, 2-1: 3 Möglichkeiten usw. Das ergibt auch die Fibonacci-Folge. Der Beweis ist einfach. Sei f(n) die Zahl der Möglichkeiten, zum Punkt n zu springen. Dann kann für n >= 2 der letzte Sprung ein 2-Sprung oder ein 1-Sprung sein. Bei einem 2-Sprung kommt man vom Punkt n - 2 und bis dahin gibt es f(n - 2) Möglichkeiten. Bei einem 1-Sprung kommt man vom Punkt n - 1 und bis dahin waren es f(n - 1) Möglichkeiten. Also: Das ist die Rekursionsformel der Fibonacci-Folge. |
||||
| 21.04.2012, 21:58 | Fragen über Fragen | Auf diesen Beitrag antworten » | ||
RE: Kombinatorik Frosch
Aber der Frosch startet bei 1, also muss er z. B. um zur 2 zu kommen einen Einersprung machen (eine Möglichkeit). Also eine verschobene Fibonacci-Folge. |
||||
| 22.04.2012, 08:47 | Huggy | Auf diesen Beitrag antworten » | ||
| RE: Kombinatorik Frosch Stimmt, wenn der Frosch zu Beginn schon auf Feld 1 steht. Ordentliche Frösche hüpfen vom Feld START auf Feld 1 oder 2. 
Wie auch immer, der Beweis für die Rekursionsgleichung gilt in beiden Fällen. |
||||
| 22.04.2012, 12:05 | MatheMathosi | Auf diesen Beitrag antworten » | ||
Danke für eure Antworten. So ähnlich hatte ich mir das auch schoin überlegt. Wenn man nun davon ausgeht, dass der Frosch auf Feld 1 startet und für n=1 die Möglichkeit 1 gesetzt wird (einzige Möglichkeit er bleibt einfach stehen). Liegt ja die Fibonaccifolge vor mit wobei Muss das jetzt noch bewiesen werden oder würdet ihr sagen die Aufgabe ist so korrekt ? z.B. durch Induktion oder so... |
||||
| 22.04.2012, 13:41 | Huggy | Auf diesen Beitrag antworten » | ||
Wenn der Frosch auf dem Feld 1 startet, beginnt die Gültigkeit der Rekursion mit n = 3, denn erst zu dem Feld 3 kann er dann wahlweise einen 1-Sprung oder einen 2-Sprung machen. Wenn die Rekursionsformel bewiesen wurde und die Anfangswerte bestimmt sind, ist alles gezeigt. |
||||
| Anzeige | ||||
|
|
||||
| 22.04.2012, 14:35 | MatheMathosi | Auf diesen Beitrag antworten » | ||
Ok klingt einleuchtend. Ich fange also bei n=3 an. Anfangswerte sind ja auch schon bestimmt. Wie beweise ich aber die Rekursionsformel ? Oder haben wir das hier schon getan ? |
||||
| 22.04.2012, 14:41 | Huggy | Auf diesen Beitrag antworten » | ||
Wir nicht!
Aber ich habe sie oben bewiesen. |
||||
| 22.04.2012, 15:48 | MatheMathosi | Auf diesen Beitrag antworten » | ||
Ok akzeptiert ! Dann mal vielen Dank |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
Wichtig: