A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© Gqg 中级黑马   /  2016-3-21 23:53  /  2186 人查看  /  28 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

看到有一道题:有一个40层阶梯,每次只能迈1阶或者2阶,问有多少种迈法.
哪个大神能提供一种算法?

28 个回复

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

评分

参与人数 1黑马币 +1 收起 理由
洋葱头头 + 1 山寨

查看全部评分

回复 使用道具 举报
递归找规律
回复 使用道具 举报 1 0
总共有40级台阶,假设总共走了x个2阶,那么每次走1阶的总次数是(40-2x)个,很显然,该数是偶数
回复 使用道具 举报
兵蜂 发表于 2016-3-22 09:57
总共有40级台阶,假设总共走了x个2阶,那么每次走1阶的总次数是(40-2x)个,很显然,该数是偶数 ...

哦,想错了,还有组合呢,不好意思
回复 使用道具 举报
zx7750462 来自手机 中级黑马 2016-3-22 12:08:23
地板
如果涉及组合就很麻烦不涉及的话二楼正解
回复 使用道具 举报
我写了一个,请各位指正:
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);//输出迈法总数
        }
}
回复 使用道具 举报
第一想到了数学中的排列
回复 使用道具 举报
好难。。。。。。
回复 使用道具 举报
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, 下载次数: 23)

QQ截圖20160323220652.png
回复 使用道具 举报
1759418586 发表于 2016-3-23 22:07
class Test_1_test {

        /**

这个应该没啥问题吧......,数据大的超出预计....
回复 使用道具 举报
果然不简单~~
回复 使用道具 举报
1759418586 发表于 2016-3-23 22:07
class Test_1_test {

        /**

按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性就降低了,我是先算出每个i对应的组合可能,再求和,见7楼,但是编译没错,运行会出上述问题,层主有时间帮我看看.
回复 使用道具 举报
xiaofushen 发表于 2016-3-24 00:45
按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性 ...

....我回头看一下是不是需要除2............
回复 使用道具 举报
先定义一个组合类
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:29
16#
都是大神,来自: iPhone客户端
回复 使用道具 举报
本帖最后由 freshnboy 于 2016-3-24 10:14 编辑

补充一下二楼的思路:定义一个求阶乘的函数,再定义一个求组合的函数,比较利于代码的复用。。。
感觉代码的服用性真的特别重要,以前做项目的时候很多代码复制了还要改来改去的,很麻烦
回复 使用道具 举报
xiaofushen 发表于 2016-3-24 00:45
按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性 ...

这个我考虑到了有重复性的问题,,,你看看当i= 13的时候不会报错,当i=14的时候就会报错,
你的思路应该是对的,但是数列中插入相同元素的那个公式我也忘了...应该是那个公式有点问题...
回复 使用道具 举报
还是想的太简单了
回复 使用道具 举报
我不是已经解决过了吗?  

forty.zip

947 Bytes, 下载次数: 95

回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马