斐波那契数列和应用举例我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

本文主要是介绍斐波那契数列和应用举例我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先介绍一下斐波那契数列

     斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。

对于斐波那契数列很明显的递推公式为：F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

利用递归实现：

int Fibonacci(int n){if（n==2||n==1）return 1;else if (n==0)return 0;elsereturn   Fibonacci(n-1)+ Fibonacci(n-2);}

利用递归方式实现时空间复杂度较高

方法二

int Fibonacci(int n){
int a=1,b=1,result=0;
if（n==2||n==1）return 1;else if (n==0)return 0;else
{
for（int i=3;i<=n;i++）
{ result=a+b;
a=b;
b=result;
}
return result;
}
}

对于矩形覆盖问题可以利用转换为斐波那契数列问题处理

非递归方法：

 int rectCover(int number) {int a=1,b=2,result=0;if(number==1)return 1;else if(number==2)return 2;else {for(int i=3;i<=number;i++){result=a+b;a=b;b=result;}}return result;}

递归方法：

 int rectCover(int number) {int a=1,b=2,result=0;if(number==1)return 1;else if(number==2)return 2;else {return  rectCover(number-1)+ rectCover(number-2);}

这篇关于斐波那契数列和应用举例我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---