پیاده سازی الگوریتم فیبوناچی Fibonacci در زبان های مختلف

برنامه نویسی
در زیر مجموعه ای از کدهای مسئله سری فیبوناچی به زبان های مختلف با دو رویکرد بازگشتی و مبتنی بر تکرار ارائه شده است.
Algorithm Implementation/Mathematics/Fibonacci Number Program
C
Recursive version
unsigned int fib(unsigned int n){ if (n < 2) return n; else return fib(n - 1) + fib(n - 2); }
Recursive version 2
unsigned int fib(unsigned int n){ return (n < 2) ? n : fib(n - 1) + fib(n - 2); }
Tail recursive version
// C++ default arguments used. If implemented in C, call with fib(n, 1, 0) instead. unsigned int fib(unsigned int n, unsigned int a = 0, unsigned int b = 1) { if(n < 1) return a; else return fib(n - 1, a + b, a); }
Lucas form
#include <math.h> long fib(unsigned int n) { double fi = (1 + sqrt(5))/2; return (pow(fi, n) - pow(-fi, -n)) / sqrt(5); }
Iterative version
unsigned int fib(unsigned int n) { unsigned int i = 1, j = 0, k, t; for (k = 1; k <= n; k++) { t = i + j; i = j; j = t; } return j; }
Exponentiation by squaring
unsigned int fib(unsigned int n){ unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t; if (n <= 0) return 0; while (i > 0){ if (i % 2 == 1){ t = d*(b + a) + c*b; a = d*b + c*a; b = t; } t = d*(2*c + d); c = c*c + d*d; d = t; i = i / 2; } return a + b; }
Alternate exponentiation by squaring
unsigned int fib(unsigned int n){ unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t; if (n <= 0) return 0; while (i > 0){ while (i % 2 == 0){ t = d*(2*c + d); c = c*c + d*d; d = t; i = i / 2; } t = d*(b + a) + c*b; a = d*b + c*a; b = t; i--; } return a + b; }
[divider]
C#
Iterative version
static int fib(int n) { int fib0 = 0, fib1 = 1; for (int i = 2; i <= n; i++) { int tmp = fib0; fib0 = fib1; fib1 = tmp + fib1; } return (n > 0 ? fib1 : 0); }
Binet’s formula
static int fibBINET(int n) { double sqrt5 = Math.Sqrt(5.0); double phi = (1 + sqrt5 ) / 2; return (int)((Math.Pow(phi, n+1) - Math.Pow(1-phi, n+1)) / sqrt5); }
Using long numbers
static Num FibbonaciNumber(int n) { Num n1 = new Num(0); Num n2 = new Num(1); Num n3 = new Num(1); for (int i = 2; i <= n; i++) { n3 = n2 + n1; n1 = n2; n2 = n3; } return n3; } struct Num { const int digit_base = 0x40000000; // 2^30 List<int> digits; public int Length { get { return digits.Count; } } public int this[int index] { get { return digits[index]; } private set { digits[index] = value; } } public Num(int i) { digits = new List<int>(); while (i > 0) { digits.Add(i % digit_base); i /= digit_base; } } public static Num operator +(Num a, Num b) { Num n = new Num(); n.digits = new List<int>(); int l = Math.Min(a.Length,b.Length); int remainder = 0; for (int i = 0; i < l; i++) { n.digits.Add((a[i] + b[i] + remainder) % digit_base); remainder = (a[i] + b[i] + remainder) / digit_base; } Num longer = a.Length > b.Length ? a : b; for (; l < longer.Length; l++) { n.digits.Add((longer[l] + remainder) % digit_base); remainder = (longer[l] + remainder) / digit_base; } if (remainder > 0) n.digits.Add(remainder); return n; } public override string ToString() { StringBuilder sb = new StringBuilder(); for (int i = Length - 1; i >= 0; i--) { sb.AppendFormat("{0:D" + (digit_base.ToString().Length-1) + "}", this[i]); } return sb.ToString(); } }
Erlang
fib(0) -> 0; fib(1) -> 1; fib(N) -> fib(N-1) + fib(N-2).
Arithmetic version
fib(N) -> S = math:sqrt(5), round(math:pow(((1 + S) / 2), N) / S).
[divider]
VB.NET
Array oriented version
Dim i As Integer = 2 Dim sequencelength As Integer = 50 Dim fibonacci(sequencelength) As Integer fibonacci(0) = 0 fibonacci(1) = 1 While i <> sequencelength fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2) i += 1 End While
Recursive Version
Public Function fibonacci(ByVal i as integer) As Integer If i < 2 Then Return i Else Return fibonacci(i-1) + fibonacci(i-2) End If[divider]
PHP
function generate_fibonacci_sequence( $length ) { for( $l = array(0,1), $i = 2, $x = 0; $i < $length; $i++ ) $l[] = $l[$x++] + $l[$x]; return $l; }
Recursive version
function fib( $n ){ return ( $n < 2 ) ? $n : fib( $n-1 )+fib( $n-2 );}
OOP version
class fibonacci { public $Begin = 0; public $Next; public $Amount; public $i; public function __construct( $Begin, $Amount ) { $this->Begin= 0; $this->Next= 1; $this->Amount = $Amount; } public function _do() { for( $this->i = 0; $this->i < $this->Amount; $this->i++ ) { $Value = ( $this->Begin + $this->Next ); echo $this->Begin . ' + ' . $this->Next . ' = ' . $Value . '<br />'; $this->Begin = $this->Next; $this->Next = $Value; } } } $Fib = new fibonacci( 0, 6 ); echo $Fib->_do();
Alternate version
function fib($n) { return round(pow(1.6180339887498948482, $n) / 2.2360679774998); }[divider]
Java
public void run(int n) { if (n <= 0) { return; } run(n,1,0); } private void run(int n, int eax, int ebx) { n--; if (n == 0) { System.out.println(eax+ebx); return; } run(n,ebx,eax+ebx); }
Variations on the recursive version
/* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */ public long fib(long n) { if (n<2) { return n; } return fib(n-1) + fib(n-2); } public long fib2(long n) { return (n < 2) ? n : getValue(n - 1) + getValue(n - 2); }
Iterative version
/** * Source based on * http://20bits.com/2007/05/08/introduction-to-dynamic-programming/ * as at 9-May-2007 */ private long fibonacci(int n) { long n2 = 0; long n1 = 1; long tmp; for (int i=n ; i>2 ; i--) { tmp = n2; n2 = n1; n1 = n1 + tmp; } return n2 + n1; }
Simpler Iterative Version
/** * returns the Nth number in the Fibonacci sequence */ public int fibonacci(int N) { int lo = 0; int hi = 1; for (int i = 0; i < N; i++) { hi = lo + hi; lo = hi - lo; } return lo; }
Memoized version
private int[] fibs; // array for memoized fibonacci numbers public int fib(int n) { if (n < 2) { return n; } if (fibs == null) { // initialise array to first size asked for fibs = new int[n + 1]; } else if (fibs.length < n) { // expand array int[] newfibs = new int[n + 1]; // inefficient if looping through values of n System.arraycopy(fibs, 0, newfibs, 0, fibs.length); fibs = newfibs; } if (fibs[n] == 0) { fibs[n] = fib(n - 1) + fib(n - 2); } return fibs[n]; }
Iterative Memoized version
public int fib(int n) { if (n < 2) { return n; } int[] f = new int[n+1]; f[0] = 0; f[1] = 1; for(int i = 2;i<=n;i++) { f[i] = f[i-1] + f[i-2]; } return f[n]; }