斐?斐波那契数列?

斐波那契数列大家知道吧?

指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:

F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

很简单,因为后一项等于前两项之和嘛

public class Solution {
    public int Fibonacci(int n) {
        int a = 1, b = 1, c = 0;
        int i = 2;
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        while(i < n){
            c = a + b;
            a = b;
            b = c;
            i++;
        }
        return c;
    }
}

现在还有几个有趣的题目:

一、

题目:

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

思路:

假设第一次跳的1阶,那么剩下n-1级台阶,共有f(n-1)种跳法,

假设第一次跳的2阶,那么剩下n-2级台阶,共有f(n-2)种跳法,

则总跳法数为:f(n) = f(n-1) + f(n-2)

又有当只有1级台阶时,只有1种跳法,

当只有2级台阶时,有2种跳法,即:

f(1) = 1

f(2) = 2

所以可以得到一个数列:

      | 1,n = 1

f(n) = | 2,n = 2

       | f(n - 1) + f(n - 2), n > 2且n为整数

可以看出这就是一个斐波那契数列。。。

二、

题目:

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

思路:

第一次可以竖着摆放或者横着摆放,

若第一次摆放1*2的小矩阵(即竖着摆放),剩下2*(n-1),摆放方式有:f(n-1)种

若第一次摆放2*1的小矩阵(即横着摆放),则该矩形下方的摆法已确定(只能横着摆),则剩下2*(n-2),摆放方式有:f(n-2)种

 

则综上,摆放方式总共有f(n) = f(n-1) + f(n-2)

嗯。。。可以看出还是一个斐波那契数列。。。

代码:

public class Solution{
    public int RectCover(int target) {
    	if(target <= 0) {
    		return 0;
    	}
    	if(target == 1) {
    		return 1;
    	}
    	if(target == 2) {
    		return 2;
    	}
    	int a = 1, b = 2, c = 0;
    	for(int i = 3; i <= target; i++) {
    		c = a + b;
    		a = b;
    		b = a;
    	}
    	return c;
    }
}

另外这个题还可以扩展,例如替换成用3*1的小矩形无重叠地覆盖一个3*n的大矩形,或者用4*1的小矩形无重叠地覆盖一个4*n的大矩形,再比如用m*1的小矩形无重叠地覆盖一个m*n的大矩形,得到的规律都是一样的:

       | 1,n = 1 
f(n) = | 2,n = 2       
       | f(n - 1) + f(n - m), n > 2且n为整数, m >=2 且m为整数

 

 

 

文章已创建 65

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部