>> 欢迎您 客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章 返回首页
>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → Java算法题:有关100阶楼梯的算法
发表一个新主题 开启一个新投票 回复文章 您是本文章第 24917 个阅读者 刷新本主题
 * 贴子主题:  Java算法题:有关100阶楼梯的算法 回复文章 点赞(0)  收藏  
作者:flybird    发表时间：2020-03-15 14:03:22     消息  查看  搜索  好友  邮件  复制  引用
    昨天在网上看到一算法题:有解决方法,但是我没有去看解决方法,而是自己想了一个算法,不过此题看上去虽简单,实则有点难度.好了我们先看题目.    

  原题：

               
       有一100阶层的楼梯，有三种走楼梯方式，一次走一阶，一次走两阶，一次走三阶。用算法实现，走完100阶总共有多少种走法.(注意,此问题的结果将是一个很大的数字,所以我用java的BigDecimal进行计算)

                  初一看,好像没什么难度,像是一个排列问题.但是深入分析发现困难重重.  好了,现在我讲讲我个人的思路.其实这就是一个组合排列问题.对1,2,3进行组合排列  (每一次迈步只有这三种走法,不可能走0阶,也不能走3阶以上).

                  第一步:我们先不谈排列,只谈组合,我们把问题简单化一下. (简单成这样比如:你有一角、两角、五角的硬币若干,有几种方法组合成10元钱).相对阶梯,这个硬币问题就简单多了,所以我第一步也是这个思路.(   1阶、2阶、  3阶,有几种组合,可以得到100阶  ).第一步组合得到若干个结果( 比如:100个一阶、98个一阶+1个二阶、95个一阶+1个二阶+1个三阶........等等).

                  第二步:第一步的组合相对比较简单,难度就在第二部的排列.对于第一步得到的结果( 每一种结果都有若干个排列,比如:[98个一阶+1个二阶]我可以走完98阶之后最后走二阶,也可以先走个二阶,再走一阶,或者换着走).这样要算出排列情况就有点难度了.(当初我在这一步思考了很多时间,用插入法,用坐标面积法等等.后来发现实现起来都挺困难).

                  第三步:就是对第一步的每一种组合,如果我们能算出每个组合的排列,然后对结果累加.最终答案就出来了.但问题是如何得到每一种的排列 (难点就在这里)?不急,我们把问题再简单一下:如果让大家对12345进行排列,有几种结果(如果大家对这个排列结果不知道如何算,那就不需要看下去了,看了你也不懂).结果是5的阶乘(1*2*3*4*5)对于若干个不相同数字的排列,结果是数字个数的阶乘.但如果里面有相同的数字进行排列,难度就增加很多.比如对11225排列,这里我只讲结果不验证了,对11223进行排列,结果是5!/(2!*2!)=30(对于这样的排序,如果有几个相同数字,按5!算会出现重复的情况,)

           下面给出代码

  1.    package  suanfa;  
  3.   import  java.math.BigDecimal;  
  6.   public   class  SF1 {  
  7.        private   static   int  a= 1 ;  
  8.        private   static   int  b= 2 ;  
  9.        private   static   int  c= 3 ;  
  10.        private   static   long   sum= 0 ;  
  11.        private   static   int  number;  
  12.        private   static  BigDecimal bigDecimalSum;  
  13.        private   static  BigDecimal bigDecimal1;  
  14.        private   static  BigDecimal bigDecimal2;  
  15.        private   static  BigDecimal bigDecimal3;  
  16.        private   static  BigDecimal bigDecimalSumAdd= new  BigDecimal( 0 );  
  18.        public   static  BigDecimal getBigDecimal( int  d){  
  19.           BigDecimal b1= new  BigDecimal( 1 );  
  20.           BigDecimal b2;  
  21.            for ( int  i= 1 ;i<=d;i++){  
  22.               b2= new  BigDecimal(i);  
  23.               b1=b1.multiply(b2);  
  24.           }  
  25.            return  b1;  
  26.       }  
  27.        public   static   void  main(String args[]){  
  28.            for ( int  i= 0 ;i<= 100 ;i++){  
  29.                for ( int  j= 0 ;j<= 50 ;j++){  
  30.                    for ( int  k= 0 ;k<= 33 ;k++){  
  31.                        if ((i*a+j*b+k*c)== 100 ){  
  32.                           number=i+j+k;  
  33.                           bigDecimalSum=getBigDecimal(number);  
  35.                            if (i> 0 )bigDecimal1=getBigDecimal(i);  
  36.                            else  bigDecimal1= new  BigDecimal( 1 );  
  38.                            if (j> 0 )bigDecimal2=getBigDecimal(j);  
  39.                            else  bigDecimal2= new  BigDecimal( 1 );  
  41.                            if (k> 0 )bigDecimal3=getBigDecimal(k);  
  42.                            else  bigDecimal3= new  BigDecimal( 1 );  
  44.                           bigDecimalSum=bigDecimalSum.divide(bigDecimal1).divide(bigDecimal2).divide(bigDecimal3);  
  45.                           bigDecimalSumAdd=bigDecimalSumAdd.add(bigDecimalSum);  
  46.                           sum++;  
  47.                           System.out.println( "一阶:" +i+ "\t2阶:" +j+ "\t3阶:" +k+ "\t\t有" +bigDecimalSum);  
  48.                            break ;  
  49.                       } else   if ((i*a+j*b+k*c)> 100 ){  
  50.                            break ;  
  51.                       }  
  52.                   }  
  53.               }  
  54.           }  
  55.           System.out.println(sum);  
  56.           System.out.println(bigDecimalSumAdd);  
  57.       }  
  58.   }
  59. //结果是180396380815100901214157639

       还有其他思路是,对于每一次迈步情况只有三种(1,2,3),最多需要多少步?(100步,每一步都走一阶),最少走34步(33个三阶,一个一阶,或者32个三阶,两个二阶)

      所以可以嵌套100层循环


  1.    for ( int  i1= 1 ;i1<= 3 ;i1++){  
  2.                for ( int  i2= 1 ;i2<= 3 ;i2++){  
  3.                   .  
  4.                   .  
  5.                   .  
  6.                    for ( int  i34= 1 ;i34<= 3 ;i34++){  
  7.                        if ((i1+i2+i3+i4+...+i34)== 100 ){  
  8.                           sum++;  
  9.                            break ;  
  10.                       } else   if ((i1+i2+i3+i4+...+i34)> 100 ){  
  11.                            break  
  12.                       }  
  13.                        for ( int  i100= 1 ;i100<= 3 ;i100++){  
  14.                            if ((i1+i2+i3+i4+...+i34+i1..+i100)== 100 ){  
  15.                               sum++;  
  16.                                break ;  
  17.                           } else   if ((i1+i2+i3+i4+...+i34+...+i100)> 100 ){  
  18.                                break  
  19.                           }  
  20.                       }  
  21.                   }  
  22.               }  
  23.           }

       呵呵这算法坑爹.

       还有用坐标,算面积,但是还没实现,



----------------------------
原文链接:https://blog.51cto.com/5496190/1088865

程序猿的技术大观园：www.javathinker.net



[这个贴子最后由 flybird 在 2020-03-20 12:00:07 重新编辑]
Java精品书籍推荐
Java最新视频教程推荐
  Java面向对象编程-->内部类
  JavaWeb开发-->开发JavaMail Web应用
  JSP与Hibernate开发-->JPA API的高级用法
  Java网络编程-->XML数据处理
  精通Spring-->Vue指令
  Vue3开发-->创建综合购物网站应用
本站其他相关文章
  算法学习与收集：一些有用的算法网站和网页
  图像基本处理算法的简单实现
  对simhash算法的一些思考
  算法的概念、特征和基本类型简介
  haproxy调度算法
  对称算法非对称算法哈希算法区别
  无向图的最短路径求解算法之——Dijkstra算法
  ipvsadm及lvs的调度算法
  全排列的六种算法
  SHA-1算法详解
  算法优化策略之“中途相遇”算法思想
  LinkedList，LinkedHashMap，LruCache源码解析
  谷歌面试算法题：两个排序数组的中位数
  技术和算法的抉择
  好书推荐：《小灰的算法之旅》
  更多...
 IPIP: 已设置保密
楼主      
共1页 0条记录 当前第1页
发表一个新主题 开启一个新投票 回复文章

中文版权所有： JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶，分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权，请与本站管理员联系。