أعداد فيبوناتشي

من موسوعة حسوب

تشكّل أعداد فيبوناتشي Fibonacci numbers متتالية تدعى بمتتالية فيبوناتشي Fibonacci Sequence يكون كل عدد فيها مساويًا لمجموع العددين الذين يسبقانه في المتتالية، وتبدأ المتتالية بالعددين 0 و 1 : 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

كل عدد في هذه المتتالية (باستثناء العددين 0 و 1) هو ناتج العددين الذين يسبقانه، ويمكن تعريف هذه المتتالية رياضيًا باستخدام العلاقة التعاودية recurrence relation التالية: 

    Fn = Fn-1 + Fn-2

أما العددان 0 و 1 فيكونان ثابتين دائمًا: 

   F0 = 0 and F1 = 1

الطريقة التعاودية

يمكن استخدام دالة تعاودية للحصول على عدد فيبوناتشي في المكان المعيّن ضمن المتتالية، وتبين الأمثلة التالية طريقة تنفيذ هذه العملية:

  • C++‎:
int F(int n) {
	if (n <= 1) {
		return n;
	return F(n-1) + F(n-2);	
}

// اختبار الدالة السابقة
int main () 
{ 
    int n = 9; 
    cout << fib(n); 
    return 0; 
}
  • بايثون:
def F(n):
	if n <= 1:
		return n
	return F(n-1) + F(n-2)

# اختبار الدالة السابقة		
print(F(9))
  • جافا:
class fibonacci
{
	public static int F(int n)
	{
		if (n <= 1) {
			return n;
		return F(n-1)+ F(n-2);	
	}

// اختبار التابع السابق
	public static void main (String args[]) 
	{ 
		int n = 9; 
		System.out.println(F(n)); 
	}

تعطي الشيفرات السابقة المخرجات التالية: 

34

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار ‎O(n) = O(n-1) + O(n-2)‎ وهو تعقيد زمني أسّي exponential.

ويمكن ملاحظة أنّ هذه الطريقة تؤدي الكثير من العمل المتكرر (انظر شجرة التعاود في أدناه)؛ لذا يمكن القول أنّ هذه هي أسوأ طريقة للحصول على عدد فيبوناتشي في موقع معين ضمن المتتالية. 

                       fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

البرمجة الديناميكية

يمكن تجنب العمل المتكرر الذي تؤديه الطريقة السابقة بتخزين أعداد فيبوناتشي المحسوبة إلى حد معين.

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

  • C++‎:
#include<stdio.h> 

int fib(int n) 
{ 
/* إنشاء مصفوفة لتخزين أعداد فيبوناتشي */

// تحتوي المصفوفة على عنصر إضافي لمعالجة الحالة التي يكون فيها العدد المعطى صفرًا 
int f[n+2]; 
int i; 

/* العنصران الصفري والأول في المتتالية هما 0 و 1 */
f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
	/* جمع الرقمين السابقين في المتتالية وتخزين الناتج */
	f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
} 

int main () 
{ 
int n = 9; 
printf("%d", fib(n)); 
return 0; 
}
  • بايثون:
def fibonacci(n): 
	
	# أول عددين في متتالية فيبوناتشي هما 0 و 1 
	FibArray = [0, 1] 
	
	while len(FibArray) < n + 1: 
		FibArray.append(0) 
	
	if n <= 1: 
		return n 
	else: 
		if FibArray[n - 1] == 0: 
			FibArray[n - 1] = fibonacci(n - 1) 

		if FibArray[n - 2] == 0: 
			FibArray[n - 2] = fibonacci(n - 2) 
			
	FibArray[n] = FibArray[n - 2] + FibArray[n - 1] 
	return FibArray[n] 
	
print(fibonacci(9))
  • جافا:
class fibonacci 
{ 
static int fib(int n) 
	{ 
	/* إنشاء مصفوفة لتخزين أعداد فيبوناتشي */
	
	// تحتوي المصفوفة على عنصر إضافي لمعالجة الحالة التي يكون فيها العدد المعطى صفرًا 
	int f[] = new int[n+2]; 
	int i; 
	
	/* العنصران الصفري والأول في المتتالية هما 0 و 1*/
	f[0] = 0; 
	f[1] = 1; 
	
	for (i = 2; i <= n; i++) 
	{ 
	/* جمع الرقمين السابقين في المتتالية وتخزين الناتج  */
		f[i] = f[i-1] + f[i-2]; 
	} 
	
	return f[n]; 
	} 
	
	public static void main (String args[]) 
	{ 
		int n = 9; 
		System.out.println(fib(n)); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية: 

34

يمكن تقليل المساحة التي تستهلكها الطريقة السابقة عن طريق تخزين العددين السابقين فقط؛ وذلك لأنّهما كل ما نحتاجه للحصول على عدد فيبوناتشي في المتتالية.

  • C++‎:
#include<stdio.h> 
int fib(int n) 
{ 
int a = 0, b = 1, c, i; 
if( n == 0) 
	return a; 
for (i = 2; i <= n; i++) 
{ 
	c = a + b; 
	a = b; 
	b = c; 
} 
return b; 
} 

int main () 
{ 
int n = 9; 
printf("%d", fib(n)); 
getchar(); 
return 0; 
}
  • بايثون:
def fibonacci(n): 
	a = 0
	b = 1
	if n < 0: 
		print("Incorrect input") 
	elif n == 0: 
		return a 
	elif n == 1: 
		return b 
	else: 
		for i in range(2,n+1): 
			c = a + b 
			a = b 
			b = c 
		return b 

# اختبار الدالة السابقة 

print(fibonacci(9))
  • جافا:
class fibonacci 
{ 
	static int fib(int n) 
	{ 
		int a = 0, b = 1, c; 
		if (n == 0) 
			return a; 
		for (int i = 2; i <= n; i++) 
		{ 
			c = a + b; 
			a = b; 
			b = c; 
		} 
		return b; 
	} 

	public static void main (String args[]) 
	{ 
		int n = 9; 
		System.out.println(fib(n)); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)‎.

استخدام المصفوفات

يمكن الحصول على عدد فيبوناتشي في الموقع (n+1) عن طريق ضرب المصفوفة M = {{1,1}, {1,0}}‎ بنفسها n من المرات (بمعنى آخر رفع المصفوفة M إلى الأس n)، ويكون هذا العدد موجودًا في الصف 0 والعمود 0 في المصفوفة الناتجة.

يمكن التعبير عن المصفوفة رياضيًا باستخدام التعبير التالي:

تعرض الأمثلة التالية كيفية تنفيذ طريقة المصفوفات في عدد من لغات البرمجة:

  • C++‎:
#include <stdio.h> 

/* تضرب هذه الدالة المساعدة المصفوفتين المعطاتين ذواتي الحجم 2*2 بعضهما ببعض، ثم تضع النتيجة في المصفوفة الأولى */


void multiply(int F[2][2], int M[2][2]); 

/* تحسب هذه الدالة المساعدة المصفوفة الأولى وترفعها إلى الأس المعطى وتضع الناتج في المصفوفة الأولى مجدّدًا
يمكن استخدام هذه الدالة في حساب عدد فيبوناتشي فقط ولا يمكن الاستفادة منها كدالة قوة عامة */
void power(int F[2][2], int n); 

int fib(int n) 
{ 
int F[2][2] = {{1,1},{1,0}}; 
if (n == 0) 
	return 0; 
power(F, n-1); 

return F[0][0]; 
} 

void multiply(int F[2][2], int M[2][2]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

void power(int F[2][2], int n) 
{ 
int i; 
int M[2][2] = {{1,1},{1,0}}; 

// ضرب المصفوفة بالمصفوفة ‎{{1,0},{0,1}}‎
// n-1 مرة
for (i = 2; i <= n; i++) 
	multiply(F, M); 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
int n = 9; 
printf("%d", fib(n)); 
getchar(); 
return 0; 
}
  • بايثون:
# تحسب هذه الدالة المساعدة المصفوفة الأولى
# وترفعها إلى الأس المعطى
# وتضع الناتج في المصفوفة الأولى مجدّدًا
# يمكن استخدام هذه الدالة في حساب عدد فيبوناتشي فقط
# ولا يمكن الاستفادة منها كدالة قوة عامة
def fib(n): 
	F = [[1, 1], 
		[1, 0]] 
	if (n == 0): 
		return 0
	power(F, n - 1) 
	
	return F[0][0] 


# تضرب هذه الدالة المساعدة المصفوفتين المعطاتين
# ذواتي الحجم 2*2 بعضهما ببعض،
# ثم تضع النتيجة في المصفوفة الأولى
def multiply(F, M): 

	x = (F[0][0] * M[0][0] +
		F[0][1] * M[1][0]) 
	y = (F[0][0] * M[0][1] +
		F[0][1] * M[1][1]) 
	z = (F[1][0] * M[0][0] +
		F[1][1] * M[1][0]) 
	w = (F[1][0] * M[0][1] +
		F[1][1] * M[1][1]) 
	
	F[0][0] = x 
	F[0][1] = y 
	F[1][0] = z 
	F[1][1] = w 

def power(F, n): 

	M = [[1, 1], 
		[1, 0]] 

	# n - 1 times multiply the 
	# matrix to {{1,0},{0,1}} 
	for i in range(2, n + 1): 
		multiply(F, M) 

# اختبار الدوال السابقة
if __name__ == "__main__": 
	n = 9
	print(fib(n))
  • جافا:
class fibonacci 
{ 
	
	static int fib(int n) 
	{ 
	int F[][] = new int[][]{{1,1},{1,0}}; 
	if (n == 0) 
		return 0; 
	power(F, n-1); 
	
	return F[0][0]; 
	} 
	
	/* تضرب هذه الدالة المساعدة المصفوفتين المعطاتين ذواتي الحجم 2*2 بعضهما ببعض، ثم تضع النتيجة في المصفوفة الأولى */
	static void multiply(int F[][], int M[][]) 
	{ 
	int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
	int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
	int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
	int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
	
	F[0][0] = x; 
	F[0][1] = y; 
	F[1][0] = z; 
	F[1][1] = w; 
	} 

	/* تحسب هذه الدالة المساعدة المصفوفة الأولى وترفعها إلى الأس المعطى وتضع الناتج في المصفوفة الأولى مجدّدًا
يمكن استخدام هذه الدالة في حساب عدد فيبوناتشي فقط ولا يمكن الاستفادة منها كدالة قوة عامة */
	static void power(int F[][], int n) 
	{ 
	int i; 
	int M[][] = new int[][]{{1,1},{1,0}}; 
	
	// ضرب المصفوفة بالمصفوفة ‎{{1,0},{0,1}}‎
// n-1 مرة
	for (i = 2; i <= n; i++) 
		multiply(F, M); 
	} 
	
	/* اختبار الدوال السابقة */
	public static void main (String args[]) 
	{ 
	int n = 9; 
	System.out.println(fib(n)); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)‎.

طريقة المصفوفات المحسنة

يمكن تحسين الطريقة السابقة باستخدام عملية ضرب تعاودية للحصول على ناتج رفع المصفوفة M إلى الأس n في الطريقة السابقة.

  • C++‎:
#include <stdio.h> 

void multiply(int F[2][2], int M[2][2]); 

void power(int F[2][2], int n); 

/* تعيد الدالة عدد فيبوناتشي في الموقع المعطى من المتتالية */
int fib(int n) 
{ 
int F[2][2] = {{1,1},{1,0}}; 
if (n == 0) 
	return 0; 
power(F, n-1); 
return F[0][0]; 
} 

/* نسخة محسنة من الدالة التي وردت في الطريقة السابقة */
void power(int F[2][2], int n) 
{ 
if( n == 0 || n == 1) 
	return; 
int M[2][2] = {{1,1},{1,0}}; 

power(F, n/2); 
multiply(F, F); 

if (n%2 != 0) 
	multiply(F, M); 
} 

void multiply(int F[2][2], int M[2][2]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
int n = 9; 
printf("%d", fib(9)); 
getchar(); 
return 0; 
}
  • بايثون:
# تعيد الدالة عدد فيبوناتشي في الموقع المعطى من المتتالية
def fib(n): 
	
	F = [[1, 1], 
		[1, 0]] 
	if (n == 0): 
		return 0
	power(F, n - 1) 
		
	return F[0][0] 
	
def multiply(F, M): 
	
	x = (F[0][0] * M[0][0] +
		F[0][1] * M[1][0]) 
	y = (F[0][0] * M[0][1] +
		F[0][1] * M[1][1]) 
	z = (F[1][0] * M[0][0] +
		F[1][1] * M[1][0]) 
	w = (F[1][0] * M[0][1] +
		F[1][1] * M[1][1]) 
	
	F[0][0] = x 
	F[0][1] = y 
	F[1][0] = z 
	F[1][1] = w 
		
# نسخة محسّنة من الدالة التي وردت في الطريقة السابقة
def power(F, n): 

	if( n == 0 or n == 1): 
		return; 
	M = [[1, 1], 
		[1, 0]]; 
		
	power(F, n // 2) 
	multiply(F, F) 
		
	if (n % 2 != 0): 
		multiply(F, M) 
	
# اختبار الدوال السابقة
if __name__ == "__main__": 
	n = 9
	print(fib(n))
  • جافا:
class fibonacci 
{ 
	/* تعيد الدالة عدد فيبوناتشي في الموقع المعطى من المتتالية */
	static int fib(int n) 
	{ 
	int F[][] = new int[][]{{1,1},{1,0}}; 
	if (n == 0) 
		return 0; 
	power(F, n-1); 
	
	return F[0][0]; 
	} 
	
	static void multiply(int F[][], int M[][]) 
	{ 
	int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
	int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
	int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
	int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
	
	F[0][0] = x; 
	F[0][1] = y; 
	F[1][0] = z; 
	F[1][1] = w; 
	} 
	/* نسخة محسّنة من الدالة التي وردت في الطريقة السابقة */
	static void power(int F[][], int n) 
	{ 
	if( n == 0 || n == 1) 
	return; 
	int M[][] = new int[][]{{1,1},{1,0}}; 
	
	power(F, n/2); 
	multiply(F, F); 
	
	if (n%2 != 0) 
	multiply(F, M); 
	} 
	
	/* اختبار الدوال السابقة */
	public static void main (String args[]) 
	{ 
		int n = 9; 
	System.out.println(fib(n)); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(Logn)‎.

استخدام الصيغة الرياضية

تستخدم هذه الطريقة الصيغة الرياضية التالية لحساب عدد فيبوناتشي في الموقع n من المتتالية: 

Fn = {[(√5 + 1)/2] ^ n} / √5

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

  • C++‎:
#include<iostream> 
#include<cmath> 

int fib(int n) { 
double phi = (1 + sqrt(5)) / 2; 
return round(pow(phi, n) / sqrt(5)); 
} 

// اختبار الدالة السابقة 
int main () 
{ 
int n = 9; 
std::cout << fib(n) << std::endl; 
return 0; 
} 
//This code is contributed by Lokesh Mohanty.
  • بايثون:
from math import pow, sqrt

def fib(n):
	phi = (1 + sqrt(5)) / 2
	return round(pow(phi, n) / sqrt(5))
	
print(fib(n))
  • جافا:
import java.util.*; 

class GFG { 

static int fib(int n) { 
double phi = (1 + Math.sqrt(5)) / 2; 
return (int) Math.round(Math.pow(phi, n) 
						/ Math.sqrt(5)); 
} 

// اختبار الدالة السابقة
public static void main(String[] args) { 
		int n = 9; 
	System.out.println(fib(n)); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية: 

34

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(1)‎.

التحقق من وجود عدد معين في متتالية فيبوناتشي

يمكن التحقق من وجود عدد معين في متتالية فيبوناتشي بحساب أعداد فيبوناتشي إلى أن نصل إلى العدد الذي يكون أكبر من العدد المعطى أو مساويًا له.

تتمتع أعداد فيبوناتشي بخاصية يمكن الاستفادة منها في التحقق من وجود عدد معين في المتتالية، إذ يكون العدد ضمن متتالية فيبوناتشي إذا وفقط إذا كان ناتج أحد التعبيرين التاليين أو كلاهما مربّعًا كاملًا: (‎5n2 + 4‎) و (‎5n2 - 4).

  • C++‎:
#include <iostream> 
#include <math.h> 
using namespace std; 

// دالة مساعدة تعيد قيمة صحيحة إن كان العدد المعطى مربعًا كاملًا
bool isPerfectSquare(int x) 
{ 
	int s = sqrt(x); 
	return (s*s == x); 
} 

// تعيد الدالة قيمة صحيحة إن كان العدد المعطى موجودًا في متتالية فيبوناتشي
// وتعيد قيمة خاطئة فيما عدا ذلك
bool isFibonacci(int n) 
{ 
	// إن تحققت العلاقة المذكورة أعلاه فالعدد موجود في متتالية فيبوناتشي
	return isPerfectSquare(5*n*n + 4) || 
		isPerfectSquare(5*n*n - 4); 
} 

// دالة مساعدة لاختبار الدوال السابقة
int main() 
{ 
for (int i = 1; i <= 10; i++) 
	isFibonacci(i)? cout << i << " is a Fibonacci Number \n": 
					cout << i << " is a not Fibonacci Number \n" ; 
return 0; 
}
  • بايثون:
import math 

# دالة مساعدة تعيد قيمة صحيحة إن كان العدد المعطى مربّعًا كاملاً
def isPerfectSquare(x): 
	s = int(math.sqrt(x)) 
	return s*s == x 

# تعيد الدالة قيمة صحيحة إن كان العدد المعطى موجودًا في متتالية فيبوناتشي
# وتعيد قيمة خاطئة فيما عدا ذلك
def isFibonacci(n): 

	# إن تحققت العلاقة المذكورة أعلاه فالعدد موجود في متتالية فيبوناتشي 
	return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4) 
	
# اختبار الدوال السابقة 
for i in range(1,11): 
	if (isFibonacci(i) == True): 
		print i,"is a Fibonacci Number"
	else: 
		print i,"is a not Fibonacci Number "
  • جافا:
class GFG 
{ 
	// دالة مساعدة تعيد قيمة صحيحة إن كان العدد المعطى مربعًا كاملًا 
	static boolean isPerfectSquare(int x) 
	{ 
		int s = (int) Math.sqrt(x); 
		return (s*s == x); 
	} 
	
	// تعيد الدالة قيمة صحيحة إن كان العدد المعطى موجودًا في متتالية فيبوناتشي
	// وتعيد قيمة خاطئة فيما عدا ذلك 
	static boolean isFibonacci(int n) 
	{ 
		// إن تحققت العلاقة المذكورة أعلاه فالعدد موجود في متتالية فيبوناتشي 
		return isPerfectSquare(5*n*n + 4) || 
			isPerfectSquare(5*n*n - 4); 
	} 

	// اختبار التوابع السسابقة
	public static void main(String[] args) 
	{ 
		for (int i = 1; i <= 10; i++) 
			System.out.println(isFibonacci(i) ? i + " is a Fibonacci Number" : 
												i + " is a not Fibonacci Number"); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية: 

1 is a Fibonacci Number
2 is a Fibonacci Number
3 is a Fibonacci Number
4 is a not Fibonacci Number
5 is a Fibonacci Number
6 is a not Fibonacci Number
7 is a not Fibonacci Number
8 is a Fibonacci Number
9 is a not Fibonacci Number
10 is a not Fibonacci Number

مصادر

مجلوبة من «https://wiki.hsoub.com/index.php?title=Algorithms/Fibonacci_numbers&oldid=29065»