C语言算法-斐波那契数列(递归和非递归的求法)

浅浅的花香味﹌ 2022-05-18 02:53 141阅读 0赞

该程序可以直接保存运行

共三个不同函数,分别对应斐波那契数列的三种不同求法

/* 程序说明: 由于斐波纳挈数列是以兔子的繁殖引入的，因此也叫“兔子数列”。 它指的是这样一个数列：0,1,1,2,3,5,8,13......从这组数可以很 明显看出这样一个规律：从第三个数开始，后边一个数一定是在其 之前两个数的和。在数学上，斐波纳挈数列可以以这样的公式表示： F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2),(n>=2) */
    
    #include "stdio.h" 
    #include "assert.h"
    
    int FeiBoNaQi( int n );  //返回斐波那契第n位 
    int *FiB2(int n);//返回斐波那契数组的初始位置 指针应用
    int FiB3(int n); //返回第n位斐波那契数 
    
    int main()
    {
        int input;
        printf("Please input <10: ");
        scanf("%d",&input);  if(input >= 10)input=10;//防止数值过大 
        printf("The result is ");
    
        int i;
        for(i=0; i<input; i++)
        printf("%d ",FeiBoNaQi(i));
    
        printf("\n----以上是递归算法----------------\n");  
    
        int *array = FiB2(input);
    
        for(i=0; i<input; i++)
        {
            printf("%d ",*(array+i));
        }
        printf("\n----以上是非递归使用数组方法----------\n");
    
        printf("the %d = %d",input,FiB3(input));        
    
        printf("\n----以上是非递归使用数组方法----------\n");       
    
    
        printf("\nhello world! \n");     
        return 0;
    } 
    
    int FeiBoNaQi( int n )
    { // 斐波那契数列 递归计算 
        //递归算法 
        assert(n >= 0);
    
        if(n==1 || n==0) return n; 
        else
        {
            return FeiBoNaQi(n-1) + FeiBoNaQi(n-2);
        }
    
    // return n <=1 ? n : (FeiBoNaQi(n-1) + FeiBoNaQi(n-2));//等价于上一段程序 
    } 
    /* 该函数时间复杂度的分析: 例如:求第十个斐波那契数列 需要计算 10 -> (9,8) 9->(8,7) 8->(7,6) 8->(7,6) 7(6,5) 6(5,4) 5(4,3) 其中存在大量重复数据的使用 时间复杂度 ----- O(2^N) */ 
    /*--------------------------------------------------------------*/ 
    int *FiB2(int n)
    {   // 斐波那契数列 非递归方法 时间复杂度O(n)--空间复杂度O(n) 
        assert(n>=0);
        int *array;//注意此处不能赋值 
        array[0]=0;
        array[1]=1;
    
        int i=2;
        for(i; i<n ; i++)
        {
            array[i] = array[i-1] + array[i-2];
        }
        return array;   
    } 
    
    /*--------------------------------------------------------------*/
    int FiB3(int n)
    {  // 斐波那契数列 非递归方法 时间复杂度O(n)--空间复杂度O(1) 
        assert(n>=0);
        int first=0;
        int second=1;
        int next = first;
    
        if(n==2) return second; 
        int i;
        for(i=2;i<n;i++)
        {
       //0 1
            next = first + second;//1 
            first = second;//1
            second = next;//1
        }   
        return next;
    }