caipengbo / Coding-Interviews

剑指offer
2 stars 0 forks source link

10. 斐波那契类问题 #8

Open caipengbo opened 5 years ago

caipengbo commented 5 years ago

简单的斐波那契问题,可以使用递归,但是容易导致递归栈溢出,可以使用循环替代

# 设置三个变量a,b,c,不断的进行迭代更新

int Fibonacci(int n) {
        if(n <= 1) return n;
        int a = 0, b = 1, c = 1;
        for(int i = 2; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        } 
        return c;
    }
caipengbo commented 5 years ago

小青蛙跳台阶问题

设台阶个数是n, 小青蛙每次只能跳 1 或 2 个台阶,问有多少种跳法?

n =1, f(n) = 1 n = 2, f(n) = 2

  1. 每次跳1个台阶,跳两次
  2. 一次跳2台阶

n = i(i > 2时) , 第一次跳就有两种选择:

  1. 先跳1个台阶, 剩下的次数f(i-1)
  2. 跳2个台阶,剩下的次数是f(i-2) f(i) = f(i-1) + f(i-2)

扩展

设台阶个数是n, 小青蛙每次只能跳 1, 2, 3....n 个台阶 数学归纳法:2的n-1次方

caipengbo commented 5 years ago

拼图问题

image