青蛙跳階蜒茄。
有個(gè)青蛙跳上了n階臺(tái)階唉擂,每次可跳一階或兩階,問有多少種跳法檀葛?
這題很有意思玩祟,剛開始第一反應(yīng)是窮舉,通過兩個(gè)for循環(huán)將所有組合方法列出來屿聋,然后計(jì)數(shù)空扎,如下:
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是組合數(shù)學(xué)里的自定義函數(shù),作用是計(jì)算組合數(shù)量润讥。剛開始寫到一半時(shí)發(fā)現(xiàn)就算低階的時(shí)候程序運(yùn)行特別慢转锈,仔細(xì)檢查后發(fā)現(xiàn)一個(gè)很有趣的現(xiàn)象,由于漏判C(4,0)這種情況楚殿,在程序中循環(huán)判斷times不為零時(shí)times為-1,程序會(huì)不斷自減直至溢出歸零撮慨,導(dǎo)致雖然結(jié)果對(duì)了但速度特慢。
while(times!=0){
times--;
next *= i-1;
i--;
if(times==0&&j!=1){
next/=2;
}
}
后來發(fā)現(xiàn)這程序可采用另一種思路脆粥,首先青蛙第一跳分一階或兩階砌溺,一階時(shí)剩余所需要的組合為jumpFloor(number-1),而二階時(shí)剩余組合為jumpFloor(number-2)变隔,由此可得遞歸方程规伐,
jumpFloor(number) = jumpFloor(number-1)+jumpFloor(number-2);即可解決問題。