عرض مصدر Algorithms/Fibonacci numbers

<noinclude>{{DISPLAYTITLE:أعداد فيبوناتشي}}</noinclude>
تشكّل أعداد فيبوناتشي Fibonacci numbers متتالية تدعى بمتتالية فيبوناتشي Fibonacci Sequence يكون كل عدد فيها مساويًا لمجموع العددين الذين يسبقانه في المتتالية، وتبدأ المتتالية بالعددين <code>0</code> و <code>1</code> :

<source lang="text">0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....</source>
كل عدد في هذه المتتالية (باستثناء العددين <code>0</code> و <code>1</code>) هو ناتج العددين الذين يسبقانه، ويمكن تعريف هذه المتتالية رياضيًا باستخدام العلاقة التعاودية recurrence relation التالية:

<source lang="text"> Fn = Fn-1 + Fn-2</source>
أما العددان 0 و 1 فيكونان ثابتين دائمًا:

<source lang="text"> F0 = 0 and F1 = 1</source>
== الطريقة التعاودية ==

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

* C++‎:

<source lang="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; 
} </source>
* بايثون:

<source lang="python">def F(n):
	if n <= 1:
		return n
	return F(n-1) + F(n-2)

# اختبار الدالة السابقة		
print(F(9))</source>
* جافا:

<source lang="java">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)); 
	} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">34</source>
=== التعقيد الزمني ===

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

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

<source lang="text">                       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)</source>
== البرمجة الديناميكية ==

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

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

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">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)) 
</source>
* جافا:

<source lang="java">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)); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">34</source>
يمكن تقليل المساحة التي تستهلكها الطريقة السابقة عن طريق تخزين العددين السابقين فقط؛ وذلك لأنّهما كل ما نحتاجه للحصول على عدد فيبوناتشي في المتتالية.

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">
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)) </source>
* جافا:

<source lang="java">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)); 
	} 
} 
</source>
=== التعقيد الزمني ===

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

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

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

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

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

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">
# تحسب هذه الدالة المساعدة المصفوفة الأولى
# وترفعها إلى الأس المعطى
# وتضع الناتج في المصفوفة الأولى مجدّدًا
# يمكن استخدام هذه الدالة في حساب عدد فيبوناتشي فقط
# ولا يمكن الاستفادة منها كدالة قوة عامة
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)) 
</source>
* جافا:

<source lang="java">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)); 
	} 
} 
</source>
=== التعقيد الزمني ===

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

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

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

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">
# تعيد الدالة عدد فيبوناتشي في الموقع المعطى من المتتالية
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)) </source>
* جافا:

<source lang="java">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)); 
	} 
} </source>
=== التعقيد الزمني ===

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

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

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

<source lang="text">Fn = {[(√5 + 1)/2] ^ n} / √5</source>
تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

* C++‎:

<source lang="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. 
</source>
* بايثون:

<source lang="python">from math import pow, sqrt

def fib(n):
	phi = (1 + sqrt(5)) / 2
	return round(pow(phi, n) / sqrt(5))
	
print(fib(n))</source>
* جافا:

<source lang="java">
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)); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">34</source>
=== التعقيد الزمني ===

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

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

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

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">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 "
</source>
* جافا:

<source lang="java">
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"); 
	} 
} 
</source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">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</source>
== مصادر ==

* صفحة [https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ Program for Fibonacci numbers] في توثيق الخوارزميات في موقع GeeksforGeeks.
* صفحة [https://www.geeksforgeeks.org/check-number-fibonacci-number/ How to check if a given number is Fibonacci number?] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]