Fibonacci-Zahlen (iterativ)

[Piwi]

Hallo Delphi-Gemeinde,

ich habe in diesem Programmtext irgend einen Denkfehler drin, der mir nicht auffallen will. Es geht darum, die Fibonacci-Zahl an der Stelle n in der Fibonacci-Reihe darzustellen.

Fibonacci-Zahlen

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Die nächste Zahl in der Reihe ergibt sich also immer aus der Summe seiner beiden Vorgänger. Rekursiv ist das ganze relativ einfach darzustellen, iterativ wohl auch, aber dort ist ein Denkfehler in meinem Programmtext:

Delphi-Quellcode:

function TForm1.fibonit(n:integer):integer;
var x,y,z,i:integer;
begin
 x:=1;
 y:=1;
 i:=0;
 repeat
 i:=i+1;
 z:=x+y;
 y:=x;
 x:=z;
 until i=(n-1);
end;


procedure TForm1.iterativbuttonClick(Sender: TObject);
var n:integer;
begin
n:=strtoint(edit1.text);
listbox1.items.add(inttostr(fibonit(n)));
end;

Er trägt in die Listbox nach ca. zehnsekündiger Berechnungsphase (!!) eine relativ hohe Zahl ein, selbst wenn ich n=1 wähle. Wo ist der Fehlerteufel? :angle:

DANKE IM VORAUS! :spin:

[Kamil]

Bei der Fuktion Fehlt ein Ergebnis (result:=x)

Entweder so:

Delphi-Quellcode:

procedure TForm1.fibonit(n:integer);
var
  x,y,z,i:integer;
begin 
  x:=1;
  y:=1;
  listbox1.items.add(inttostr(x));
  listbox1.items.add(inttostr(y));
  i:=0;
  repeat
    i:=i+1;
    z:=x+y;
    listbox1.items.add(inttostr(z));
    y:=x;
    x:=z;
  until i=(n-1);
end; 

procedure TForm1.Button1Click(Sender: TObject);
var
  n: integer;
begin 
  n:=strtoint(edit1.text);
  fibonit(n);
end;

oder so:

Delphi-Quellcode:

function TForm1.fibonit(n:integer): integer;
var
  x,y,z,i:integer;
begin 
  x:=1;
  y:=1;
  i:=0;
  repeat
    i:=i+1;
    z:=x+y;
    y:=x;
    x:=z;
  until i=(n-1);
  result:=z;
end; 

procedure TForm1.Button1Click(Sender: TObject);
var
  n: integer;
begin 
  n:=strtoint(edit1.text);
  listbox1.items.add(inttostr(fibonit(n)));
end;

[sharkx]

Zitat:

Zitat von Kamil

Bei der Fuktion Fehlt ein Ergebnis (result:=x)

Entweder so:

Delphi-Quellcode:

procedure TForm1.fibonit(n:integer);
var
  x,y,z,i:integer;
begin 
  x:=1;
  y:=1;
  listbox1.items.add(inttostr(x));
  listbox1.items.add(inttostr(y));
  i:=0;
  repeat
    i:=i+1;
    z:=x+y;
    listbox1.items.add(inttostr(z));
    y:=x;
    x:=z;
  until i=(n-1);
end; 

procedure TForm1.Button1Click(Sender: TObject);
var
  n: integer;
begin 
  n:=strtoint(edit1.text);
  fibonit(n);
end;

oder so:

Delphi-Quellcode:

function TForm1.fibonit(n:integer): integer;
var
  x,y,z,i:integer;
begin 
  x:=1;
  y:=1;
  i:=0;
  repeat
    i:=i+1;
    z:=x+y;
    y:=x;
    x:=z;
  until i=(n-1);
  result:=z;
end; 

procedure TForm1.Button1Click(Sender: TObject);
var
  n: integer;
begin 
  n:=strtoint(edit1.text);
  listbox1.items.add(inttostr(fibonit(n)));
end;

Delphi-Quellcode:

    
    y:=x;
    x:=z;

Wozu? Warum nich gleich y := z; ?

[Kamil]

Zitat:

Zitat von sharkx

Delphi-Quellcode:

    
    y:=x;
    x:=z;

Wozu? Warum nich gleich y := z; ?

Weil Fibonacci Zahlen aus den zwei vorherigen Zahlen gebildet werden:

Fib(1)=1
Fib(2)=1
Fib(x)=Fib(x-1)+Fib(x-2)

[himitsu]

Ein Hallöle von http://www.FrankNStein.de/Smiley-Wolke.gif,

Mit freuntlichen Grüßen von Daniel B und mir:
Fibonacci

http://www.delphipraxis.net/images/common/divider.jpg
http://www.FrankNStein.de/Smiley-Kuss.gif * * http://www.FrankNStein.de/Smiley-Spinne.gif * * * http://www.FrankNStein.de/Smiley-Winken.gif

[MCeddy]

Hi Piwi. So eine Aufgabe mit Fibonzahlen hatte ich gestern in meiner Info-Klausur auch drann gehabt. Ich hab das Problem dort mit einem Array gelöst. Hier der Code für Turbo Pascal:

Delphi-Quellcode:

program Fibonacci_Zahlen;

uses
  crt;

const
  MAX = 25;

var
  zahlen : array[0..MAX] of longint;
  i      : integer;

begin
  zahlen[0] := 0;
  zahlen[1] := 1;
  for i := 2 to MAX do
    zahlen[i] := zahlen[i-1] + zahlen[i-2];
  for i := 0 to MAX do
    writeln('fibo(', i, ') = ', zahlen[i]);
  readln;
end.

viele Grüße

MCeddy02
:cheers:

[sharkx]

Zitat:

Zitat von Kamil

Zitat:

Zitat von sharkx

Delphi-Quellcode:

    
    y:=x;
    x:=z;

Wozu? Warum nich gleich y := z; ?

Weil Fibonacci Zahlen aus den zwei vorherigen Zahlen gebildet werden:

Fib(1)=1
Fib(2)=1
Fib(x)=Fib(x-1)+Fib(x-2)

Ja aber du tust doch nach dem oberen Code einfach die Variablen bzw deren Result an eine andere Weitergeben. y :=x; x := z; .. Da passiert doch nichts mehr mit addieren, multiplizieren oder sonstwas.

[Chewie]

Wenn du genau hinsiehst, wirst du sehen, dass x zu Beginn der Schleife wieder gelesen wird.

[MCeddy]

Hi ich bin's nochmal. Habe jetzt mal als meiner Lösung eine Funktion zusammen gebastelt bei der die Fibonacci-Zahlen an der stelle n mit Hilfe von einem Array erzeugt werden können:

Delphi-Quellcode:

function  fibonacci(n : byte) : longint;
const
  MAX = 40;
var
  zahlen : array[0..MAX] of longint;
  i      : integer;
begin
  zahlen[0] := 0;
  zahlen[1] := 1;
  for i := 2 to n do
    zahlen[i] := zahlen[i-1] + zahlen[i-2];
  result := zahlen[n];
end;

tschau und noch ein schönes Wochenende allen DP-Usern :zwinker:

MCeddy02
:cat:

[himitsu]

http://www.FrankNStein.de/Smiley-Wolke.gif Hallöle,

hier mal eine Version ohne Array und mit Fehlerbehandlung.

Liefert die Fibonacci-Zahlen im Bereich von 0 bis 92 (0 bis 7540113804746346429).

Delphi-Quellcode:

Function Fibonacci(N: Byte): Int64;
  Var I1, I2, Ix: Int64;
    I: Integer;

  Begin
    I1 := 0;
    I2 := 1;
    For I := 1 to N do Begin
      Ix := I1;
      I1 := I2;
      I2 := Ix + I2;
    End;
    If N <= 1 Then Result := N
    Else If N <= 92 Then Result := I1
    Else Result := -1; {Fehler}
  End;

http://www.delphipraxis.net/images/common/divider.jpg
http://www.FrankNStein.de/Smiley-Kuss.gif * * http://www.FrankNStein.de/Smiley-Spinne.gif * * * http://www.FrankNStein.de/Smiley-Winken.gif

[Illuminator-23-5]

fibonacci geht meiner meinung so am einfachsten:

Delphi-Quellcode:

var
  alt, uralt, neu, i: integer;
begin
  alt := 0;
  neu := 1;
  for i := 2 to j do begin
    uralt := alt;
    alt := neu;
    neu := uralt + alt;
  end;
  return neu;

und das am schnellsten:

Delphi-Quellcode:

var
  a, b, c, d, n, r: integer;
begin
  n := StrToInt(Edit1.Text);
  asm
    MOV a, EAX
    MOV b, EBX
    MOV c, ECX
    MOV d, EDX

    MOV EDX, n
    SUB EDX, 1
    MOV EAX, 0  //alt
    MOV EBX, 1  //neu
    JZ @@end
    @@1:
    MOV ECX, EAX
    MOV EAX, EBX
    MOV EBX, EAX
    ADD EBX, ECX
    SUB EDX, 1
    CMP EDX, 1
    JAE @@1
    @@end:
    MOV r, EBX

    MOV EAX, a
    MOV EBX, b
    MOV ECX, c
    MOV EDX, d
  end;
  return r;

[Freekill]

Zitat:

Zitat von Piwi

Hallo Delphi-Gemeinde,

ich habe in diesem Programmtext irgend einen Denkfehler drin, der mir nicht auffallen will. Es geht darum, die Fibonacci-Zahl an der Stelle n in der Fibonacci-Reihe darzustellen.

Fibonacci-Zahlen

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Die nächste Zahl in der Reihe ergibt sich also immer aus der Summe seiner beiden Vorgänger. Rekursiv ist das ganze relativ einfach darzustellen, iterativ wohl auch, aber dort ist ein Denkfehler in meinem Programmtext:

Delphi-Quellcode:

function TForm1.fibonit(n:integer):integer;
var x,y,z,i:integer;
begin
 x:=1;
 y:=1;
 i:=0;
 repeat
 i:=i+1;
 z:=x+y;
 y:=x;
 x:=z;
 until i=(n-1);
end;


procedure TForm1.iterativbuttonClick(Sender: TObject);
var n:integer;
begin
n:=strtoint(edit1.text);
listbox1.items.add(inttostr(fibonit(n)));
end;

Er trägt in die Listbox nach ca. zehnsekündiger Berechnungsphase (!!) eine relativ hohe Zahl ein, selbst wenn ich n=1 wähle. Wo ist der Fehlerteufel? :angle:

DANKE IM VORAUS! :spin:

Auch wenn der letzte Beitrag hier schon eine ganze Weile her ist, wage ich es den Quelltext für zukünftige Besucher zu korrigieren. Die Abbruchbedingung für die Repeat-Schleife stimmt nicht ganz. Ich musste im Rahmen des Informatiksunterricht selbst die Fibonaccizahlen Iterativ programmieren. Dabei ist mir bei dieser Variante aufgefallen, dass die Abbruchbedingung nicht "until i=(n-1)" sondern "until i=(n-2)" heißen muss. Ansonsten verschieben sich die Zahlen um eine Stelle nach vorn und die Reihe stimmt nicht mehr.

[pstruh]

Hallo :?:
erstaunlich, dass überhaupt ein Ergebnis kommt. Wo wird denn das Funktionsergebnis zugewiesen???
Gruß

[patti]

Es gibt übrigens auch eine Funktion zum Berechnen der Fibonacci-Zahlen:

Im Anhang die Formel als JPG-Bild!

Damit sollte sich das Problem vielleicht auch hinkriegen lassen!

P@Tti

EDIT 1: Okay, der erste Beitrag ist von 2003...
EDIT 2: @pstruh: Das wird wahrscheinlich der Grund sein, warum er immer ne hohe Zahl als Ergebnis bekommen hat, selbst bei n=1

[negaH]

schau mal hier

http://www.delphipraxis.net/internal...ct.php?t=51660
http://www.delphipraxis.net/internal...ight=fibonacci

Gruß Hagen