无标题文章

青蛙跳阶。

有个青蛙跳上了n阶台阶，每次可跳一阶或两阶，问有多少种跳法？

这题很有意思，刚开始第一反应是穷举，通过两个for循环将所有组合方法列出来，然后计数，如下：

int jumpFloor(int number) {

int i,j,tmp,sum=0;

for(i=0;i<=number;i++){

for(j=0;j<=number/2;j++){

tmp = i+2*j;

if(tmp==number){

sum+=cx(i+j,i);

}

其中cx是组合数学里的自定义函数，作用是计算组合数量。刚开始写到一半时发现就算低阶的时候程序运行特别慢，仔细检查后发现一个很有趣的现象，由于漏判C(4,0)这种情况，在程序中循环判断times不为零时times为-1,程序会不断自减直至溢出归零，导致虽然结果对了但速度特慢。

while(times!=0){

times--;

next *= i-1;

i--;

if(times==0&&j!=1){

next/=2;

}

}

后来发现这程序可采用另一种思路，首先青蛙第一跳分一阶或两阶，一阶时剩余所需要的组合为jumpFloor(number-1)，而二阶时剩余组合为jumpFloor(number-2)，由此可得递归方程，

jumpFloor(number) = jumpFloor(number-1)+jumpFloor(number-2);即可解决问题。