《剑指Offer》-07递归与循环

发表于 | 分类于

tip:md中插表情，可用字符/符号的Unicode编码 比如😀😎🙅😱👽也可以替代一些icon，减少网页图片

斐波那契数列

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Fibonacci(n)
{
    // write code here
    if(n===0) return 0;
    if(n===1) return 1;
    var m1=0,
        m2=1;
    for(let i=2;i<=n;i++){
        if(m2>m1){
            m1+=m2;
        }else{
            m2+=m1;
        }
    }
    return Math.max(m1,m2);
}

总结：
斐波那契数列的标准公式为：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function jumpFloor(number)
{
    // write code here
    if(number===1) return 1;
    if(number===2) return 2;
    var m1=1,
        m2=2;
    for(let i=3;i<=number;i++){
        if(m2>m1){
            m1+=m2;
        }else{
            m2+=m1;
        }
    }
    return Math.max(m1,m2);
}

总结：
这题其实与上一题一样：
🐸跳1阶，有1种情况；
🐸跳2阶，有2种情况；
🐸跳3阶，有3种情况；
🐸跳4阶，有5种情况；
可发现规律，其实就是斐波那契数列
f(n)=f(n-1)+f(n-2)

变态跳台阶

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

1
2
3
4
5
function jumpFloorII(number)
{
    // write code here
    return Math.pow(2,(number-1))
}

总结：
n级台阶
跳1级，剩下n-1级，有f(n-1)种方法；
跳2级，剩下n-2，有f(n-2)种方法；
跳3级，剩下n-3，有f(n-3)种方法；
。。。
跳n-1级，剩下1级，有f(1)种方法；
总的方法相加：
f(n)=f(n-1)+f(n-2)+…+f(1)=2*f(n-1)，找到规律

矩形覆盖

题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法：
1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function rectCover(number)
{
    // write code here
    if(number===0){
        return 0;
    }
    if(number===1){
        return 1;
    }
    if(number===2){
        return 2;
    }
    var m1=1,
        m2=2;
    for(var i=3;i<=number;i++){
        if(m2>m1){
            m1+=m2;
        }else{
            m2+=m1;
        }
    }
    return Math.max(m1,m2);
}

总结：遇事不决就枚举，还是斐波那契数列

0%