كتابة fibonacci numbers

اخي الكريم سؤالك هذا موجود مثال في كتاب الأخ سلطان :

/index.php?showtopic=74297

تحت درس استدعاء التابع لنفسه

الف شكر اخوي.. لكن لم اجد درس بهذا الاسم في فهرس الكتاب

هل ممكن ان تذكر لي اسم الدرس بالضبط؟؟؟

الFibonacci Series هي سلسلة شهيرة و حلها سهل و دائما تكون مثالاً على Recursive Series أثناء تعلم الRecursion

و هذه طريقتها في حالة الRecursion

int fib(int);

void main()
{
	for(int i=1; i<8; i++)
  cout<<fib(i)<<", ";
	cout<<endl;
}	


int fib(int n)
{
	int tmp;
	if(n < 0)
  return -1;

	if(n==0)
  return 0;

	if(n==1)
  return 1;

	return fib(n-1) + fib(n-2);
  
}

رغم انهامن الامثلة الممتازة على الRecursion الا ان استخدام الRecursion لايجادها بعتبر خطئا فادحا

#include <stdio.h>
#include <conio.h>

void  main()
  {
   int n=8;
   int f1=0,f2=1,tmp=0,i;
//***********************
     clrscr();
     printf("%d  %d  ",f1,f2);
     for(i=2;i<n;i++)
       {
	tmp=f1;
	f1=f2;
	f2=tmp+f1;
	printf("%d  ",f2);
       }

   getch();

  }

استخدام الRecursion عامةً كارثة و لكن قدمت المثال بالRecursion عن عمد لأنني متأكد أن الهدف من هذا المثال هو شرح الRecursion فحاولت اختصار الطريق

طريقة الـ recursion تمشي .. لكن الـ Big-O لها هو (O(2^n

الطريقة الـ iterative ستكون (O(n

هناك طريقة يكون زمنها هو ((O(log(n لكنها تستخدم الـ matrices

حيث تاخذ matrix

[ 1 1 ]

[ 0 1 ]

و ترفعه الى الأس n-1 ثم تاخذ اول عنصر من الناتج, و سيكون هو الرقم المطلوب.

السر هو في طريقة رفم الماتركس الى الأس ..

for any matrix X,

X^n = 

X^(n/2) * X(n/2)  <-- if n is even
X^(n/2) * X(n/2) * X  <--- if n is odd

حيث نقوم في كل خطوة بتقسيم n على 2

هذا كود مكتوب بالجافا يحلها بهذه الطريقة .. كتبته قبل فترة لواجب في الكلية:

اولا هذا الماتركس المستخدم ...

/**
 * A simple (hard-coded) 2 by 2 matrix
 */
public class Matrix
{    
    /*
     The matrix is:
     [ a b ]
     [ c d ]
    */
    int a;
    int b;
    int c;
    int d;
    
    public Matrix( int pa, int pb, int pc, int pd )
    {
        a = pa;
        b = pb;
        c = pc;
        d = pd;
    }
    
    public static Matrix multiply( Matrix m1, Matrix m2 )
    {
        int na, nb, nc, nd;
        
        //calculate the result-of-the-multiplication matrix
        //um .... read your linear algebra book!! or whatever
        na = m1.a*m2.a + m1.b*m2.c;
        nb = m1.a*m2.b + m1.b*m2.d;
        nc = m1.c*m2.a + m1.d*m2.c;
        nd = m1.c*m2.b + m1.d*m2.d;        
        
        return new Matrix( na, nb, nc, nd );        
    }
    
    public Matrix power( int n )
    {
        return power(this, n);
    }
    
    private static Matrix power( Matrix m, int power )
    {
        //HACK!!!!! 
        //this maybe wrong, but it doesn't really matter, since we shouldn't be called with a 0 power anyway.
        if( power == 0 )
        {
            return new Matrix(1, 0, 1, 0);
        }
        if( power == 1 )
        {
            return m;
        }
        
        Matrix m2;        
        m2 = power( m, (power / 2) ); //magical division by two! log time :)
        
        if( power % 2 == 0 ) //power is even
        {
            return multiply( m2, m2 );
        }
        else //power is odd
        {
            return multiply( multiply(m2, m2), m );
        }
    }
}

و استخدامه ببساطة

    public static int Algorithm3( int n )
    {
        if( n == 0 ) return 0;
        if( n == 1 ) return 1;        
        
        /*  build a matrix that looks like
         * [ 1 1 ]
         * [ 1 0 ]
         * and raise it to the power of n-1
         */        
        Matrix m = new Matrix( 1, 1, 1, 0 );
        m = m.power(n-1);
        
        //get the first element of it, which will magically happen to be the nth Fibonacci number
        return m.a;
    }

مشكووووووووورين

romanof كتب:

رغم انهامن الامثلة الممتازة على الRecursion  الا ان استخدام الRecursion  لايجادها بعتبر خطئا فادحا

←

ليه بس :o

bashmohandes كتب:

استخدام الRecursion عامةً كارثة

←

انا كده مش فاهمة اول مرة اعرف المعلومة دي ممكن اعرف ليه

hasan_aljudy كتب:

طريقة الـ recursion تمشي .. لكن الـ Big-O لها هو (O(2^n

الطريقة الـ iterative ستكون (O(n

هناك طريقة يكون زمنها هو ((O(log(n for any matrix X,

←

انا اعرف في الcode cost بس ممكن توضيح يعني حسبتها ازاي

أعتقد المشكله في استخدام الRecursion - أعتقد لم اتأكد بعد - في مساحة الstack لأن كل مره يتم استدعاء الfunction يتم حفظ عنوان الرجوع وحجز متغيرات داخليه للfunction وكل هذا في الstack , ولن الfunction تقوم باستدعاء نفسها مثلا عدد n من المرات - حسب وظيفة الfunction - فانه يتم حجز متطلبات هذه الfunction في الذاكره عدد n من المرات و كل هذا في الstack المحدودة المساحه , فيمكن حدوث فيض عن الstack مثلا - تخمين - مما يؤدي الى الكتابه على قسم آخر data وينتج عنه خطأ في نتائج البرنامج ككل

ويمكن تكون في ال optimization في الكود لأن استدعاء داله والرجوع منها اضافة الى حجز متغيرات وتمرير القيم اليها أغلى بكثير من loop يستخدم نفس المتغيرات

الاجابه كلها تخمين وأنتظر اجابة موثوقه :D

مشكلة الـ recursion انه في كل خطوة يتم استدعاء خطوتين .. و في هاتين الخطوتين سيتم استدعاء 4 خطوات, و في هذه الاربع خطوات يتم استدعاء ثماني خطوات و بعدها 16, و بعدها 32 .. الخ ... كل مرة نضرب في 2 ... في خلال فترة قصيرة يزداد هذا الرقم بشكل كبير جدا!

السلام عليكم

فى الواقع الrecursion تعتبر اكثر طريقة مكلفة من ناحية المساحة والسرعة, حيث انك عندما تقوم بعملية recursion فى كل مرة تستدعى فيها الدالة يقوم البرنامج بحفظ المتغيرات وعنوان العودة وعنوان الstack بالاضافة للمتغيرات التى ترسل إلى الدالة, كل هذه الاشياء تضرب فى العدد n وهو عدد مرات إستدعاء الدالة, كى لا يحدث فيض فى الstack لابد ان يكون حجمه يساوى n*عدد المتغيرات الداخلية + عدد الparameter التى ترسل للدالة + حجم الstack المطلوب لباقى البرنامج..

اما بالنسبة للوقت فمن الصعب حسابة إذا لم تعرف ما تقوم به الداله ولكن بالتاكيد الrecursion ياخذ وقت اكبر كما انه ياخذ مساحة اكبر, المساحة يمكن حسابها بسهولة حيث انها O(n) وذلك لان كل إستدعاء للدالة ياخذ نفس كمية المساحة ...

والسلام عليكم

لاحظ اخي العزيز

return fib(n-1) + fib(n-2);

بدلا من ان تستفيد من القيم التي تمت حسابها في fib(n-2 ستقوم بحسابها من جديد في fib(n-1) الاتعتبر هذا اسرافا وتبديد للموارد

ألف شكر ليكوا على الشرح المستفيض ده

فهمت :D