Rekursion bestimmen |
09.05.2019, 11:35 | Peter430 | Auf diesen Beitrag antworten » |
Rekursion bestimmen Aus n Zahlen ziehe ich i-mal eine 0. Die nicht gezogenen Zahlen sind 1. Bekanntermaßen ist die Anzahl der Möglichkeiten dafür (n + 1 - i) über i. Und wenn ich über alle i summiere erhalte ich die Anzahl a_n der möglichen 0-1 Zahlenfolgen der Länge n ohne Doppelnull. Damit erhalte ich: a_1 = 1 + 1 = 2 a_2 = 1 + 2 = 3 a_3 = 1 + 3 + 1 = 5 a_4 = 1 + 4 + 3 = 8 a_5 = 1 + 5 + 6 + 1 = 13 a_6 = 1 + 6 + 10 + 4 = 21 a_7 = 1 + 7 + 15 + 10 +1 = 34 Das sieht mir sehr nach den Fibonacci Zahlen aus. Natürlich könnte man das mit Induktion beweisen. Aber kann man sich das denn nicht auch irgenwie veranschaulichen ? Wenn ich die Länge der 0-1 Zahlenfolgen um 1 erhöhe, warum wird dann gerade die Anzahl der beiden Vorgänger aufaddiert ? |
||
09.05.2019, 19:27 | HAL 9000 | Auf diesen Beitrag antworten » |
Man kann sich leicht inhaltlich überlegen, warum die Fibonacci-Rekursion hier gilt. Mach bei den -stelligen Zahlen die Fallunterscheidung nach der letzten Ziffer: a) Ist diese eine 1, dann gibt es für die Ziffern davor nur die Einschränkung, dass keine zwei Nullen hintereinander vorkommen dürfen. Die Anzahl solcher -stelligen Zahlen ist ja nun gerade , und an jeder dieser Zahlen hängen wir Ziffer 1 dran. b) Ist diese eine 0, dann darf die vorletzte Ziffer keine 0 sein, d.h., die Zahl muss auf 10 enden. Für die Ziffern davor gibt es wieder nur die Einschränkung, dass keine zwei Nullen hintereinander vorkommen dürfen. Die Anzahl solcher -stelligen Zahlen ist , und an jede dieser Zahlen hängen wir die zwei Ziffern 10 dran. Macht summa summarum . Fehlen noch die Anfangswerte (0/1) und (01/10/11), schon haben wir die verschobene Fibonaccifolge . |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|