N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式
N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式？思路一：设有x次走一阶，y次走两阶，则一定满足x+2*y=n，且x、y均为整数，那么对于任何一个满足的x的可能走法共有
C（x+(n-x)/2,x）种走法，即从数x+(n-x)/2中取x种组合，值为（x+(n-x)/2）的阶乘除以x的阶乘与(n-x)/2的阶乘的乘积。
依次取可能的x值，然后相加每一种的可能情况就可以了。代码如下
/* * N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式 */public class ListCraw {public static void main(String args[]){System.out.println(crawlist(30));}public static int crawlist(int n){if(n<=0){return -1;}int total=0;for(int x=0;x<=n;x++){if((n-x)%2==0){if(x==0||n-x==0){total++;}else{ int re=f(n+(x-n)/2)/(f(x)*f((n-x)/2));//计算组合数C(x+(n-x)/2,x)total+=re;}}}return total;}public static int f(int n){//求n的阶乘,返回-1，说明输入数据n不合法if(n==0){return 1;}else if(n>=1){return n*f(n-1);}else{return -1;}}} 思路二：走到第n阶时可能是从第n-1阶走一步到的，也可能是从n-2阶走两阶到的，设F(n)为走到n阶的种数，则F(n)=F(n-1)+F(n-2)。当n=1时，F(1)=1，n=2时，F(2)=2,这是一个动态规划问题。其实就是一个斐波那契数列。
public static int fic(int n){if(n==1||n==2){return n;}else if(n>=3){return fic(n-1)+fic(n-2);}else{return -1;//输入n值非法}}
页:
[1]