【剑指Offer】T10 斐波那契数列及其变种

斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数 n,请你输出斐波那契数列的第 n 项(从 0 开始,第 0 项为 0)。n<=39
循环实现:

long long Fibonacci(unsigned int n){
//    if(n == 0)
//        return 0;
//    if(n == 1)
//        return 1;
//    return Fibonacci(n-1) + Fibonacci(n - 2);

    int result[2] = {0, 1};
    if(n < 2){
        return result[n];
    }

    long long  fbn_1 = 0;
    long long  fbn_2 = 1;
    long long  fbn = 0;
    for(int i = 2; i <= n; i++){
        fbn = fbn_1 + fbn_2;
        fbn_1 = fbn_2;
        fbn_2 = fbn;
    }
    return fbn;

}

递归实现:

long long Fibonacci(unsigned int n){
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n - 2);
}
    

青蛙跳台阶

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

递归实现:

int jumpFloor(int number) {
        if(number < 2)
            return number;
 
        if(n >= 2){
            return FrogJump(n-1) + FrogJump(n-2);
        }
    }

非递归实现:

int jumpFloor(int number) {
        if(number < 2)
            return number;
 
        int fbn1 = 0;
        int fbn2 = 1;
        int fbn = 0;
 
        for(int i = 1; i <= number; i++){
            fbn = fbn1 + fbn2;
            fbn1 =fbn2;
            fbn2 = fbn;
        }
        return fbn;
}

题目 10-3 变态青蛙跳台阶 --- 没做

方块填充

我们可以用 2 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形,总共有多少种方法?

class Solution {
public:
    int rectCover(int number) {
        if(number <= 2){
            return number;
        }
         
        int method1 = 1;
        int method2 = 2;
        int method = 0;
         
        for(int i = 3; i <= number; i++){
            method = method1 + method2;
            method1 = method2;
            method2 = method;
        }
        return method;
    }
};

也是斐波那契数列,这种题如果要用迭代法,从底层开始分析,则需要更改迭代起始位置的,这里是从 3 开始

本文链接:https://ariser.cn/index.php/archives/149/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!