黑马程序员技术交流社区

标题: 一道有趣的题求解 [打印本页]

作者: Gqg 时间: 2016-3-21 23:53
标题: 一道有趣的题求解
看到有一道题：有一个40层阶梯，每次只能迈1阶或者2阶，问有多少种迈法.
哪个大神能提供一种算法？

作者: 1759418586 时间: 2016-3-22 08:48
假设迈2阶的次数为i,i的范围是0-20, j是迈1阶的次数 j= 40-2i ,利用for循环,i从0开始.到20,
将 i 插入到 j 个1中,统计有多少个方法,; 循环完了再统计一下总次数,这是我的思路.,,等晚上我看看能不能将代码发过来.

作者: little_bear123 时间: 2016-3-22 09:54
递归找规律

作者: 兵蜂 时间: 2016-3-22 09:57
总共有40级台阶，假设总共走了x个2阶，那么每次走1阶的总次数是（40-2x）个，很显然，该数是偶数

作者: 兵蜂 时间: 2016-3-22 09:58

兵蜂发表于 2016-3-22 09:57
总共有40级台阶，假设总共走了x个2阶，那么每次走1阶的总次数是（40-2x）个，很显然，该数是偶数 ...

哦，想错了，还有组合呢，不好意思

作者: zx7750462 时间: 2016-3-22 12:08
如果涉及组合就很麻烦不涉及的话二楼正解

作者: xiaofushen 时间: 2016-3-22 22:41
我写了一个,请各位指正:
class Test1 { //by xiaofushen
public static void main(String[] args) {
double sum = 0;double m = 1;double a = 1; //定义sum,记录迈法总数
for (int i = 1,j = 40 - 2 * i;i <= 20 ;i++ ) { //i是迈2阶的步数,j是迈一阶的步数,i=0另算
for (int x = 1;x <= i ;x++ ) {
m *= x;//求对应i的阶乘
}
for (int y = i + j;y >= j + 1 ;y-- ) {
a *= y;//求对应A(i)(i+j)的排列
}
sum += (a / m);//算出i对应的每种组合迈法总数,并求和
//之前用long定义sum,m,a但是这步运行出错:ArithmeticException
//用double输出是Infinity(无穷)
}
sum++;//加上i=0的迈法
System.out.println(sum);//输出迈法总数
}
}

作者: abijiame 时间: 2016-3-22 22:51
第一想到了数学中的排列

作者: jiangkaizhuo 时间: 2016-3-22 23:26

好难。。。。。。

作者: 1759418586 时间: 2016-3-23 22:07
class Test_1_test {

/**
* 假设走2阶的次数为i,假设走1阶的次数为j 则j= 40-2i;
*/
public static void main(String[] args) {
long sum = 0;
for (int i = 0; i <= 20; i++) {

sum = sum + (long)Math.pow(41-2*i, i); //这里是(41-2*i)的i次方,,
}
System.out.println("一共有"+sum+"种可能性");
}
}

输出结果是

QQ截圖20160323220652.png (13.56 KB, 下载次数: 29)

QQ截圖20160323220652.png

作者: 1759418586 时间: 2016-3-23 22:09

1759418586 发表于 2016-3-23 22:07
class Test_1_test {

/**

这个应该没啥问题吧......,数据大的超出预计....

作者: zxydeh 时间: 2016-3-23 22:11
果然不简单~~

作者: xiaofushen 时间: 2016-3-24 00:45

1759418586 发表于 2016-3-23 22:07
class Test_1_test {

/**

按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性就降低了,我是先算出每个i对应的组合可能,再求和,见7楼,但是编译没错,运行会出上述问题,层主有时间帮我看看.

作者: 1759418586 时间: 2016-3-24 07:26

xiaofushen 发表于 2016-3-24 00:45
按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性 ...

....我回头看一下是不是需要除2............

作者: 兵蜂 时间: 2016-3-24 08:05
先定义一个组合类
public class Combination {
//定义降序阶乘，返回积
public static int factorial(int start){
int ji=1;
for(;start>=1;start--){
ji*=start;
}
return ji;
}
//定义降序number个数阶乘，返回积
public static int factorial_limit(int start,int number){
int ji=1;
while(number>=1){
ji*=start;
number--;
start--;
}
return ji;
}
//定义组合方法，参数total是指总共迈的步数，select为一次迈一步的次数（也可表示一次迈两部的步数）
public static int OpCombination(int total,int select){
int tmp1=factorial_limit(total, select);
int tmp2=factorial(select);
return tmp1/tmp2;
}
}
再用主方法调用它
public class Test {

public static void main(String[] args) {
// TODO Auto-generated method stub
//定义一个变量，记录走法的次数
int times=0;
//定义一个循环，局部变量i表示一种走法中，一步2阶出现的次数
for(int i=0;i<=20;i++){
int tmp=0;
//tmp表示一步1阶出现的次数
tmp=40-2*i;
//tmp表示总共走了多少步
tmp+=i;
//进行组合，统计次数
times +=Combination.OpCombination(tmp, i);
}
System.out.println(times);
}

}

作者: Banana_uSuOO 时间: 2016-3-24 08:18
都是大神，

作者: freshnboy 时间: 2016-3-24 10:11
本帖最后由 freshnboy 于 2016-3-24 10:14 编辑

补充一下二楼的思路：定义一个求阶乘的函数，再定义一个求组合的函数，比较利于代码的复用。。。
感觉代码的服用性真的特别重要，以前做项目的时候很多代码复制了还要改来改去的，很麻烦

作者: 1759418586 时间: 2016-3-24 21:43

xiaofushen 发表于 2016-3-24 00:45
按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性 ...

这个我考虑到了有重复性的问题,,,你看看当i= 13的时候不会报错,当i=14的时候就会报错,
你的思路应该是对的,但是数列中插入相同元素的那个公式我也忘了...应该是那个公式有点问题...

作者: ghost飒 时间: 2016-3-24 21:46
还是想的太简单了

作者: yijincheng 时间: 2016-3-24 22:19
我不是已经解决过了吗？

947 Bytes, 下载次数: 148

作者: yijincheng 时间: 2016-3-24 22:20

1759418586 发表于 2016-3-23 22:07
class Test_1_test {

/**

答案是一亿六千万。

作者: yijincheng 时间: 2016-3-24 22:22
本帖最后由 yijincheng 于 2016-3-24 23:07 编辑

看到了这道题，多人第一个思路估计都是：
全部只迈1阶，最多40步；全部只迈2阶，最少20步。
然后算38步迈一阶，1步迈2阶总共有多少种组合；19步迈2阶，2步迈1阶有多少种组合…………。把所有组合都一一算出来，最后加起来，得到答案。

这样算其实也可以。但是这是道编程题啊。上述的算法终究还是大部分的逻辑判断都是人脑完成的，最后计算机不过是担任了一个高级计算器的角色。有点太过于委屈如今这个时代计算机的计算速度了
用编程解决数学问题，就应该人脑动的越少越好，就靠计算机恐怖的计算速度暴力的穷举出来才叫做程序员的道嘛。
那么，现在我们来看看该如何穷举出所有的可能迈步的组合。
我们不用去考虑第一步该怎么走，第二步该迈2阶还是1阶。把这些可能性全部试一遍。
也就写代码来模拟爬这个40级台阶。
第一步开始，就是两个分支：先迈2阶和先迈1阶。那么就分开来搞定。先迈2阶，等爬到顶了，再下来，再走先迈1阶的路线。
到了第二步，又是分两支——第二步是迈1阶还是迈2阶？还是先走迈一阶的走法，走到顶了，再下拉，走迈2阶的走法。
………………
可是这么一直走下去，什么时候是头呢？这就要有个变量来显示还剩多少台阶，初始值为40，每走一步，就根据迈一阶还是两阶，减去1或2.当变成0了就可以return了。
具体代码实现就是

public class Steps {
private int totalSteps; //总共多少级台阶
private int ways; //总共有多少种走法
public Steps() {
totalSteps = 40; //40级台阶
ways = 0; //初始化总走法
}
public void go() { //运用了递归算法。先算第一步迈一级的分支；再算第一步迈两级的分支
oneStep(totalSteps);
twoStep(totalSteps);
}
private boolean oneStep(int remainSteps){//参数的意义：还剩下多少级台阶。
remainSteps -= 1; //走了一级
if(remainSteps == 0) {//剩下的台阶为0，返回true，ways加1.
ways++;
return true;
}
else if(remainSteps < 0) {//冒了，返回false
return false;
}
else if(remainSteps > 0) {//还剩有台阶没走完，继续走。还是先算走一级的分支，再算走两级的分支。
oneStep(remainSteps);
twoStep(remainSteps);
}
return false;
}
private boolean twoStep(int remainSteps){
remainSteps -= 2; //走了两级
if(remainSteps == 0) {//剩下的台阶为0，返回true，ways加1.
ways++;
return true;
}
else if(remainSteps < 0) {//冒了，返回false
return false;
}
else if(remainSteps > 0) {//还剩有台阶没走完，继续走。还是先算走一级的分支，再算走两级的分支。
oneStep(remainSteps);
twoStep(remainSteps);
}
return false;
}
public void show() {
System.out.println(ways);
}
}

复制代码

代码写得匆忙。oneStep（）和twoSteps（）方法似乎不需要返回值。为程序健壮性就留着吧。没有接触过递归算法的同学，可以找时间学习一下。这是一个虽然抽象，但是却非常强大的数据结构。
这个结构非常像二叉树。大家可以试试，用TreeSet的结构来做这道题。

作者: yijincheng 时间: 2016-3-24 22:23

1759418586 发表于 2016-3-22 08:48
假设迈2阶的次数为i,i的范围是0-20, j是迈1阶的次数 j= 40-2i ,利用for循环,i从0开始.到20,
将 i 插 ...

算法终究还是大部分的逻辑判断都是人脑完成的，最后计算机不过是担任了一个高级计算器的角色。有点太过于委屈如今这个时代计算机的计算速度了。
正确思路因该用递归结构，穷举出来。

作者: yijincheng 时间: 2016-3-24 22:31

little_bear123 发表于 2016-3-22 09:54
递归找规律

看了这么多层。就这么一个思路对的。

作者: 1759418586 时间: 2016-3-25 00:41

yijincheng 发表于 2016-3-24 22:31
看了这么多层。就这么一个思路对的。

毕竟新手,只记得初中时候数学上学的插入元素的方法,,就拿来用了...
如果结合数学上的公式的话应该能更快得出结果,为啥非得用穷举,.......

作者: ameanboy 时间: 2016-3-25 02:47
这是个经典的二叉树算法题，明天搬代码过来

作者: Joschi 时间: 2016-3-25 13:28
好题，收藏了

作者: yijincheng 时间: 2016-3-25 14:16
本帖最后由 yijincheng 于 2016-3-25 14:33 编辑

1759418586 发表于 2016-3-25 00:41
毕竟新手,只记得初中时候数学上学的插入元素的方法,,就拿来用了...
如果结合数学上的公式的话应该能更快 ...

结果上来看，你也算错了啊。当然，你当思路是正确的，不过计算过程不对。排列组合的公式是：C(n,m) = m!/n!*(m - n) !，你再改改看。不过从解决问题效率角度看，并不推荐。现在家用机CPU的处理速度都是每秒几十亿次。真心不必替电脑担心穷举所花费的时间，大概会慢个几微秒吧。再者，要理解递归结构、回溯算法的难度也不比这个纯数学问题低。

作者: xiaofushen 时间: 2016-3-25 22:30
本帖最后由 xiaofushen 于 2016-3-25 22:31 编辑

yijincheng 发表于 2016-3-24 22:22
看到了这道题，多人第一个思路估计都是：
全部只迈1阶，最多40步；全部只迈2阶，最少20步。
然后算38步迈一 ...

受教了,递归和二叉树,看完层主分析后,才知道这果然是道有趣的题.二叉树结构本身有递归特性,其操作可以用递归描述.原问题只要能分解为相同形式且更简单的子问题,并且有结束条件,就可以用递归解决.

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2