Difference between revisions of "Fibonacci number"
From Free Pascal wiki
Jump to navigationJump to search (review) |
|||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Fibonacci number}} |
| − | |||
| − | |||
The Fibonacci Sequence is the series of numbers: | The Fibonacci Sequence is the series of numbers: | ||
| − | 0, 1, 1, 2, 3, 5, 8, 13, 21, | + | 0, 1, 1, 2, 3, 5, 8, 13, 21, … |
| − | The idea is to add the two last numbers | + | The idea is to add the two last numbers in order to produce the next value. |
| − | |||
| − | |||
| + | == recursive implementation == | ||
<syntaxhighlight> | <syntaxhighlight> | ||
| − | + | function FibonacciNumber(const n: integer): integer; | |
| − | function FibonacciNumber( n : integer ): integer; | ||
begin | begin | ||
| − | + | // recursive case | |
| − | + | if n > 1 then | |
| − | + | result := (FibonacciNumber(n-1) + FibonacciNumber(n-2)) | |
| − | + | // base case | |
| − | end; | + | else if n = 0 then |
| − | + | result := 0 | |
| + | else | ||
| + | result := 1; | ||
| + | end; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | == | + | == iterative implementation == |
| − | This one is preferable. | + | This one is preferable for its run-time behaviour. |
<syntaxhighlight> | <syntaxhighlight> | ||
| − | |||
function Fibonacci(n: Integer): Integer; | function Fibonacci(n: Integer): Integer; | ||
var | var | ||
| Line 34: | Line 32: | ||
if n <= 0 then | if n <= 0 then | ||
exit(0); | exit(0); | ||
| − | if n = 1 then | + | if n = 1 then |
| − | + | exit(1); | |
u := 0; | u := 0; | ||
v := 1; | v := 1; | ||
| − | for i := 2 to n do | + | for i := 2 to n do |
begin | begin | ||
w := u + v; | w := u + v; | ||
| Line 45: | Line 43: | ||
end; | end; | ||
Result := v; | Result := v; | ||
| − | + | end; | |
| − | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== See also == | == See also == | ||
| − | + | * [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] |
| − | * [[ | + | * [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]] |
[[Category:Mathematics]] | [[Category:Mathematics]] | ||
Revision as of 18:42, 27 January 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
function FibonacciNumber(const n: integer): integer;
begin
// recursive case
if n > 1 then
result := (FibonacciNumber(n-1) + FibonacciNumber(n-2))
// base case
else if n = 0 then
result := 0
else
result := 1;
end;iterative implementation
This one is preferable for its run-time behaviour.
function Fibonacci(n: Integer): Integer;
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;