给出计算斐波那些数的算法，分别用递归和非递归算法实现，并给出

[问答题]

给出计算斐波那些数的算法，分别用递归和非递归算法实现，并给出两种算法的时间复杂度。

丨太阳与月亮丨

递归求解，复杂度O(2^n)

int Fibonacci(int n)
{
··if( n == 1 || n == 2) 
 ···return 1;
··else
 ···return Fibonacci(n-1)+Fibonacci(n-2);  }

非递归求解，复杂度O(n)

int Fibonacci(int n) {
··if( n == 1 || n == 2) 
 ···return 1;
··else
 ·{
    int result=0;
    int temp1=1;
    int temp2=1;
    for(int i=2;i<n;i++)
    {
         result=temp1+temp2;
        temp1=temp2;
        temp2=result;
    }
   } 
    return result;
}

编辑于 2017-01-27 10:27:06 回复(0)