问题:兔子问题,假定最初有新生的雌雄兔子一对,除了本月新生的兔子外,每队兔子每个月都可以生出一对新的兔子;而且假定兔子永远不会死,请问n个月后一共有多少对兔子?
设满n个月时兔子对数为fn,其中当月新生兔子数目为Nn对,第n-1个月存活的兔子数目设为On对,则有fn=Nn+On;
而On=fn-1,Nn=fn-2,由此得到fn=fn-1+fn-2(n>=3);且f1=1,f2=1;(画图观察)
例1:一个楼梯有n级,每次可以跨上1级或2级,求从楼梯的最低端登到最顶端的不同的方法数。
第一步如果跨1级还有n-1级要爬,方法数fn-1,如果跨2级还有n-2要爬方法数fn-2;
2,使用多米诺(dominos)骨牌-即1*2的小方格,覆盖2 *n的方格棋盘有多少种不同的方式?
设方法数为Sn或者被横着覆盖,或者被竖着覆盖,
横着情况余下的就(n-2)的方格,则方法数Sn-2,竖着(n-1),方法数Sn-1,
初值条件S1=1(n=1),S2=2(n=2);
3,你有1-n的n条边,让你拿走尽量少的边,使得剩下的边,任意取三个都不能组成三角形。
让剩下的边不能组成三角形,那就让剩下的边构成斐波那契数列