Difference between revisions of "Fibonacci number/fi"

From Free Pascal wiki
Jump to navigationJump to search
(Created page with "{{Fibonacci_number}} = Fibonaccin lukujono = Fibonaccin lukujono koostuu numeroista: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Ajatuksena on lisätä kaksi viimeistä numeroa yhte...")
 
Line 1: Line 1:
−
{{Fibonacci_number}}
+
{{Fibonacci number}}
−
 
 
−
= Fibonaccin lukujono =
 
  
 
Fibonaccin lukujono koostuu numeroista:
 
Fibonaccin lukujono koostuu numeroista:
 +
<syntaxhighlight lang="pascal">
 +
0, 1, 1, 2, 3, 5, 8, 13, 21, …
 +
</syntaxhighlight>
 +
Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.
  
−
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
+
== Fibonaccin lukujonon luonti ==
  
−
Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.
+
Seuraavat toteutukset osoittavat Fibonacci-numeroiden laskentaperiaatteen. Siinä ei ole syötön valvontaa. Riippuen asetuksista voidaan luoda [[runtime error/fi|ajonaikainen virhe]] (esim. <syntaxhighlight lang="pascal" enclose="none">{$rangeChecks on}</syntaxhighlight> tai käyttämällä {{Doc|package=RTL|unit=system=|identifier=runerror|text=<syntaxhighlight lang="pascal" enclose="none">system.runError</syntaxhighlight>}}), [[Raise/fi|nostaa (raise)]] [[Exceptions/fi|poikkeus]] tai palauttaa väärä arvo, joka ilmaisee, että jokin meni pieleen.
  
−
== Rekursiivinen tapa ==
 
  
−
<syntaxhighlight>
+
=== Rekursiivinen toteutus ===
 +
<syntaxhighlight lang="pascal" line start="3">
 +
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};
  
−
function FibonacciNumber( n : integer ): integer;
+
{**
 +
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
 
begin
−
  if n > 1 then result := ( FibonacciNumber( n - 1 ) + FibonacciNumber( n - 2 ) )
+
// optimization: then part gets executed most of the time
−
    else
+
if n > 1 then
−
      if n = 0 then result := 0
+
begin
−
        else result := 1;
+
fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
−
end;  
+
end
 +
else
 +
begin
 +
// since the domain is restricted to non-negative integers
 +
// we can bluntly assign the result to n
 +
fibonacci := n;
 +
end;
 +
end;
 +
</syntaxhighlight>
  
 +
=== Iteratiivinen toteutus ===
 +
Tämä on suositeltavampi sen  [[runtime|ajonaikaisen]] käyttäytymisen suhteen.
 +
<syntaxhighlight lang="pascal" line start="13">
 +
{**
 +
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;
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
== Iteratiivinen tapa ==
+
== Huomioita ==
−
Tämä on suositeltavampi.
 
  
−
<syntaxhighlight>
+
Fibonacci-numeroa laskettaessa joka kerta uudelleen, kun sitä tarvitaan, tarvitaan jonkin verran muistia ja se vie lisäksi aikaa.
 +
[[Application/fi|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.
  
−
function Fibonacci(n: Integer): Integer;
+
Se miten se tuotannossa toteutetaan on kuitenkin jätetty pois tästä, koska jokainen tekee sen vähän eri tavalla.
−
var
 
−
  i,u,v,w: Integer;
 
−
begin
 
−
  if n <= 0 then
 
−
    exit(0);
 
−
  if n = 1 then
 
−
    exit(1);
 
−
  u := 0;
 
−
  v := 1;
 
−
  for i := 2 to n do
 
−
  begin
 
−
    w := u + v;
 
−
    u := v;
 
−
    v := w;
 
−
  end;
 
−
  Result := v;
 
−
End;
 
−
 
 
−
</syntaxhighlight>
 
  
 
== Katso myös ==
 
== Katso myös ==
−
+
* [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences]
−
* [http://www.freepascal.org/docs-html/prog/progsu151.html Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number]  
+
* [https://freepascal.org/docs-html/current/prog/progsu150.html Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number]
−
* [[Solution_3| Tao Yue Solution to Fibonacci Sequence Problem]]
+
* [https://rosettacode.org/wiki/Fibonacci_sequence#Pascal Fibonacci sequence § “Pascal” on RosettaCode.org]
 +
* [[gmp|GNU multiple precision arithmetic library]]'s functions [https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm <syntaxhighlight lang="c" enclose="none">mpz_fib_ui</syntaxhighlight> and <syntaxhighlight lang="c" enclose="none">mpz_fib2_ui</syntaxhighlight>]
 +
* [[Lucas number/fi|Lucasin luvut]], samantapainen lukusarja mutta erilainen alustus
 +
* [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]]

Revision as of 21:08, 10 July 2019

│ 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

 3type
 4	/// domain for Fibonacci function
 5	/// where result is within nativeUInt
 6	// You can not name it fibonacciDomain,
 7	// since the Fibonacci function itself
 8	// is defined for all whole numbers
 9	// but the result beyond F(n) exceeds high(nativeUInt).
10	fibonacciLeftInverseRange =
11		{$ifdef CPU64} 0..93 {$else} 0..47 {$endif};
12
13{**
14	toteuttaa Fibonacci-sekvenssin rekursiivisesti
15	
16	\param n the index of the Fibonacci number to retrieve
17	\returns the Fibonacci value at n
18}
19function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20begin
21	// optimization: then part gets executed most of the time
22	if n > 1 then
23	begin
24		fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
25	end
26	else
27	begin
28		// since the domain is restricted to non-negative integers
29		// we can bluntly assign the result to n
30		fibonacci := n;
31	end;
32end;

Iteratiivinen toteutus

Tämä on suositeltavampi sen ajonaikaisen käyttäytymisen suhteen. 

13{**
14	toteuttaa Fibonacci-sekvenssin iteratiivisesti
15	
16	\param n the index of the Fibonacci number to calculate
17	\returns the Fibonacci value at n
18}
19function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20type
21	/// more meaningful identifiers than simple integers
22	relativePosition = (previous, current, next);
23var
24	/// temporary iterator variable
25	i: longword;
26	/// holds preceding fibonacci values
27	f: array[relativePosition] of nativeUInt;
28begin
29	f[previous] := 0;
30	f[current] := 1;
31	
32	// note, in Pascal for-loop-limits are inclusive
33	for i := 1 to n do
34	begin
35		f[next] := f[previous] + f[current];
36		f[previous] := f[current];
37		f[current] := f[next];
38	end;
39	
40	// assign to previous, bc f[current] = f[next] for next iteration
41	fibonacci := f[previous];
42end;

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

Retrieved from "http://wiki.freepascal.org/index.php?title=Fibonacci_number/fi&oldid=125709"