面试题 10：斐波那契数列

Posted on

题目一：求斐波那契数列的第 n 项。
写一个函数，输入 n，求 Fibonacci 数列的第 n 项，斐波那契数列的定义如下：

  • 递归是在一个函数的内部调用这个函数自身；循环则是通过设置计算的初始值及终止条件，在一个范围内重复计算。
  • 如果没有特别的要求，应聘者可以尽量多采用递归的方法编程，可能引起：调用栈溢出。
  • 每一次函数调用，都需要在内存中分配空间以保存参数、返回地址、临时变量，而且往栈里压入数据和弹出数据都需要时间。
1
2
3
4
5
6
7
8
9
10
11
12
long long Fibonacci(unsigned int n) 
{
    if (n <= 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}


在这棵树中有很多节点是重复的。重复的节点数会随着 n 的增大而急剧增加，往往意味着计算量的增大。
只要想办法避免重复计算就行了，比如我们可以把已经得到的数列中间项保存起来。更简单的做法是把递归的算法用循环实现，从下往上计算。

题目二：青蛙跳台阶问题。
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

  • 第一次跳的时候有两种不同的选择：一是第一次只跳 1 级；二是第一次跳 2 级。

Source Code