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个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢
楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法? 【参考解答(递归法)】 基础:楼梯有一个台阶,只有一种走法(一步登上去);两个台阶,有2种走法(一步上去,或分两次...
本文实例讲述了Python走楼梯问题解决方法。...分析:问题可以从最后一次是走1步还是两步,反向考虑 ''' def take_stairs_recursive(n): if n == 1: return 1 elif n == 2: return 2 else: return take_stairs_recur
好用的取色器,按住ALT 用鼠标取色 方便实用!
有n级台阶,一个人每次上一级或者两级,问有多少种走完N级台阶的方法。为了防止溢出,请将结果Mod 1000000007。 给定一个正整数int N,请返回一个数,代表上楼的方式数。保证N小于等于100000。 这道题类似于...
行业资料-交通装置-一种可上楼的车.zip
随着城市可开发土地越来越少,工业上楼席转全国,方兴未艾,建筑是一个拥有2000多年历史的极其传统行业,用传统方式很难找到合理的解决方案,通过数字化技术方式跨界到建筑界,期待资源整合出一个新物种建筑一数字化赋能的...
行业资料-交通装置-一种可以上楼梯的推拉车.zip
于是某人想出了一个新的电梯调度算法:由于大楼楼层不高,因此每次电梯从一楼往上走时,只允许电梯停在某一层,然后其他人在从本层爬楼梯到达各自的目的地;在一楼的时候,每人选择自己的楼层,电梯应根据每楼层的...
小学生小心上楼精选.doc
小学生小心上楼参考.doc
上楼村山洪灾害防御预案.docx
2023数字化赋能工业上楼白皮书.pptx
VC 6.0 MFC模拟电梯上楼 下楼逻辑实现,本程序直观...不过本人学习MFC没多少天,程序还是有遗憾的,就是在电梯下楼的时候,要一层一层的按,要不然人进不到电梯里,也希望高手能优化这个程序,让其变得更加人性化一些。
行业资料-交通装置-一种方便上楼梯的新型多功能行李车.exe
在虚拟公寓中漫游-漫游+上楼
关于禁止电动车上楼充电的通知学习总结.doc
【华为&SZAD】2023数字化赋能工业上楼白皮书.pdf
活动类、上楼走、下楼走、慢速走、中速走、快速慢跑、站着、坐着、躺着,这几类动作图片书集。 9个人类活动类型数据集。活动类、上楼走、下楼走、慢速走、中速走、快速慢跑、站着、坐着、躺着,这几类动作图片书集。...