Fibonacci number/fi
│
Deutsch (de) │
English (en) │
suomi (fi) │
français (fr) │
русский (ru) │
Fibonaccin lukujono koostuu numeroista:
0, 1, 1, 2, 3, 5, 8, 13, 21, …
Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.
Fibonaccin lukujonon luonti
Seuraavat toteutukset osoittavat Fibonacci-numeroiden laskentaperiaatteen. Siinä ei ole syötön valvontaa. Riippuen asetuksista voidaan luoda ajonaikainen virhe (esim. {$rangeChecks on}
tai käyttämällä system.runError
), nostaa (raise) poikkeus tai palauttaa väärä arvo, joka ilmaisee, että jokin meni pieleen.
Rekursiivinen toteutus
type
/// domain for Fibonacci function
/// where result is within nativeUInt
// You can not name it fibonacciDomain,
// since the Fibonacci function itself
// is defined for all whole numbers
// but the result beyond F(n) exceeds high(nativeUInt).
fibonacciLeftInverseRange =
{$ifdef CPU64} 0..93 {$else} 0..47 {$endif};
{**
toteuttaa Fibonacci-sekvenssin rekursiivisesti
\param n the index of the Fibonacci number to retrieve
\returns the Fibonacci value at n
}
function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
begin
// optimization: then part gets executed most of the time
if n > 1 then
begin
fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
end
else
begin
// since the domain is restricted to non-negative integers
// we can bluntly assign the result to n
fibonacci := n;
end;
end;
Iteratiivinen toteutus
Tämä on suositeltavampi sen ajonaikaisen käyttäytymisen suhteen.
{**
toteuttaa Fibonacci-sekvenssin iteratiivisesti
\param n the index of the Fibonacci number to calculate
\returns the Fibonacci value at n
}
function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
type
/// more meaningful identifiers than simple integers
relativePosition = (previous, current, next);
var
/// temporary iterator variable
i: longword;
/// holds preceding fibonacci values
f: array[relativePosition] of nativeUInt;
begin
f[previous] := 0;
f[current] := 1;
// note, in Pascal for-loop-limits are inclusive
for i := 1 to n do
begin
f[next] := f[previous] + f[current];
f[previous] := f[current];
f[current] := f[next];
end;
// assign to previous, bc f[current] = f[next] for next iteration
fibonacci := f[previous];
end;
Huomioita
Fibonacci-numeroa laskettaessa joka kerta uudelleen, kun sitä tarvitaan, tarvitaan jonkin verran muistia ja se vie lisäksi aikaa. Sovellukset jotka luottavat voimakkaasti Fibonacci-numeroihin, käyttävät hakutaulukkoa. Sitä ei yleensä enää lasketa, mikä on jo tunnettu tosiasia. Koska Fibonacci-sekvenssi ei muutu, sen laskeminen on lähinnä opetusta, mutta sitä ei ole tarkoitettu tuotanto käyttöön.
Se miten se tuotannossa toteutetaan on kuitenkin jätetty pois tästä, koska jokainen tekee sen vähän eri tavalla.
Katso myös
- Fibonacci numbers in the on-line encyclopedia of integer sequences
- Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number
- Fibonacci sequence § “Pascal” on RosettaCode.org
- GNU multiple precision arithmetic library's functions
mpz_fib_ui
andmpz_fib2_ui
- Lucasin luvut, samantapainen lukusarja mutta erilainen alustus
- Tao Yue Solution to Fibonacci Sequence Problem