نوتیف

دنیایی رو به دانش و آگاهی

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

2 min read
برنامه نویسی

برنامه نویسی

در زیر مجموعه ای از کدهای مسئله سری فیبوناچی به زبان های مختلف با دو رویکرد بازگشتی و مبتنی بر تکرار ارائه شده است.

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];
	}

منبع

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.