Fibonaccifølgen

Fra Wikipedia, den frie encyklopedi

Fibonaccifølgen er en tallfølge som i matematikken er definert som:

Sagt med ord: Du starter med 0 og 1, og produserer deretter det neste Fibonacci-tallet ved å legge sammen de to forrige Fibonacci-tallene. De første Fibonacci-tallene (følge A000045 i OEIS) er

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711 ...

Tallfølgen er uendelig. Det nye tallet i Fibonacci-følgen er gitt ved

Etter hvert som tallene i følgen blir større, nærmer forholdet mellom to etterfølgende tall seg Φ (phi) som tilsvarer 1.6180339887... og utgjør delingsforholdet i det gylne snitt.

Innhold 1 Historie 2 Et enkelt Perlscript for utskrift av følgen 3 Enkel rekursiv Javakode for å beregne fibonaccitall nummer n 4 Referanser

[rediger] Historie

Fibonaccifølgen som fenomen ble først beskrevet av den indiske matematikeren Pingala, født ca. år 500 f. Kr.^[1][2] Han beskrev de grunnleggende idéene bak Fibonnacifølgen. I den moderne verden er likevel fenomenet best kjent på grunn oppdagelsene gjort av Leonardo Fibonacci (1170-1250), fra Pisa i Nord-Italia. Han beskrev økningen i en noe idealisert kaninbestand (antall par kaniner) etter n måneder hvis følgende kriteria blir møtt:

• Den første måneden blir det bare født ett kaninpar,
• Nyfødte kaninpar blir produktive fra og med den andre måneden og utover,
• Innavl eksisterer ikke,
• Hver måned produserer hvert kjønnsmodent par et nytt kaninpar, og
• Kaninene dør aldri.

Formelen ovenfor passer til kaninproblemet fordi hvis vi i måneden n har a kaniner og i måneden n+1 har b kaniner, så vil vi i måneden n+2 ha a+b kaniner. Dette fordi vi vet at hver kanin hovedsakelig føder en ny kanin hver måned (eller egentlig at hvert par føder et annet par, men det er akkurat det samme) og det betyr at alle a kaniner føder et tilsvarende antall a kaniner som vil bli kjønnsmodne etter to måneder, som er nøyaktig i måneden n+2. Det er derfor vi har bestanden ved tidspunktet n+1 (som er b) pluss bestanden ved tidspunkt n (som er a).

Fibonacci-følgen finnes også i stor grad i naturen, for eksempel vil antall kronblader på blomster og antall blader ofte følge følgen.

[rediger] Et enkelt Perlscript for utskrift av følgen

#!/usr/bin/perl

use bigint;

my ($a, $b) = (1, 1);
for (;;) {
    print("$a\n");
    ($a, $b) = ($b, $a+$b);
}

[rediger] Enkel rekursiv Javakode for å beregne fibonaccitall nummer n

	public static int fib(int n){
		if(n == 0 || n == 1)
			return 1;
		else
			return fib(n-1)+ fib(n -2);
		
	}

[rediger] Referanser