数据结构考研复习 | Fibonacci数列的递归、数组、迭代(循环)实现及其时间复杂度

不念不忘少年蓝@ 2023-07-15 09:05 13阅读 0赞

#include <stdio.h>
    #include <iostream>
    
    int fibonacci_recurrence(int n) //递归实现
    {
        if (n == 0 or n == 1)
            return 1;
        else if(n > 1)
        {
            return fibonacci_recurrence(n-1)+fibonacci_recurrence(n-2);
        }
        else
            printf("error");
    }//递归实现的时间复杂度是O(2^n)
    
    int fibonacci_array(int n) //数组实现
    {
        //1,1,2,3,5,8,13,......
        if (n == 0 or n == 1)
            return 1;
        else if (n > 1)
        {
            int nums[n];
            nums[0] = 1;
            nums[1] = 1;
            for(int i = 2; i<=n; i++)
            {
                nums[i] = nums[i-1] + nums[i-2];
            }
            return nums[n];
        }
    }//数组实现的时间复杂度是O(n)
    
    int fibonacci_iteration(int n) //迭代(循环)实现
    {
        if (n == 0 or n == 1)
            return 1;
        else
        {
            int num1 = 1;
            int num2 = 1;
            int res;
            while(n > 1)
            {
                res = num1 + num2;
                num2 = num1;
                num1 = res;
                n--;
            }
            return res;
        }
    }//迭代实现的时间复杂度是O(n)
    
    int main()
    {
        int num;
        printf("input num:\n");
        scanf("%d",&num);
        if(num<0)
            printf("error");
        else
        {
            printf("递归实现：\n");
            printf("%d\n",fibonacci_recurrence(num));
            printf("数组实现：\n");
            printf("%d\n",fibonacci_array(num));
            printf("迭代(循环)实现：\n");
            printf("%d\n",fibonacci_iteration(num));
        }
        system("pause");
        return 0;
    }