从键盘输入一个整数n,求n阶斐波拉切级数

太过爱你忘了你带给我的痛 2023-07-19 04:55 11阅读 0赞

## 从键盘输入一个整数n,求n阶斐波拉切级数 ##

请用递归算法，从键盘输入一个小于25的整数n, 求斐波拉切级数。

求 n 阶斐波拉切级数的公式如 下：

当n=0或当n=1时    F （ n ） = 1

当n>1时              F （ n ）= F （ n-1 ） +F （ n-2 ）

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入</th> 
   <th>期待的输出</th> 
   <th>时间限制</th> 
   <th>内存限制</th> 
   <th>额外进程</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td>&nbsp; 
    <ol> 
     <li>10↵</li> 
    </ol></td> 
   <td>&nbsp; 
    <ol> 
     <li>89↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>测试用例 2</td> 
   <td>&nbsp; 
    <ol> 
     <li>23↵</li> 
    </ol></td> 
   <td>&nbsp; 
    <ol> 
     <li>46368↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

--------------------

### 题解 ###

**方法一 ：递推实现**

本题很简单，可以用一个数组a来存储斐波拉切级数，其中数组的下标对应n的值。预设a\[ 0 \]， a\[ i \]为0，即可自底向上推出n级的结果 a\[n\]。

#include <stdio.h>   //导入stdio.h库，里面包含输入输出函数
    
    int main() {
        int n;
        scanf("%d", &n);
    
        int a[26];
        a[0] = a[1] = 1;
        for (int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        printf("%d\n", a[n]);
    }

这是一个指数时间复杂度![\\bg\_white O(n)][bg_white O_n]的算法，线性时间复杂度，可以接受。

--------------------

**方法二：递归实现**

如果已经学过函数的话，可以递归实现：

#include <stdio.h>   //导入stdio.h库，里面包含输入输出函数
    
    /* 返回n级斐波拉契数 */
    int fib(int n) {
        if (n == 0 || n == 1)
            return 1;  //递归的终点
        return fib(n - 1) + fib(n - 2);  //递归调用自身
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        printf("%d\n", fib(n));
    }

当然，这里的递归没有优化，其效率和递归层次的承受度很低。不过对于本题AC够了。

这是一个指数时间复杂度![O(\\alpha ^n)][O_alpha _n]的算法，其中 ![\\bg\_white \\alpha = (\\sqrt\{5\} + 1) / 2][bg_white _alpha _ _sqrt_5_ _ 1_ _ 2]，对...它就是优美的黄金分割率1.618...不过算法的运行效率随n呈指数增长，实在是不够优美.../(ㄒoㄒ)/~~

--------------------

**其他方法 ：**

实在学有余力的同学还可以去搜搜将**斐波拉契数转化为矩阵的幂运算**，并且是**使用快速幂实现**。这是一个对数时间复杂度![O(log(n))][O_log_n]的算法，也是目前来说求斐波拉契数的可以实践的最快算法。

--------------------

本文给出了三种经典的计算斐波拉契数的算法，并且进行了简简单单的时间分析..**.对于时间复杂度和效率的分析初学者了解即可.**..主要是斐波拉契数列的问题太经典了，我遇见这个话题就忍不住多码了点字哈哈哈~

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

[bg_white O_n]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28n%29
[O_alpha _n]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28%5Calpha%20%5En%29
[bg_white _alpha _ _sqrt_5_ _ 1_ _ 2]: https://private.codecogs.com/gif.latex?%5Cbg_white%20%5Calpha%20%3D%20%28%5Csqrt%7B5%7D%20&plus;%201%29%20/%202
[O_log_n]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28log%28n%29%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/deb77f045bac408eac640a1e2f538a62.png