斐波拉切数列--实例

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

2.解题思路：
解法一：排列组合，假设竖方块的数量是y，横方块的数量是x，可知x+2y=target,用for循环遍历x，并用递归的方法对数量为x的横方块和数量为y的竖方块进行排列组合。（比较复杂）
解法二：斐波那契数列，经过举例发现该问题符合菲波那切数列的特点。

3.代码：
解法一：

public class Solution {
    public int RectCover(int target) {
        int x;
        int y;
        int count = 0;
        if(target == 0){
            return 0;
        }
        for(x = 0; x <= target; x++){
            y = (target - x)/2;
            if((target -x)%2 != 0){
                count = count + fseqence(++x,y);
            }
            else {
                count = count + fseqence(x,y);
            }
        }
        return count;
    }
    
    public int fseqence(int x, int y){
        if(x==0||y==0)
            return 1;
        else 
            return fseqence(x-1,y)+fseqence(x,y-1);
    }
}

解法二：

public int RectCover(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 3; i <= n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}

一、跳台阶：
1.题目描述：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
2.解题思路：斐波那契数列。
3.代码：

public int JumpFloor(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 1;
    for (int i = 2; i < n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}

斐波拉切数列--实例

相关推荐