Algorithmus zur Berechnung der Fibonaccizahlen - Beweis durch vollständige Induktion

14.04.2013, 18:02

onMyWay

Algorithmus zur Berechnung der Fibonaccizahlen - Beweis durch vollständige Induktion

Hallo,
ich habe eine Frage zur der sich im Anhang befindenden Aufgabe.

Es wird Folgendes gefragt: "Zeigen Sie mit vollständiger Induktion, dass das folgende Programm für n Element N ( inkl. 0 ) die n-te Fibonaccizahl berechnet."

Ich bin leider recht schlecht, wenn es darum geht etwas zu beweisen, aber ich bin hier der Meinung, dass das Programm nicht für alle Zahlen die Berechnung durchführt.

Es wird gesagt, dass n ein Element aus den natürlichen Zahlen ist inklusive der Null!

Das Programm ist nun so geschrieben, dass der Schleifenindex i=1 ist und die Bedingung i <= n. Wenn ich nun für n=0 einsetze, so wird die Rechenschleife überhaupt nicht gestartet.

Nun wird in der Aufgabe jedoch der Stichpunkt "Invarianten" genannt. Laut Wikipedia bedeutet es in der Informatik Folgendes:

"Eine Invariante ist eine Aussage, die über die Ausführung bestimmter Programmbefehle hinweg gilt. Sie ist also vor und nach diesen Befehlen wahr, sie ist demnach nicht veränderlich, also invariant."

Quellen: http://de.wikipedia.org/wiki/Invariante_(Informatik)

Heißt das nun, dass ich den Schleifenbefehl / Schleifenbedingung überhaupt nicht beachten muss, sondern nur den Teil innerhalb der Schleife, der wirklich für die Berechnung der Fibonaccizahlen verantwortlich ist?

Wäre sehr nett, wenn sich jemand dazu äußern könnte, ob ich überhaupt auf dem richtigen Weg bin.

EDIT: Link

14.04.2013, 20:57

Auf diesen Beitrag antworten »

Airblader

Wenn du

setzt, dann heißt das, dass du [l]F(0)[/l] berechnen willst – also die 0-te Fibonacci-Zahl. Was das für eine Zahl ist steht schon in der Definition der Fibonacci-Zahlen: [latex]F(0) := 0[/latex]

.

Werfen wir also [latex]n = 0[/latex]

in das Programm. Wie du korrekt bemerkt hast, wird die Schleife gar nicht erst ausgeführt. Aber das tut ja nicht weh, das Programm gibt ja trotzdem etwas aus – und zwar 0. Also alles in Ordnung!
Von dem Begriff "Invariante" kann ich in der Aufgabenstellung nichts sehen.

Ist dir denn klar, wie eine vollständige Induktion prinzipiell funktioniert? Falls nein, jetzt nachlesen gehen. Bevor man eine Methode nicht versteht, kann man sie auch nicht anwenden.
Der erste Schritt einer vollständigen Induktion ist immer der Induktionsanfang. Den haben wir oben ja nun sozusagen gemacht, indem wir die Aussage für [latex]n = 0[/latex]

verifiziert haben. Kommen wir also zum Induktionsschritt, d.h. wir nehmen an, dass die Aussage für alle Werte kleiner oder gleich $[latex]n \in \mathbb N_0[/latex]$ gilt. Zeigen müssen wir nun, dass dann fibonacci(n+1) die (n+1)-te Fibonacci-Zahl berechnet.

Wir setzen also [latex]n+1[/latex]

in unser Programm ein. Jetzt nutzen wir einen kleinen Trick. Die Schleife

code:
1: 2: 3: 4: 5:	for( int i = 1; i <= n+1; i++ ) { int t = b; b = a+b; a = t; }

lässt sich umschreiben zu

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	for( int i = 1; i <= n; i++ ) { int t = b; b = a+b; a = t; } int t = b; b = a+b; a = t;

Jetzt darfst du erstmal weiterdenken.

Neue Frage »

Antworten »

Algorithmus zur Berechnung der Fibonaccizahlen - Beweis durch vollständige Induktion

Verwandte Themen