Diskussion:Fibonacci-Folge

Programmierung

Es gibt 3 mir bekannte Prinzipien, um die Fibonacci-Zahlen zu berechnen:

1. rekursiv in quadratischer Laufzeit
2. iterativ in linearer Laufzeit
3. direkt in konstanter Laufzeit

Für die ersten beiden könnte ich ein Java-Programm schreiben, für die dritte die Formel TeXen. Ist Java OK? Die Programmiersprache, die hier benutzt wurde, kenne ich nicht, und Pseudocode finde ich furchtbar. --Head 00:15, 5. Sep 2003 (CEST)

Wenn's nach mir geht, können wir den Basic-Dialekt gerne in Java umschreiben. Eine Referenzimplementierung in Java zu 2. gibt's auf meiner Homepage (www.jonelo.de/java/bigal_de.html). Sourcecode ist im jar ;-) Jonelo 12:59, 5. Sep 2003 (CEST)

Die verwendete Programmiersprache ist QBasic (oder Basic - kA), ist eigentlich bekannt, aber hoffnungslos veraltet. floklk

Noch 'ne Meinung: Da Java ein Produkt und keine Programmiersprache ist, ist Pseudocode hier viel besser angebracht. Der Artikel sieht so einfach nur scheusslich aus, mit je einem Beispiel aus Python, Java und Pseudocode. Der Nächste kommt dann wohl mit VisualBasic, .NET, Cobol, Haskell, Lisp, Brainfuck, Dolog, C/C++, Rexx, Perl, Tcl, Delphi, Fortran, XYZ-Assembler, Postscript (Ja, Postscript ist eine Programmiersprache), M4, Redcode, awk oder Gofer an. ---

Nun, um genau zu sein ist Java ein Produkt, ein Trademark und natürlich auch eine Programmiersprache! Da sie in der Regel leicht zu lesen und plattformunabhänig ist, ist es wohl Geschmacksache was mehr Sinn macht: Pseudocode oder Java. Deinem zweiten Argument "zu viel Code im Artikel" stimme ich Dir aber hingegen voll zu. Meiner Meinung nach ist weniger oft mehr und ein ganzes Programm reinpasten ist wirklich overkill. Gibt's da noch andere Meinungen zum Artikel verschlanken/verschönern? Jonelo 22:43, 28. Apr 2004 (CEST)

hallo head, ich denke, du hast es nicht so gemeint, aber es könnte so mißverstanden werden:

1. rekursiv == quadratischer Laufzeit
2. iterativ == linearer Laufzeit

selbstverständlich läßt sich das ganze auch

1. rekursiv UND linear, bzw.
2. iterativ UND quadratisch berechnen.

zur programmiersprache: ich finde pseudocode ok, was ich nicht ok finde, sind 4 verschiedenen programmiersprachen in einem einzelnen artikel ( pseudo, basic, python, java). mfg Wzwz 23:16, 2. Mai 2004 (CEST)

Vier Programme dazu finde ich auch zuviel. Nebenbei ist die "iterative" Berechnung im Java-Programm die explizite Formel von Binet, kein iteratives Auswerten der Rekursionsgleichung. --SirJective 12:56, 5. Mai 2004 (CEST)

Ich finde die Aufführung von 4 verschiedenen Algorithmen per seitenlangem Quellkode in einem WP-Artikel völlig absurd. Wenn niemand protestiert, lösche ich demnächst den Beitrag von Benutzer:Took vom 27.02.04. Es bliebe dann nur das kleine Basicprogramm übrig. Hätte nichts dagegen, das auch zu löschen, muss aber nicht sein. --Wolfgangbeyer 23:24, 7. Jul 2004 (CEST)

Kein Widerspruch? Dann lösche ich das mal. Modifiziere auch mal das Basicprogramm, da es alles andere als schön ist, denn es berechnet pro Durchlauf gleich 2 Zahlen. Wem soll sowas überhaupt was bringen? Wenn jemand auch nur einen Funken von Programmierkenntnissen hat, dann schreibt er so ein Programm auf der Stelle hin (was simpleres gibts ja fast nicht) und wenn er keine hat, dann sagts ihm auch wenig. Aber ok ... --Wolfgangbeyer 10:52, 10. Jul 2004 (CEST)

Zahl / Zahlen

Gibt es einen besonderen Grund, warum der Artikel entgegen der Konventionen einen Pluraleintrag hat? Wenn man sich eine ganz bestimmte Zahl ansieht, die den Kriterien der Zahlen genügt, dann ist es üblich den Begriff in der Einzahl zu verwenden. Stern 00:36, 28. Apr 2004 (CEST)

In diesem Artikel geht es um eine bestimmte Zahlenfolge, deren einzelne Glieder nicht (ohne eine ziemlich willkuerlich aussehende explizite Formel) ohne die anderen Glieder definiert werden koennen. Oder weisst du einen Weg, eine Fibonacci-Zahl zu definieren, ohne alle (kleineren) Fibonacci-Zahlen zu definieren - und zwar ohne die Formel von Binet? Bei Fermat-Zahlen zum Beispiel ist das anders, die sind unabhaengig voneinander als Zahlen einer bestimmten Form definiert. --SirJective 12:56, 5. Mai 2004 (CEST)

Und wenn man den artikel nach Fibonacci-Zahlenfolge verschiebt? --Wiki Wichtel sowie KatEgo 23:38, 7. Jul 2004 (CEST)

Keine schlechte Idee. Ich hätte jedenfalls nichts dagegen. --Wolfgangbeyer 23:19, 9. Jul 2004 (CEST)

So richtig überzeugt mich das nicht, man kann von jeder natürlichen Zahl sagen, ob sie Fibonacci-Zahl ist oder nicht. Und würde ein Suchender (unter Berücksichtgung der Singular-Konvention) denn nicht einen Artikel zur Fibonacci-Zahl suchen (statt Fibonacci-Zahlenfolge) ? --Callimachos 09:30, 10. Jul 2004 (CEST)

Das ist natürlich richtig, aber die Fibonacci-Zahlen werde so gut wie immer in ihrer Gesamtheit betrachtet oder zumindest in Bezug auf ihrer unmittelbaren Nachbarn, anders als z. B. die rationalen Zahlen, wo man sich auch mal dafür interessiert, ob z. B. π eine ist. Einen entsprechenden Redirect bei Fibonacci-Zahl muss es natürlich geben und gibt es auch. Das google-Trefferverhältnis Fibonacci-Zahlen : Fibonacci-Folge : Fibonacci-Zahl : Fibonacci-Zahlenfolge beträgt übrigens ca. 6100:5200:1700:100. Das spricht meiner Ansicht nach eindeutig für Fibonacci-Folge. Ich mach' das jetzt einfach mal. --Wolfgangbeyer 10:25, 10. Jul 2004 (CEST)

Seltsam: Die Verschiebe-Operation hat nicht funktioniert. Ich dachte, das geht auch dann wenn dort schon ein Redirect steht. Selbst das löschen des Redirects hat nichts genützt. Schade, denn nun steht die ganze Versionsgeschichte unter Fibonacci-Zahlen. --Wolfgangbeyer 10:47, 10. Jul 2004 (CEST)

Programm-Quellcodes

Ich bin durchaus ein Freund von Quellcodes, aber müssen es denn die Quellcodes von drei verschiedenen Programmiersprachen sein? Ich kann auch noch LOGO, Lisp, REXX, tcl und AWK beitragen. Im Prinzip sollten zwei Quellcodes reichen, und zwar den rekursiven und einen iterativen Ansatz. Und das am besten in einer neutralen Form, die sich nicht auf eine bestimmte Programiersprache bezieht. --Arbol01 11:26, 17. Aug 2004 (CEST)

Formelversionen

Die Folge würde auch mit f(n) = f(n-1) + f(n-2) funktionieren, dann müsste man allerdings n > 1 festlegen, ist also wohl eher Geschmackssache. Interessanter ist, dass f0 mal mit 0 und mal mit 1 festgelegt wird, so dass man darüber philosophieren könnte, ob die Null eine fibonaccizahl ist oder nicht. Kennt jemand die Primärquelle? -Hati 12:08, 26. Aug 2004 (CEST)

Weitere Zahlenreihen

könnte man die auch erwähnen?

Lucas

Wie Fibonacci (mit f0=f1=1), aber mit f0=1 und f1=3; würde wohl besser zu Kaninchen passen, die ja nicht genau einen Nachkommen haben. -Hati

Padovan

entdeckt 1924 von dem frz. Architekturstudenten Gérard Cordonnier, 1928 vom niederländischen benediktinermönch und Architekten Hans van der Laan: f(n) = f(n-2)+ f(n-3) mit n>3 und f0=f1=f3=1
(auf Kaninchen angewandt, könnte die Verzögerung der Tragzeit entsprechen). -Hati

Chaos

f(n) = f[n - f(n-1)] + f[n-(fn-2)] mit n>1 und f0=f1=1
wäre eine nette Programmier-Übung und liefert Pseudozufallszahlen. -Hati 12:08, 26. Aug 2004 (CEST)

Hm, welches von diesen f's meint denn die Fibonacci-Funktion und welche die Zufallszahlenfunktion? Ist das denn überhaupt beschränkt? Sieht jedenfalls gefährlich aus: Wenn man damit Punkte im Raum würfeln will, könnten die unter Umständen alle auf einer Fläche im Raum liegen. Hatte das Problem mal im Rahmen meiner Physik-Diplomarbeit, als ich per Monte-Carlo-Methode ein vieldimensionales Problem (Integral) lösen wollte. Zum Glück habe ich damals schon (ca. 1976) privat begeistert mit bescheidenen Computergrafiken experimentiert und mich irgendwann über die regelmäßigen Muster gewundert, die man erhält, wenn man viele Rechtecke mit zufälligen Seitenlängen und Mitten würfelt. Als ich dann im Handbuch des verwendeten Basic-Dialekts was von Zufallszahlen auf der Basis von Fibonacci-Zahlen las, war mir alles klar. Hätte schlecht ausgehen können für meine Diplomarbeit ;-). --Wolfgangbeyer 00:26, 5. Sep 2004 (CEST)

Da sind wir wohl nicht mehr bei der Fibonaccio-Funktion sondern bei einer Iterationsanweisung, bei der die Zahl der Rückschritte nochmals eine Rückschrittschleife enthält. Dadurch entsteht eine Zahlenreihe, die einer Zufallsreihe sehr ähnlich ist, aber durch den Algorithmus exakt determiniert ist. Bei exakt gleichem Anfangswert wird also immer die gleiche Zahlenreihe generiert. Eine andere Zahlenreihe entsteht dann, wenn man einen anderen Startwert benutzt. Ob jetzt computer diesen oder einen anderen deterministischen Algorithmus verwenden (Iteration der Zeltfunktion ginge auch aber nicht bei jedem Startwert) weiß ich nicht. Wenn man aber immer eine andere "Zufalls"zahlrenreihe haben will, holt sich der Computer als Startwert die Systemzeit (16stellig?) als Startwert. -Hati 16:27, 5. Sep 2004 (CEST)

Kaninchen

Dem Biologen sträuben sich natürlich die Haare, wenn man mit f0=0 aus dem Nichts ein Kaninchenpaar zaubert. Da wäre f0=1 "biologischer". Für die Programmierer: Das geht noch viel einfacher mit Excel und hat den Vorteil, dass man die Zahlenreihe gleich als Diagramm darstellen kann und sich mit Parametern spielen kann: f(n) = a*f(n-1) + b*f(n-2). Mit Der Veriation von f0 und f1 kommen da die erstaunlichsten Zahlenfolgen mit Gleichgewichtswerten oder Oszillationen heraus, die sich ganz gut zur Modellierung von dynamischen Systemen wie Populationen eignen.
Konsequenterweise muss natürlich ein "geschleichtsreifes" Kaninchenpaar wieder ein Kaninchenpaar hervorbringen. Das ganze ginge übrigens eleganter mit Blattläusen während der sommerzeit, da diese sich ungeschlechtlich fortpflanzen. Da kann man dann tatsächlucb von einer einzigen Blattlaus ausgehen.
-Hati 12:08, 26. Aug 2004 (CEST)

Vorschlag für Kaninchen-Formulierungsänderungen:

1. Zu Beginn gibt es ein Kaninchenpaar. Zu Beginn gibt es ein Kaninchen [Wenn man von Paar spricht, geht man bei Säugetieren von Mänchen und Weibchen aus. Und gebärfahige Männchen ... ;-)]
2. Jedes neugeborene Kaninchen wird nach 2 Monaten entspricht 2 Iterationszyklen) gebärfähig.
3. Jedes gebärfähige Kaninchen [statt -paar] bringt jeden Monat ein weiteres zur Welt.
4. Kaninchen leben ewig.
5. Kaninchen haben einen unbegrenzten Lebensraum.
6. Kaninchen pflanzen sich ungeschlechtlich fort.

Den folgenden Satz würde ich ganz streichen, da er etwas verwirrend und sprachlich nicht ganz korrekt ist: Jeden Monat kommt zu der Anzahl der Paare, die im letzten Monat gelebt haben, die dazu, die im vorletzten gelebt haben, da diese sich nun vermehren. Das entspricht aber gerade der oben angegebenen Rekursionsformel.
statt dessen (*grübel grübel*) -Hati 12:20, 26. Aug 2004 (CEST)

Also Kaninchen pflanzen sich ungeschlechtlich fort. gefällt mir gar nicht (zu wenig realistisch und zu lustlos ;-)). Aber Deine Kritik war schon berechtigt. Was hälst Du von der jetzigen Variante?

Ist so ok. Ergänzung durch eine realistischeres Beispiel: Ungeschlechtliche Fortpflanzung der Blattlaus im Frühling und Sommer: Da kann man tatsächlich von einem weiblichen Individuum ausgehen, das Junge lebend zur Welt bringt, die schon nach kurzer Zeit wieder lebende Junge gebären. -Hati 16:31, 5. Sep 2004 (CEST)

$f_{0}=0$

Ich habe wenig Hoffnung, das dadurch dauerhaft etwas vermieden wird, nämlich das jemand aus welchen Gründen auch immer definiert, dass $f_{0}=1$ ist. Die rekursive Formel ist da sehr unklar, da sie sich auf Vorgänger festlegt.

Wendet man aber die allgemeine Lucas-Folge $U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$ mit P = 1 und Q = -1 bzw. die Formel von Binet an, dann wird klar ersichtlich, das f_0 = 0 sein muß:

Die Fibonaccifolge läßt sich über die allgemeine Formel $U_{n}(1,-1)={\frac {a^{n}-b^{n}}{a-b}}$ mit a = ${\frac {1+{\sqrt {5}}}{2}}$ und b = ${\frac {1-{\sqrt {5}}}{2}}$ erzeugen. Dabei ist $f_{0}=U_{0}(1,-1)={\frac {a^{0}-b^{0}}{a-b}}={\frac {1-1}{a-b}}={\frac {0}{a-b}}=0$

Damit ist gezeigt, daß $f_{0}=0$ ist. --Arbol01 21:57, 22. Nov 2004 (CET)

Lukas-Folge

Habe ja nicht prinzipiell was dagegen, wenn ein Bezug zur Lukas-Folge hergestellt wird. Ich würde das aber auf gar keinen Fall in dieser erschlagenden Ausführlichkeit an den Anfang stellen sondern weit nach unten in ein eigenes Kapitel. Versuche mal, den Artikel mit den Augen eines Laien zu lesen - der schnallt doch völlig ab, selbst wenn er die Rekursionsformel schon kennt. Auch die Parameter 1,-1 fallen für ihn ja völlig unmotiviert vom Himmel. Im Prinzip würde es auch völlig reichen, darauf hinzuweisen, dass ein Bezug zur Lukas-Folge besteht, und die ganze Mathematik dorthin zu verlagern. Wenn unbedingt hier, dann am besten nach dem Goldenen Schnitt z. B. unter Bezug zur Lukas-Folge. Bitte Artikel generell so strukturieren, dass das einfach vorne und das komplizierte weiter hinten steht. --Wolfgangbeyer 00:29, 23. Nov 2004 (CET)

Finde den Abschnitt zu den Lukas-Zahlen schon ungemein formellastig, da könnte man sicher einige Zwischenschritte weglassen. Dafür steht die eigentliche Definition $f(n)=U_{n}(1,-1)$ nirgendwo explizit da, sondern man muss sie sich indirekt aus der Formelwüste klauben. Was soll eigentlich an dieser Definition iterativ sein? --Wolfgangbeyer 00:50, 23. Nov 2004 (CET)

Iterativ? Hmmmm, naja sie ist nicht rekursiv. Ok, sie wird direkt berechnet. Aber ich denke, du kannst das besser Formulieren.

Statt $f(n)=U_{n}(1,-1)$ könnte man natürlich kurz $f(n)=U_{n}$ schreiben, wobei es natürlich unendlich viele $f(n)=U_{n}$ gibt. Wenn Du eine Idee hast, wie man es besser integrieren kann, dann mach es. Wenn mir an der Änderung etwas nicht gefällt, dann kann ich es wieder ändern, bzw. wenn es, wie bei der Mandelbrot-Menge, über meinen Horizont geht, mich aus dem Artikel raushalten werde.

Ich halte es trotzdem für sinnvoll, die Lucas-Folge an erster Stelle zu nennen, weil "Idioten" (dazu zähle ich mich auch), die wilkürlich F(0)=1 setzen, statt F(0)=0. Die rekursive Darstellung läßt das zu, die direkte Darstellung aber nicht. --Arbol01 01:16, 23. Nov 2004 (CET)

Das als Grund für die Einführung der Lukas-Folge ist nicht einsichtig. Wer sagt denn, dass man $f(n)=U_{n}(1,-1)$ definieren muss und nicht $f(n)=U_{n+1}(1,-1)$? Es gibt keine richtigen und falschen Definitionen in der Mathematik, sondern nur mehr oder weniger nützliche. Daher hat diese Argumentation kein Gewicht. --Wolfgangbeyer 18:57, 23. Nov 2004 (CET)

Nachtrag: Es ist durchaus nicht selbstverständlich, dass das einfache vor dem komplizierten kommt. Bestes Beispiel dagegen ist der Binomialkoeffizient, bei dem das Allgemeine vor dem Speziellen kommt, und eben nicht das Einfache vor dem Komplizierten. Nebenbei habe ich Binomialkoeffizient nicht strukturiert. --Arbol01 01:41, 23. Nov 2004 (CET)

Das kann ich nicht erkennen. In Binomialkoeffizient geht es von anfang an um Binomialkoeffizienten und um nichts komplizierteres. Hier aber wolltest Du die Fibonacci-Folge über etwas einführen, das erheblich komplizierter als das Artikelthema selbst ist. --Wolfgangbeyer 18:57, 23. Nov 2004 (CET)

Wie dem auch sei, ich habe jetzt den Formellastigen Teil nach hinten verschoben, dafür aber die Formel von Binet an diese Stelle gesetzt, an der vorher die Lucas-Folge war. Und ganz nach vorne habe ich die Kaninchen gesetzt. --Arbol01 19:11, 23. Nov 2004 (CET)

Evtl. hast Du die Bedeutung des Begriffs "Wikisource" missverstanden. Das ist keine Sammlung zum Auslagern von Source-Code im Sinne von Computerprogrammen, sondern eine Sammlung von ganz gewöhnlichen Texten. Ich bin auch kein Freund von langatmigen Programm-Listings in Wikipedia-Artikeln, so dass ich das hier eigentlich nicht unbedingt vermisse. Aber es ist nur eine Frage der Zeit, bis hier wieder jemand so was reinschreibt - wenn wir Pech haben doppelt so umfangreich. --Wolfgangbeyer 19:45, 23. Nov 2004 (CET)

Hoppla, sehe erst jetzt den Weblink auf den Quellkode. Das verhindert vielleicht doch, dass er wieder hier reinkommt ;-). --Wolfgangbeyer 19:50, 23. Nov 2004 (CET)

Jein, vielleicht ist es mal so gedacht gewesen. Jedenfalls wimmelt es, im eglischsprachigen Wikisource-Teil, vin Programmlistings. Da fallen die beiden Fibonacci-Listings überhapt nicht auf. Das mußt Du dir wirklich mal ansehen.

Ich würde es nie wagen, in den deutschsprachigen Teil der Wikisource Programmlistings, oder Listen und Tabellen mit Prim- oder sonstigen Zahlen unterzubringen.

Wenn jemand wieder Listings im Artikel Fibonacci-Folge unterbringt, dann ist in dem ausgelagerten Listing-Teil noch genug platz.

Hier, um sich ein Bild zu machen: http://wikisource.org/wiki/Main_Page:English http://wikisource.org/wiki/Wikisource:Source_code http://wikisource.org/wiki/Wikisource:Mathematics. --Arbol01 19:57, 23. Nov 2004 (CET)

Rekursion oder Iteration

Seid ihr euch sicher, dass Fibonacci und Konsorten rekursiv (also durch eine Proozedur, die sich selbst aufruft), oder nicht doch iterativ, also durch eine Prozedur die nacheinander abläuft, wobei bei jedem Durchlauf der zuletzt errechnete Wert übergeben wird? Siehe die verlinkten Programm-Beispiele die für mich schwer nach Iteration ausschauen. Siehe dazu auch Heinz-Otto Peitgen et al., Bausteine des Chaos, 1992, Klett-Cotta, ISBN 3-6-08-95888-7 -Hati 18:21, 26. Nov 2004 (CET)

Die Frage verstehe ich nicht! Keine Funktion kann den Anspruch erheben, ausschließlich durch Rekursion, Iteration oder auch nur direkt darstellen. Eine Funktion, für die es einen rekursiven Algorithmus gibt, existiert auch einen iterativen Algorithmus (Arbol01)

Stimmt schon - so wie es da steht, ist die Bezeichnung iterativ passender. --Wolfgangbeyer 10:29, 27. Nov 2004 (CET)

Oder? Jetzt bin ich etwas verwirrt. Man spricht von einer Rekursionsformel aber nicht von einer Iterationsformel. Rekursiv heißt selbstbezüglich, und das ist es ja. Vielleicht muss man bedenken, ob man von der Formel oder einer programmtechnischen Umsetzung spricht. Im iterativen Algorithmus tritt der rekursive Charakter zurück, da man Zuweisungen zu verschieden Variablen macht, die aber letztlich zur selben Folge gehören. Da Iteration nur ausdrückt, dass viele Schritte notwendig sind, ist Rekursion hier schon treffender. --Wolfgangbeyer 10:48, 27. Nov 2004 (CET)rekursiv onder iterativ

Rekursiv ist, wen eine Funktion r wieder eine funktion r aufruft die wiederum r aufruft, und so weiter, bis eine Abbruchbedingung erfüllt ist:

(!5) = 5*(!4) = 5*4*(!3) = 5*4*3*(!2) =5*4*3*2*(!1) = 5*4*3*2*1

Iterativ ist, wenn die Berechnung in einer Schleife abläuft:

w=5
f=1
do i = 1 to w
  f=f*i
end
say fakultät f

Das ist der prinzipielle Unterschied zwischen Rekursiv und Iterativ. Später mehr! --Arbol01 11:04, 27. Nov 2004 (CET)

Schon klar, das ist das, was ich oben mit programmtechnischer Umsetzung bezeichnet habe. Um die geht es aber im Artikel gar nicht sondern um die mathematische Definition. Und die ist selbstbezüglich also eine Rekursionsformel. --Wolfgangbeyer 13:52, 27. Nov 2004 (CET)

Da stellt sich mir wiederum eine Frage: Die folgende Funktion zu Berechnung des Binomialkoeffizienten ist iterativ realisiert:

#include <stdio.h>

unsigned int ggt(unsigned int m, unsigned int n)
{
  unsigned int c=0;
  do
  {
    if (m < n)
    {
      if ((n % m) > 0)
      {
        n %= m;
      }
      else
      {
        c = m;
      }
    }
    if (m > n)
    {
      if ((m % n) > 0)
      {
        m %= n;
      }
      else
      {
        c = n;
      }
    }
  }
  while (c == 0);
  return(c);
}

unsigned int bin_koeff(unsigned int n, unsigned int k)
{
  unsigned int na = n;
  unsigned int ka = k;
  unsigned int t;
  if (na == ka) ka = 0;
  if (na == 0)  return(0);
  if (ka == 0)  return(1);
  if (ka == 1)  return(na);
  if ((ka > 1) && (na > 0))
  {
    do
    {
      na *= (n-1);
      ka *= (k-1);
      t   = ggt(na,ka);
      na /= t;
      ka /= t;
      n--;
      k--;
    }
    while (k > 1);
  }
  return(na / ka);
}

int main()
{
  unsigned int a, b, ergebnis;
  scanf("%d",&a);
  scanf("%d",&b);
  ergebnis = bin_koeff(a,b);
  printf(" %d ueber %d = %d \n",a,b,ergebnis);
  return 0;
}

Ist sie nach mathematischer Definition dennoch rekursiv? Es würde mich wundern.

Die rekursive Realisation der gleichen Funktion ist:

MAIN
  DEFINE ergebnis INTEGER,
         wert1    INTEGER,
         wert2    INTEGER
  PROMPT "n : " FOR wert1
  PROMPT "k : " FOR wert2
  CALL binomial_koeffizient(wert1,wert2) RETURNING ergebnis
  DISPLAY ergebnis
END MAIN

FUNCTION binomial_koeffizient(n,k)
  DEFINE ergebnis1 INTEGER,
         ergebnis2 INTEGER,
         n         INTEGER,
         k         INTEGER
  IF ((k = 0) AND (n >= 0)) OR ((k = n) AND (k >= 0)) THEN
    LET ergebnis1 = 1
    RETURN ergebnis1
  END IF
  IF (n > k) AND (k > 0) THEN
    CALL binomial_koeffizient(n-1,k-1) RETURNING ergebnis1
    CALL binomial_koeffizient(n-1,k)   RETURNING ergebnis2
    LET ergebnis1 = ergebnis1 + ergebnis2
    RETURN ergebnis1
  END IF
END FUNCTION

--Arbol01 14:37, 27. Nov 2004 (CET)

"Ist sie nach mathematischer Definition dennoch rekursiv?" Diese Frage gibt für mich keinen Sinn und beruht vielleicht auf einem Mißverständnis. Du stellst ein iteratives Verfahren vor. Die mathematische Definition, von der ich sprach, bezog sich auf die Struktur der Formel im Artikel. Und die würde ich, so wie sie da steht, rekursiv nennen. Das heißt nicht, dass man f(n) nicht über ein iteratives Verfahren berechnen kann. --Wolfgangbeyer 16:18, 27. Nov 2004 (CET)

Ah jetzt verstehe ich! Aber dann drücke es auch so aus. Ich verstand deine Antwort so, als ob die iterative Darstellung der Fäkultät dem Mathematischen Sinne nach rekursiv sei.

Das F(n) = F(n-1) + F(n-2) rekursiv ist, ist unbestreitbar. --Arbol01 17:33, 27. Nov 2004 (CET)

Überarbeitung

Habe mir doch noch mal die Zeit genommen, diesen Artikel etwas umzugestalten:

• Worte sind zwar oft leichter verständlich als Formeln, aber im vorliegenden Fall ist es eher umgekehrt: Die Rekursionsformel zusammen mit dem Satz, dass jede Zahl die Summe iherer beiden Vorgänger ist, dürfte erheblich leichter nachvollziehbar sein, als die Schilderung der Kaninchenpopulation. Ich wette, die meisten Leser müssen erst dreimal nachdenken, bevor sie darin die simple Rekursionsformel wiedererkennen. Daher ist die Rekursionsformel am Anfang ausnahmsweise besser aufgehoben.
• Im Prinzip ist es in der Mathematik eine Frage des Geschmacks, welche Aussagen man als Definition und welche man als abgeleitete Beziehungen darstellt. Im Rahmen der Wikipedia sehe ich keien Sinn, irgendetwas anderes als in Übereinstimmung mit der Mathematikgeschichte die Rekursionsformel als Definition vorzustellen. Die Formel von Binet gehört daher an eine spätere Stelle im Text.
• Die Lucas-Folge geht ja über das eigentlich Thema des Artikel weit hinaus. Habe daher mal alles, was damit zusammenhängt in ein einziges Kapitel gesteckt. Auch die Umformung in die Formel von Binet müssen wir daher nicht mit zig Rechenschritten nachvollziehen, sondern es genügt, den Weg anzudeuten. Da damit diese Beziehung für den allgemeinen Fall bewiesen ist, muss sie ja nicht noch explizit für f₂ bewiesen werden. Auch die Herleitung der Rekursionsformel erübrigt sich damit, denn sie zeigt nichts anderes als die innere Widerspruchsfreiheit der Mathematik. Ganz abgesehen beruht sie auf der Beziehung $U_{n+2}=PU_{n}-QU_{n+1}$, die völlig vom Himmel fällt. Selbst unter Lucas-Folge finde ich sie nicht. --Wolfgangbeyer 00:44, 8. Dez 2004 (CET)

Vieleicht nicht unter Lucas-Folge, so aber doch unter Fibonacci numbers unter Generalizations. Ich halte es doch mal für angebracht, über die Grenze zu schauen. --Arbol01 01:55, 8. Dez 2004 (CET)

Hallo Arbol01, ich habe meine Änderungen ausführlich begründet. Wenn Du das einfach komplett revertierts, erwarte ich schon einen Kommentar zu meinen Argumenten. Der ganze Abschnitt zur Lucas-Zahlen ist reichlich verwirrend für den Leser. Du sagst dem Leser nicht, wovon Du ausgehst, wo Du hin willst und warum. Zusätzlich zu meinen obigen Einwänden: Wen interessiert, dass ab U₂ die Ausdrücke a und b benötigt werden? Ich habe absolut nichts gegen einen Blick über den Zaun, aber Du solltest in diesen Abschnitt einen Roten Faden reinbringen. Im Übrigen ist Dir offenbar entgangen, dass ich die Schreibweise f(n) in die für Folgen übliche Schreibweise f_n umgewandelt habe. --Wolfgangbeyer 22:05, 8. Dez 2004 (CET)

Eine Antwort: Ich bin durchaus nicht mit deiner Begründung über deine Änderung zufrieden (allerdings habe ich auch keinen Anspruch auf eine solche ausführliche Begründung). Ich möchte für jeden, den es interessiert, einen weiteren Weg, oder besser gesagt ein komplettes Bild bieten, und nicht nur eine 08/15-Antwort, wie sie im täglichen Schulbetrieb, und vielleicht auch sonstwo, Usus ist (Der Spiegel 50/6.12.04 - Die Magie der Zahlen). Anders gesagt ich will dem, den es interessiert, die Möglichkeiten bieten, die ich während meiner Schulzeit, und auch sonst, nicht hatte. Und dazu gehört auch dieses hochkomplizierte Gebiet dazu. Ich halte keinen Menschen für so Doof, das er es nicht verstehen könnte. Tatsächlich ist mir natürlich auch klar, das jeder Mensch das sich alles selbst noch mal erarbeiten (errechnen) muß. Zumindest will ich aber jedem diese Wege bieten.

Ja, das mit dem f(n) ist mir entgangen, bzw. wollte ich erst mal abwarten.

Nicht unbedingt als Handreichung, folgende Überlegung: Ich nehme meinen Abschnitt, und baue ihn in die Lucas-Folgen ein. Nicht um Dir einen Gefallen zu tun, oder dir zuzugestehen, der Artikel Fibonacci-Folge wäre dein Artikel (auch wenn Du ihn initiert hast). --Arbol01 22:23, 8. Dez 2004 (CET)

Noch etwas: Eine Enzykliopädie ist weder ein Roman, noch ein Fachbuch. Dein Wunsch nach einem roten Faden ist verständlich, aber schwierig, bis unmöglich. Warum? Weil die Intention eines Lesers, die in diesem Falle die Hauptrolle spielt, eine ganz unterschiedliche ist. Der eine Leser hat einen Standpunkt, der nächste einen anderen, und beide Leser fassen den Artikel dementsprechend unterschiedlich auf. Bei einem Roman führt der Autor durch eine Geschichte, die dann ja wirklich eindimensional sein muß, und in einem Lehrbuch ist das ähnlich. Die Mathematik ist aber nicht eindimensional, sondern ein ganzes Universum, bei der man im Idealfall von jedem Punkt zu jedem anderen Punkt kommt. --Arbol01 22:32, 8. Dez 2004 (CET)

Eine Enzyklopädie soll demjenigen, der über ein Thema etwas wissen will, helfen, dieses Wissen zu erlangen. Wenn nur derjenige mit einem Artikel etwas anfangen kann, der es eh schon weiß, kann man sich die Mühe sparen. Insofern sollte ein Enzyklopädie Artikel durchaus vom Einfachen zum Schweren gehen und nicht umgekehrt, sonst wendet sich der Leser einem anderen Thema zu. Wenn jetzt das Argument kommt, "dann ist der Leser meines Artikels nicht wert", dann ist das ziemlich arrogant. Wiki dient nicht der geistigen Selbstbefriedigung seiner Autoren. Wenn jemand wirklich über ein Thema Bescheid weiß und nicht nur so tut als ob, weil er sich hier und da etwas angelesen hat, dann kann er diese Information auch strukturiert (d.h. mit Rotem Faden) rüberbringen. --217.255.10.102 09:25, 9. Dez 2004 (CET)

Zuerst zu deinem Vorwurf: Wenn ich wirklich der Ansicht wäre: "dann ist der Leser meines Artikels nicht wert", dann würde ich hier gar nicht erst schreiben. Mein Ziel ist ja, etwas, was ich auch weiß, oder zumimdest erfahren habe, anderen weiterzuvermitteln. Und ich bin auch nicht der Ansicht, man solle um Himmelswillen immer vom leichten zum Schweren gehen. Nein, man soll und muß auch den Weg vom "schweren" zum einfachen nehmen. Der Aha-Effekt, der Erfolg ist um so größer. Du sprichst wie derjenige, der immer nur den Wanderweg benutzt, und die Nase über diejenigen rümpfst, die freikletternd ihren Weg anders suchen. Einfach geht immer. In diesem Fall hat fast jedes Programmierhandbuch, jeder Programmierkurs die rekursive Programmierung der Fibonacci-Folge. Wo bleibt da die Herausforderung. --Arbol01 17:27, 9. Dez 2004 (CET)

Ich komme mal auf Dein obiges "Angebot" zurück und setze eine gestraffte Version ein. (Nebenbemerkung zur Vermeidung von Missverständnissen: 217.255.10.102 bin nicht ich. Ich stimme ihm auch nur partiell(!) zu.) --Wolfgangbeyer 23:39, 9. Dez 2004 (CET)

Ich habe es auch nicht geglaubt! --Arbol01 00:49, 10. Dez 2004 (CET)

f(0)=1?

Habe mal ein wenig gegoogelt: f₀=1 habe ich nicht gefunden. Damit müsste man auch alle Formeln weiter unten anpassen. Allerdings wird häufig mit f₁=1 begonnen, d. h. f₀=0 ausgelassen, oft aber in Kombination mit einer bestimmten praktischen Situation, in der die Fibonacci-Zahlen auftauchen und situationsbedingt mit 1 beginnen. Habe mal eine entsprechende Formulierung gewählt. --Wolfgangbeyer 21:25, 20. Jan 2005 (CET)

Fibonacci und die Kaninchen

In wie weit sieht man denn die Fibonacci-Zahlen in einer Kaninchen-Population? ich erkenne eher sowas wie eine klassisdche exponentielle zunahme.

danke, --Abdull 00:23, 23. Jan 2005 (CET)

Da empfehle ich den Zahlenteufel von Hans Magnus Enzensberger. Da ist es sehr anschaulich beschrieben. Im übriegen ist es umgekehrt. Die Fibonacci-Folge soll das Wachstum einer Kaninchenpopulation erklären, und nicht die Kaninchenpopulation die Fibonacci-Folge.

Angenommen man beginnt mit einem Kaninchenpärchen zu einem Zeitpunkt Null. Erst nach zwei Monaten kann ein Pärchen Junge bekommen, und zwar der Einfachheithalber ein Pärchen. Danach bekommt dann ein Pärchen jeden Monat Junge (immer noch der Einfacherhalber Pärchen):

0    1    2    3    4    5    6 ...

1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 ...
          1 -> 1 -> 1 -> 1 -> 1 
               1 -> 1 -> 1 -> 1
                    1 -> 1 -> 1
                    1 -> 1 -> 1
                         1 -> 1
                         1 -> 1 ...
                         1 -> 1
                              1
                              1
                              1
                              1
                              1 ...

Und so weiter. So ungefähr klappt das auch mit der Verästelung bei Bäumen. --Arbol01 00:43, 23. Jan 2005 (CET)

Ach ja, natürlich nur bei einem unbegrenzten Lebensraum, Unsterblichkeit, immer Pärchen und kein Inzuchtproblem. --Arbol01 00:48, 23. Jan 2005 (CET)

Verallgemeinerung

Das die Fibonacci-Folge (Folgen ?) mit der allgemeinen Lucas-Folge zu tun hat, habe ich schon mal erwähnt. Das hat aber mit dem, worauf ich hier hinaus will nur am Rande zu tun.

Die Fibonacci-Folge läßt sich über die Formel von Binet:

$f_{n}={\frac {1}{\sqrt {5}}}(a^{n}-b^{n})$ mit a = ${\frac {1+{\sqrt {5}}}{2}}$ und b = ${\frac {1-{\sqrt {5}}}{2}}$

herleiten. Das steht ja auch im Artikel. Aber das ist nicht die einzige Folge dieser Art. Es gibt unzählige Folgen der Form:

$f_{n}={\frac {1}{\sqrt {x}}}(a^{n}-b^{n})$ mit a = ${\frac {1+{\sqrt {x}}}{2}}$ und b = ${\frac {1-{\sqrt {x}}}{2}}$

Die einzelnen Glieder dieser verallgemeinerten Folge sind $a_{0}=0\ ,\ a_{1}=1\ ,\ a_{2}=1\ ,\ a_{3}={\frac {3+x}{4}}\ ,\ a_{5}=...$. Leider bin ich noch weiter gekommen. --Arbol01 16:55, 17. Mär 2005 (CET)

Jede zweistufige lineare Rekursion

$a_{n+1}=ua_{n}+va_{n-1}$

hat eine explizite Lösungsformel, die entweder die Form

$a_{n}=c_{1}\lambda _{1}^{n}+c_{2}\lambda _{2}^{n}$

oder

$a_{n}=c_{1}\lambda ^{n}+c_{2}n\lambda ^{n}$

hat. Umgekehrt erfüllt jede Folge dieser Form eine zweistufige lineare Rekursion, in Deinem Fall

$a_{n+1}=a_{n}-{\frac {1-x}{4}}\cdot a_{n-1}.$

Steht das hier in der WP nicht schon irgendwo?--Gunther 18:59, 17. Mär 2005 (CET)

Das wüßte ich auch gerne. Wenn nicht, dann sollte es irgendwo stehen. Warum nicht unter verallgemeinerung der Fibonacci-Folgen? --Arbol01 19:06, 17. Mär 2005 (CET)

Es gibt eine (ziemlich unverständliche) Fassung unter Lineare Differenzengleichung. Habe diesen Artikel als "überarbeitungswürdig" eingetragen, vielleicht verbessert er sich ja von selbst :-)--Gunther 23:56, 17. Mär 2005 (CET)

Zu Deiner Verallgemeinerung siehe Wikipedia:Was Wikipedia nicht ist, Punkt 2. Das fällt alles wie gesagt unter die Lösungstheorie linearer Rekursionen, aber welche besonderen Eigenschaften hat Deine Verallgemeinerung?

Versteh' mich nicht falsch, es ist nun einmal extrem schwierig, in der Elementarmathematik Konzepte zu finden, die nicht schon Hunderte anderer betrachtet haben.--Gunther 09:09, 18. Mär 2005 (CET)

Mit Punkt 1. spielst Du wahrscheinlich auf "Wikipedia dient nicht der Theoriefindung, sondern der Theoriedarstellung. In ihr sollten weder neue Theorien, Modelle, Konzepte, Methoden aufgestellt noch neue Begriffe etabliert werden. Ebenso unerwünscht sind nicht nachprüfbare Aussagen. Ziel des Enzyklopädieprojektes ist die Zusammenstellung bekannten Wissens." an. Das trifft es in diesem Fall aber nicht, da es unzählige dieser Folgen gibt, und es bestimmt nicht neu ist.

Das besondere der allgemeinen rekursiven Formel ist halt, das man ein (nicht ganz) beliebiges x einsetzen kann, und man bekommt die entsprechende Folge:

x = 5: 0, 1, 1, 2, 3, 5, 8, ... (Fibonacci-Folge) $a_{n+1}=a_{n-1}+a_{n}$

x = 9: 0, 1, 1, 3, 5, 11, 21, 43, ... (Jacobstal-Folge) $a_{n+1}=2*a_{n-1}+a_{n}$

Kurz gesagt: Für x = 4m+1 bekommt man die rekursive Folge $a_{n+1}=m*a_{n-1}+a_{n}$ wenn ich alles richtig verstanden habe. --Arbol01 09:57, 18. Mär 2005 (CET)

Trotzdem wählst Du eine spezielle Klasse aus, und diese Betrachtung ist "neu". Eine etwas übertriebener Vergleich wäre ein Abschnitt in reelle Zahl über Zahlen, deren dezimale Nachkommastellen alle gerade sind. Natürlich sind reelle Zahlen nicht neu, aber gerade diese Unterklasse zu betrachten ist es.--Gunther 10:14, 18. Mär 2005 (CET)

Es gibt in Wikipedia auch einen Grundsatz: "Ignoriere die Regeln". Das heißt nicht, das man machen soll, was man will.

Mir geht es letzendlich immer noch um die Lucas-Folgen. Die Fibonacci-Folge und die Jacobsthal-Folge (das sind die beiden bekannten Folgen) gehören zu den folgen, die durch das Schema $a={\frac {1+{\sqrt {x}}}{2}}$ und b = ${\frac {1-{\sqrt {x}}}{2}}$ miteinander, und mit der allgemeinen Lucas-Folge verbunden sind. Es gibt da noch wenigstens zwei andere spezielle Formen der Lucas-Folge. Eine davon ist dergestalt, daß bei beistimmten P und Q die beiden Lösungen der quadratischen Gleichung natürliche Zahlen sin. Die andere Form habe ich nicht parat.

Ausserdem gibt es noch den kleinen Fermatschen Satz als Spezialfall der allgemeinen Lucas-Folge. --Arbol01 10:38, 18. Mär 2005 (CET)

Habe mal einen verständlichen Teil zu Lineare Differenzengleichung hinzugefügt.--Gunther 16:28, 18. Mär 2005 (CET)

n > 2 ist überflüssig

Der Zusatz, das für die Fibonacci-Folge $a_{n}=a_{n-1}+a_{n-2}\$ erst ab n=2 gilt ist überflüssig und falsch. Da der Umkehrschluß $a_{n-2}=a_{n}-a_{n-1}\$ gilt. Die Folge läßt sich also nach hinten verlängern:

... 8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 34 55 89 144 233 ... . 

$a_{0}=1$ und $a_{1}=1$ gelten natürlich weiterhin. --Arbol01 23:02, 26. Nov 2005 (CET)

Hallo Arbol01. Ich denke, die Einschränkung n >= 2 ist nicht überflüssig, und falsch ist sie schon gar nicht. Jede Folge muss einen Definitionsberech haben, und der ist hier {0, 1, 2, 3, ...} und eben nicht Z (ganze Zahlen). Bei jeder rekursiven Definition gibt es einen oder mehrere Startwerte, und dann eben eine Vorschrift, die ab einem bestimmten n (hier 2) auf frühere Werte zurückgreift. ich möchte daher die Einschränkung wieder aufnehmen. Konnte ich dich überzeugen? Gruß von --Wasseralm 23:39, 26. Nov 2005 (CET)

Hallo ihr beiden, ich war einfach so frei, und habe das Bildungsgesetz - wie ich hoffe - etwas flüssiger formuliert. In dieser neuen Version sollte unmittelbar herauskommen, dass $n\geq 2$ eine sinnvolle Ergänzung ist.--JFKCom 23:51, 26. Nov 2005 (CET)

Wenn wir statt einer Aufzählung von 3 Gleichungen einen Satz hinschreiben, dann geben auch die Aufzählungspunkte keine Sinn mehr. Habe daher einen anderen Vorschlag formuliert. --Wolfgangbeyer 01:37, 27. Nov 2005 (CET)

Naja, ehe ich hier einen Edit-War auslöse beuge ich mich der Mehrheit. Nichtsdestotrotz halte ich die Einschränkung $n\geq 2$ für überflüssig, da, wie sich aus der in Z erweiterte Konstrukt kein Widerspruch ergibt, wenn man die rekursive Bildungsregel für alle n $a_{n}=a_{n-1}+a_{n-2}\$ sein läßt. Erst wenn die erweiterung nach Z zu einem Widerspruch führen würde, wäre so eine Einschränkung angebracht. --Arbol01 02:02, 27. Nov 2005 (CET)

Ich wollte eigentlich nicht für $n\geq 2$ plädieren sondern nur gegen die Aufzählungszeichen, die durch den Satz zerrissen wurden. Hinsichtlich $n\geq 2$ bin ich eher neutral. --Wolfgangbeyer 02:21, 27. Nov 2005 (CET)

Die Frage ist nicht, ob diese Fortsetzung möglich ist, sondern ob sie üblich ist und ob sie relevante Anwendungen hat. Primär ist die Fibonacci-Folge eine Folge, also indiziert durch positive oder nichtnegative ganze Zahlen.--80.136.185.54 03:15, 27. Nov 2005 (CET)

Also mir gefällt die momentane Version auch ziemlich gut. Gruß --Wasseralm 13:53, 27. Nov 2005 (CET)

Fibonacci-Folge und Lucas-Folge

Um gleich die Luft rauszulassen: Ich meine die Folge 2, 1, 3, 4, 7, 11, ... und nicht die allgemeinen Lucas-Folgen U(P,Q) und V(P,Q).

Zwischen der Fibonacci-Folge und der Lucas-Folge gibt es Verbindungen. Das sich ein Glied der Lucas-Folge aus der Summe zweier Glieder der Fibonacci-Folge bilden läßt $L_{n}=f_{n-1}+f_{n+1}\$ habe ich schon in Lucas-Folge erwähnt. Es gibt da aber noch eine andere Formel, die mehr die Fibonacci-Folge betrifft: $f_{2n}=f_{n}\cdot L_{n}$. In Worten: Das Produkt der n.ten Fibonacci-Zahl mit der n.ten Lucas-Zahl ist gleich der Fibonacci-Zahl an der doppelten Position. --Arbol01 01:07, 23. Feb 2006 (CET)

"Jeden Monat kommt zu der Anzahl der Paare, die im letzten Monat gelebt haben, eine Anzahl von neugeborenen Paaren hinzu, die gleich der Anzahl der Paare ist, die bereits im vorletzten Monat gelebt haben, da genau diese geschlechtsreif sind und sich nun vermehren. Das entspricht aber gerade der oben angegebenen Rekursionsformel."

Ich glaube, das sollte anders formuliert werden.. diese Erklärung stimmt zwar genau mit der Rekursionsvorschrift überein, nicht jedoch mit der tatsächlichen Vermehrung der Kaninchen. z.B: 3 + 5 = 8, die 8 kommt aber nicht aus dieser Addition zustande, sondern aus 5 (Anzahl der Kaninchenpaare, die es bereits gibt) plus 2 (unter den 5 Kaninchenpaaren gibt es 2, die bereits jedes Monat werfen) plus 1 (Nachkommen des Kaninchenpaares, welches im 4. Monat geboren wurde und nun im 6. Monat zum ersten Mal wirft).

Kann auch sein dass ich mich irre, bitte um eure Meinung! liebe grüße

Ich glaube, Du irrst dich nicht. Aber für die Berechnung macht das ja keinen Unterschied. In der Realität wird ein Weibliches Kaninchen nicht immer die gleiche Zahl an Nachkommen werfen, alte Kaninichen werden sterben, ab einer gewissen Bevölkerungsdichte wird die Geburtenrate zurück gehen, ... . Wichtig ist, das die Näherung stimmt. --Arbol01 17:46, 2. Apr 2006 (CEST)

Die angeblichen "Fibonacci"-Zahlen.

Wie im englischen Pendant zu lesen ist, stammen die Zahlen nicht von Fibonacci!

Sie wurden bereits 1600 Jahre zuvor in Indien entdeckt.

Unglaublich, dass sich solche Misnomen so verbreiten. Habe es in jedem Fall im ersten Abschnitt korrigiert. --Gentlemanx 14:58, 15. Sep 2006 (CEST)

Auch in der alten Version stand nichts davon, dass Fibonacci der erste gewesen sei.--Gunther 15:18, 14. Sep 2006 (CEST)

Auf diesen Firlefanz soll ich jetzt wohl nicht eingehen, oder? Troll woanders 'rum! --Gentlemanx 14:58, 15. Sep 2006 (CEST)