題目描述:有n級台階,一直青蛙,每次跳1個台階或者每次跳2個台階,請問青蛙上到第n級台階有多少種方法。
不妨先用數學的方法找規律解這個問題:
假設他有3級台階;
可分為兩類:
跳0次2台階,剩餘3次1台階;組合數C(0,3)
跳1次2台階,剩餘1次1台階;組合數C(1,2)
總數sum=C(0,3)+C(1,2)
假設他有4級台階;
跳0次2台階,剩餘4次1台階;組合數C(0,4)//
跳1次2台階,剩餘2次1台階;組合數C(1,3)//
跳2次2台階,剩餘0次1台階;組合數C(2,2)//兩個數字總是以1為機關加減靠近,且二者之和為台階數,以第一個數字<=第二個數字結束
sum=C(0,4)+C(1,3)+C(2,2)
...........
假設他有10級台階;
跳0次2台階,剩餘4次1台階;組合數C(0,4)
跳0次2台階,剩餘4次1台階;組合數C(0,4)
跳0次2台階,剩餘4次1台階;組合數C(0,4)
跳0次2台階,剩餘4次1台階;組合數C(0,4)
............
我們可以預測
sum=C(0,10)+C(1,9)+C(2,8)+C(3,7)+C(4,6)+C(5,5)
于是可以推測出第n級sum
sum=C(0,n)+C(1,n-1)+C(2,n-2)+...........
數學上組合數的計算方式為
C(a,b)=a!/b!*(a-b)!
是以在解答這個問題是,我們不避免要寫一個運算階乘的函數。
int fac(int n)
{ int ret=1;
if(n<=1)
{return 1;
}
else
{
ret=ret*n;
return ret*fac(n-1);
}
}
再回到運算總數
sum=C(0,n)+C(1,n-1)+C(2,n-2)+...........
這是一個累加,故可以用上循環
等等,當n=1時,方法隻有一種。故我們先可以把最簡單的先解決。
if(n<=1)
{return 1;
}
當n>=2時,我們會發現無法用計算機輸出0!,故直接将其定為1
這裡可以使用一個while循環來計算和,用b來接受和
int a=1,b=1;
while(a<=n)
{
b=b+fac(n-1)/(fac(a)*fac(n-1-a));//核心步驟
n--;
a++;
}
return b;
傳回值就為b。
總的代碼就為
//青蛙跳台階
#include<stdio.h>
//階乘函數
int fac(int n)
{ int ret=1;
if(n<=1)
{return 1;
}
else
{
ret=ret*n;
return ret*fac(n-1);
}
}
//
int mains(int n)
{ int a=1,b=1;
if(n==1)
{
return 1;
}
while(a<=n)
{
b=b+fac(n-1)/(fac(a)*fac(n-1-a));//核心步驟
n--;
a++;
}
return b;
}
int main()
{ int n;int res;
scanf("%d",&n);
res=mains(n);
printf("%d",res);
return 0;
}