Vielleicht war die Frage etwas seltsam gestellt, aber andererseits sind einige Personen bei exakt dieser Fragestellung auf das gekommen, auf das ich hinaus wollte. DFYX Lösung ist in sofern elegant, als das sie nur korrekte Wege zählt (wobei 'fyx nochmal genau lesen sollte und seine Formel insofern modifizieren sollte, das weder A noch B Felder sind ()), was zumindest schon mal eine Verbesserung ist, aber aufgrund der wundervollen Einfachheit der Mathematik hätte man auch auf eine andere, viel bezauberndere Lösung kommen können die sich aus der Äquivalenz der reinen Summenbildung und der Konstruktionsvorschrift der Fibonacci-Folge (Siehe hier) ergibt. Rechnet man einfach die Summe aus, so kommt man auf 17.711 Wege, welche der Frosch einschlagen kann - und welche Zahl findet sich an der Stelle F(20+2)? Genau, ebenfalls 17.711.
Um das ganze mal bildlich und nicht mit Formeln zu erklären:
Restriktion: Keine: Der Frosch darf beliebig springen.
Wenn der Frosch keine Restriktionen hat, dann ergibt sich - wie hoffentlich wirklich jedem klar ist, die Folge 2,4,8,16: 2^n.
Restriktion: Nur jedes 2. Feld darf berührt werden.
0 Felder:
A B
Der Frosch hat einen Weg. (A,B)
1 Feld:
A [ ] B
A [x] B
Der Frosch hat exakt zwei Wege, (A,B & A,1,B)
2 Felder:
A [ ] [ ] B
A [x] [ ] B
A [ ] [x] B
Der Frosch hat exakt drei Wege (A,B & A,1,B & A,2,B)
3 Felder:
A [ ] [ ] [ ] B
A [x] [ ] [x] B
A [x] [ ] [ ] B
A [ ] [x] [ ] B
A [ ] [ ] [x] B
Der Frosch hat exakt fünf Wege (A,B & A,1,3,B & A,1,B & A,2,B & A,3,B)
4 Felder:
A [ ] [ ] [ ] [ ] B
A [x] [ ] [ ] [ ] B
A [x] [ ] [x] [ ] B
A [x] [ ] [ ] [x] B
A [ ] [x] [ ] [x] B
A [ ] [x] [ ] [ ] B
A [ ] [ ] [x] [ ] B
A [ ] [ ] [ ] [x] B
Der Frosch hat exakt acht Wege (...)
5 Felder:
A [ ] [ ] [ ] [ ] [ ] B
A [x] [ ] [ ] [ ] [ ] B
A [ ] [x] [ ] [ ] [ ] B
A [ ] [ ] [x] [ ] [ ] B
A [ ] [ ] [ ] [x] [ ] B
A [ ] [ ] [ ] [ ] [x] B
A [x] [ ] [x] [ ] [x] B
A [x] [ ] [x] [ ] [ ] B
A [x] [ ] [ ] [x] [ ] B
A [x] [ ] [ ] [ ] [x] B
A [ ] [x] [ ] [ ] [ ] B
A [ ] [ ] [ ] [x] [ ] B
A [ ] [ ] [x] [ ] [x] B
Der Frosch hat exakt dreizehn Wege
Wie man sieht, etabliert sich die Fibonacci-Folge - und wie ebenfalls offensichtlich sein dürfte verändert sich dies, ändern wir den Parameter der zu überspringenden Felder. Nehmen wir an, dass der Frosch immer über mindestens zwei Felder springen muss, dann erhält man die Folge 2,3,4,6,9,13,..., bei der man nicht die beiden vorherigen Nummern addiert, sondern jeweils n-1 und n-3 addiert. Bei drei Feldern ergibt sich folgerichtig 2,3,4,5,7,10,14, also n-1 + n-4. Man setze beliebig fort. :-)
mirabile dictu!
Wenn Malu möchte, er war der erste, der drauf kam, ansonsten, freie Runde.
Zitieren