Difference between revisions of "Fibonacci number"
From Free Pascal wiki
Jump to navigationJump to search (review) |
(blow up) |
||
Line 2: | Line 2: | ||
The Fibonacci Sequence is the series of numbers: | The Fibonacci Sequence is the series of numbers: | ||
− | + | <syntaxhighlight lang="pascal"> | |
0, 1, 1, 2, 3, 5, 8, 13, 21, … | 0, 1, 1, 2, 3, 5, 8, 13, 21, … | ||
− | + | </syntaxhighlight> | |
The idea is to add the two last numbers in order to produce the next value. | The idea is to add the two last numbers in order to produce the next value. | ||
== recursive implementation == | == recursive implementation == | ||
− | <syntaxhighlight> | + | <syntaxhighlight lang="pascal"> |
− | function | + | {** |
+ | implements Fibonacci sequence recursively | ||
+ | |||
+ | \param n the index of the Fibonacci number to retrieve | ||
+ | \returns the Fibonacci value at n | ||
+ | } | ||
+ | function fibonacci(const n: byte): qword; | ||
begin | begin | ||
− | // | + | // optimization: then part gets executed most of the time |
if n > 1 then | if n > 1 then | ||
− | + | begin | |
− | + | fibonacci := fibonacci(n - 2) + fibonacci(n - 1); | |
− | + | end | |
− | |||
else | else | ||
− | result := | + | begin |
+ | // since the domain is restricted to non-negative integers | ||
+ | // we can bluntly assign the result to n | ||
+ | fibonacci := n; | ||
+ | end; | ||
end; | end; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
== iterative implementation == | == iterative implementation == | ||
− | This one is preferable for its run-time | + | This one is preferable for its run-time behavior. |
− | + | <syntaxhighlight lang="pascal"> | |
− | <syntaxhighlight> | + | {** |
− | function | + | implements Fibonacci sequence iteratively |
+ | |||
+ | \param n the index of the Fibonacci number to calculate | ||
+ | \returns the Fibonacci value at n | ||
+ | } | ||
+ | function fibonacci(const n: longword): qword; | ||
+ | type | ||
+ | /// more meaningful identifiers than simple integers | ||
+ | relativePosition = (previous, current, next); | ||
var | var | ||
− | + | /// temporary iterator variable | |
+ | i: longword; | ||
+ | /// holds preceding fibonacci values | ||
+ | f: array[relativePosition] of qword; | ||
begin | 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; | end; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | == | + | == see also == |
* [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences] | * [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences] | ||
* [https://freepascal.org/docs-html/current/prog/progsu150.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] | ||
+ | * [https://rosettacode.org/wiki/Fibonacci_sequence#Pascal Fibonacci sequence § “Pascal” on RosettaCode.org] | ||
* [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]] | * [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]] | ||
[[Category:Mathematics]] | [[Category:Mathematics]] |
Revision as of 02:27, 7 November 2018
│
Deutsch (de) │
English (en) │
suomi (fi) │
français (fr) │
русский (ru) │
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, …
The idea is to add the two last numbers in order to produce the next value.
recursive implementation
{**
implements Fibonacci sequence recursively
\param n the index of the Fibonacci number to retrieve
\returns the Fibonacci value at n
}
function fibonacci(const n: byte): qword;
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;
iterative implementation
This one is preferable for its run-time behavior.
{**
implements Fibonacci sequence iteratively
\param n the index of the Fibonacci number to calculate
\returns the Fibonacci value at n
}
function fibonacci(const n: longword): qword;
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 qword;
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;