Invarianten Beweis: Fibonacci < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:19 Di 27.08.2013 | | Autor: | Hezz09 |
| Aufgabe | Aufgabe 4 (Invarianten)
Die Folge F(n); n [mm] \in \IN [/mm] der Fibonaccizahlen ist folgendermaen de niert:
F(0) := 0
F(1) := 1
F(n) := F(n - 1) + F(n - 2)
Die Folge beginnt also mit 0; 1; 1; 2; 3; 5; 8; : : : .
Zeigen Sie mit vollstandiger Induktion, dass das folgende Programm fur n [mm] \in \IN [/mm] die n-te
Fibonaccizahl berechnet.
1 public static int fibonacci ( int n){
2 int a = 0 ;
3 int b = 1 ;
4 for ( int i =1; i <= n ; ++i ){
5 int t = b ;
6 b = a + b ;
7 a = t ;
8 }
9 return a ;
10 }
Hinweis. Zeigen Sie fur alle i [mm] \in \IN [/mm] : Vor der i-ten Iteration der for-Schleife hat die
Variablen a den Wert F(i - 1) und die Variable b hat den Wert F(i). Folgern Sie dann
aus dieser Aussage die Korrektheit des Programmes. |
Guten Tag allerseits,
ich beschäftige mich mit der obigen Aufgabe und habe auch schon meinen eigenen Lösungsweg zurechtgestellt. Nur bin ich mir unsicher ob ich dies so zeigen kann oder ob meine Begründung fehlerhaft oder lückenhaft ist.
Vor der i-ten Iteration ist a = F(i-1) und b = F(i).
Induktionsanfang für i = 2:
Wie wir oben im Programm sehen, haben wir bei i = 2 genau einen Schleifendurchlauf. Somit ist:
t = 1
b = 1 [mm] \gdw [/mm] F(2) := F(1) + F(0) [mm] \Rightarrow [/mm] Richtig.
a = 1 [mm] \gdw [/mm] F(1) (Laut obiger Definition ebenso richtig).
Nun müssen wir von i auf i + 1 schließen, damit wir zeigen, dass das Programm invariant ist und für alle i [mm] \in \IN [/mm] gilt.
Induktionsschritt :
Vor dem i+1 -ten Schleifendurchlauf haben wir also i Schleifendurchläufe.
Somit muss gelten:
a = F(i+1-1) = F(i) := F(i-1)+F(i-2) (Habe jetzt von der obigen Definition n durch i ausgetauscht)
b = F(i+1) := F(i) + F(i-1) [mm] \gdw [/mm] b + a
Wenn ihr eine genauere Beschreibung wollt wie genau ich dadrauf gekommen bin, so meldet es bitte. Ich würde gerne anfangs nur wissen,
ob man das so machen kann oder eher nicht?
Viele Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und (etwas verspätet leider)
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Die Folge F(n); n [mm]\in \IN[/mm] der Fibonaccizahlen ist
> folgendermaen de niert:
> F(0) := 0
> F(1) := 1
> F(n) := F(n - 1) + F(n - 2)
> Die Folge beginnt also mit 0; 1; 1; 2; 3; 5; 8; : : : .
> Zeigen Sie mit vollstandiger Induktion, dass das folgende
> Programm fur n [mm]\in \IN[/mm] die n-te
> Fibonaccizahl berechnet.
> 1 public static int fibonacci ( int n){
> 2 int a = 0 ;
> 3 int b = 1 ;
> 4 for ( int i =1; i <= n ; ++i ){
> 5 int t = b ;
> 6 b = a + b ;
> 7 a = t ;
> 8 }
> 9 return a ;
> 10 }
> Hinweis. Zeigen Sie fur alle i [mm]\in \IN[/mm] : Vor der i-ten
> Iteration der for-Schleife hat die
> Variablen a den Wert F(i - 1) und die Variable b hat den
> Wert F(i). Folgern Sie dann
> aus dieser Aussage die Korrektheit des Programmes.
> Guten Tag allerseits,
>
> ich beschäftige mich mit der obigen Aufgabe und habe auch
> schon meinen eigenen Lösungsweg zurechtgestellt. Nur bin
> ich mir unsicher ob ich dies so zeigen kann oder ob meine
> Begründung fehlerhaft oder lückenhaft ist.
>
> Vor der i-ten Iteration ist a = F(i-1) und b = F(i).
>
> Induktionsanfang für i = 2:
>
> Wie wir oben im Programm sehen, haben wir bei i = 2 genau
> einen Schleifendurchlauf. Somit ist:
> t = 1
> b = 1 [mm]\gdw[/mm] F(2) := F(1) + F(0) [mm]\Rightarrow[/mm] Richtig.
> a = 1 [mm]\gdw[/mm] F(1) (Laut obiger Definition ebenso richtig).
>
> Nun müssen wir von i auf i + 1 schließen, damit wir
> zeigen, dass das Programm invariant ist und für alle i [mm]\in \IN[/mm]
> gilt.
> Induktionsschritt :
> Vor dem i+1 -ten Schleifendurchlauf haben wir also i
> Schleifendurchläufe.
> Somit muss gelten:
> a = F(i+1-1) = F(i) := F(i-1)+F(i-2) (Habe jetzt von der
> obigen Definition n durch i ausgetauscht)
> b = F(i+1) := F(i) + F(i-1) [mm]\gdw[/mm] b + a
>
> Wenn ihr eine genauere Beschreibung wollt wie genau ich
> dadrauf gekommen bin, so meldet es bitte. Ich würde gerne
> anfangs nur wissen,
> ob man das so machen kann oder eher nicht?
Das ist ja eigentlich alles total einfach, wenn man sich anschaut, was der Programmcode tut. Und vermutlich hast du auch das richtige im Sionn gehabt, nur die Notation ist verbesserungswürdig.
Als erstes würde ich den Induktionsanfang mit dem Schleifenanfang gleich setzen und mit i=1 beginnen. Beim Induktionsschluss musst du einfach beim Aufschreiben diener Gedanken darauf achten, dass eine Variable wie b nicht gleichzeitig in zwei Schleifendurchläufen (oder auch nur vor und nach ihrer Zuweisung) betrachtet werden darf.
Verbal könnte man das einfach so begründen:
- Zu Beginn der Schleife i+1 ist a nach Voraussetzung F(i) und b ist gleich F(i+1). Jetzt wird zu b F(i) addierst und das ergibt eben gerade F(i+2). Dann wird F(i+1) ausgegeben und i inkrementiert, so dass beim nächsten Durchlauf zwangsläufig nach dem gleichen Muster F(i+2) ausgeben wird.
Gruß, Diophant
|
|
|
|
