黑马程序员技术交流社区

标题: 求解一道有趣的题 [打印本页]
作者: q312092921    时间: 2016-3-29 21:03
标题: 求解一道有趣的题
有一个40层阶梯，每次只能迈1阶或者2阶，问有多少种迈法.
哪个大神能提供一种算法？
作者: dxw    时间: 2016-3-29 21:56
本帖最后由 dxw 于 2016-3-29 22:01 编辑

public class Floor {
        public static void main(String[] args) {
                int count=0;//楼梯走法计数器
                for(int y=0;y<=20;y++) {//y为每次走2步的数量，用y控制x的值
                        int x=0;//x为每次一步的数量
                        int z=0
                        x=40-2*y;
                        z=x+y;        //每种可能一共走几次
                        count+=a(y,z);//计算并累加本次x,y组合的走法到count
                }
                System.out.println(count);//输出结果853090906
        }
        public static int a(int y,int z) {//计算本次x,y组合的走法
                int n=1;
                for(int m=0;m<y;m++,z--) {
                        n*=z;
                }
                return n;
        }
}


作者: 蓝色小宇宙    时间: 2016-3-29 22:31
本帖最后由 蓝色小宇宙 于 2016-3-30 03:20 编辑

重新修改了下代码,不知道对不对,结果是8507815389127种,因为超出了int的范围,所以用的是BigInteger来做的
  1. import java.math.BigInteger;
  2. import java.util.HashMap;
  3. import java.util.Set;

  5. public class Test4 {
  6.         public static void main(String[] args) {
  7.                 /*
  8.                  * 有一个40层阶梯，每次只能迈1阶或者2阶，问有多少种迈法.
  9.                  * 由n*1 + m*2 = 40;,0 <= n <= 40, 0 <= m <=40/2
  10.                  * 获取n和m值后,存入集合里,再遍历判断每个键值对里面有多少种组合排序方式即迈步方式,数学思想是排列组合
  11.                  */
  12.                
  13.                 //创建HashMap集合来存放n,m的值
  14.                 HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
  15.                 //遍历n
  16.                 for (int n = 0; n <= 40; n++) {
  17.                         if ((40 - n) % 2 == 0) {
  18.                                 hm.put(n,(40-n)/2);
  19.                         }
  20.                 }
  21.                 getSum(hm);
  22.         }

  24.         private static void getSum(HashMap<Integer, Integer> hm) {
  25.                 //获取集合hm的键集合
  26.                 Set<Integer> key = hm.keySet();
  27.                 //声明一个变量来记住每个键值对的迈步方式的和
  28.                 BigInteger sum = new BigInteger("0");
  29.                 //遍历键集合
  30.                 for (Integer in : key) {
  31.                         //获取每个键所对应的值
  32.                         int m = hm.get(in);
  33.                         //打印迈1步与迈2步的键值对
  34.                         System.out.print("(" + in.intValue() + "," + m + ")  ");
  35.                         //调用getMethod()方法,获取每个键值对的迈步方式总和,并打印出来
  36.                         System.out.println("这个组合的迈步方式有" + getMethod(in.intValue(),m) + "种");
  37.                         //将每个键值对的迈步方式总和叠加,遍历完集合后即可得到所有键值对的迈步和
  38.                         sum = sum.add(getMethod(in.intValue(),m));
  39.                 }
  40.                 //打印总和结果
  41.                 System.out.println("总的迈步方式有" + sum + "种.");
  42.         }
  43.         //定义一个限定条件的阶乘的方法以获取每个键值对的迈步方式的和        (数学中排列组合的方法)
  44.         private static BigInteger getMethod(int in, int m) {
  45.                 //计数器
  46.                 int count = 0;
  47.                 //声明一个变量初始化为1,记录阶乘的结果
  48.                 BigInteger sum = new BigInteger("1");
  49.                 //获取两个数里的最大值与最小值
  50.                 int max = Math.max(in, m);
  51.                 int min = Math.min(in, m);
  52.                 //阶乘,直到计数器等于最小值时停止
  53.                 while(count != min) {
  54.                         //阶乘
  55.                         sum = sum .multiply(new BigInteger(max + 1 + ""));
  56.                         //每次max减1,以达到阶乘效果
  57.                         max--;
  58.                         //计数器加1
  59.                         count++;
  60.                 }
  61.                 return sum;
  62.         }
  63. }
复制代码











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