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

پیاده سازی الگوریتم فیبوناچی 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];
	}

منبع

نوتیف
امیدوارم مطالب نوتیف برایتان مفید واقع شده باشد. با عضویت در خبرنامه نوتیف مطالب تازه ما را در اینباکس خود داشته باشید. کانال ما در تلگرام هم راه سریع و مطمئنی برای آگاهی از مطالب ماست. *** من رضا حیدری مدیر وب سایت نوتیف هستم. همکنون مشغول به تحصیل در رشته کارشناسی ارشد نرم افزار بوده و به دنیای فناوری علاقه مندم به همین دلیل در نوتیف به دنبال نشر و ترویج موضوعات روز دنیای فناوری بخصوص موضوعات مرتبط با دنیای موبایل، اینترنت، کامپیوتر هستم. در کنار اینها گاهی هم گریزی به دیگر موضوعات مهم خواهیم زد که خالی از لطف نخواهد بود. با نوتیف همراه باشید بودن با شما افتخار بزرگی برای ماست.

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

2 + 15 =

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

Top