|
|
昨天在网上看到一算法题:有解决方法,但是我没有去看解决方法,而是自己想了一个算法,不过此题看上去虽简单,实则有点难度.好了我们先看题目. 原题：
有一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!算会出现重复的情况,)
下面给出代码
- package suanfa;
- import java.math.BigDecimal;
- public class SF1 {
- private static int a= 1 ;
- private static int b= 2 ;
- private static int c= 3 ;
- private static long sum= 0 ;
- private static int number;
- private static BigDecimal bigDecimalSum;
- private static BigDecimal bigDecimal1;
- private static BigDecimal bigDecimal2;
- private static BigDecimal bigDecimal3;
- private static BigDecimal bigDecimalSumAdd= new BigDecimal( 0 );
- public static BigDecimal getBigDecimal( int d){
- BigDecimal b1= new BigDecimal( 1 );
- BigDecimal b2;
- for ( int i= 1 ;i<=d;i++){
- b2= new BigDecimal(i);
- b1=b1.multiply(b2);
- }
- return b1;
- }
- public static void main(String args[]){
- for ( int i= 0 ;i<= 100 ;i++){
- for ( int j= 0 ;j<= 50 ;j++){
- for ( int k= 0 ;k<= 33 ;k++){
- if ((i*a+j*b+k*c)== 100 ){
- number=i+j+k;
- bigDecimalSum=getBigDecimal(number);
- if (i> 0 )bigDecimal1=getBigDecimal(i);
- else bigDecimal1= new BigDecimal( 1 );
- if (j> 0 )bigDecimal2=getBigDecimal(j);
- else bigDecimal2= new BigDecimal( 1 );
- if (k> 0 )bigDecimal3=getBigDecimal(k);
- else bigDecimal3= new BigDecimal( 1 );
- bigDecimalSum=bigDecimalSum.divide(bigDecimal1).divide(bigDecimal2).divide(bigDecimal3);
- bigDecimalSumAdd=bigDecimalSumAdd.add(bigDecimalSum);
- sum++;
- System.out.println( "一阶:" +i+ "\t2阶:" +j+ "\t3阶:" +k+ "\t\t有" +bigDecimalSum);
- break ;
- } else if ((i*a+j*b+k*c)> 100 ){
- break ;
- }
- }
- }
- }
- System.out.println(sum);
- System.out.println(bigDecimalSumAdd);
- }
- }
- //结果是180396380815100901214157639
|
还有其他思路是,对于每一次迈步情况只有三种(1,2,3),最多需要多少步?(100步,每一步都走一阶),最少走34步(33个三阶,一个一阶,或者32个三阶,两个二阶)
所以可以嵌套100层循环
- for ( int i1= 1 ;i1<= 3 ;i1++){
- for ( int i2= 1 ;i2<= 3 ;i2++){
- .
- .
- .
- for ( int i34= 1 ;i34<= 3 ;i34++){
- if ((i1+i2+i3+i4+...+i34)== 100 ){
- sum++;
- break ;
- } else if ((i1+i2+i3+i4+...+i34)> 100 ){
- break
- }
- for ( int i100= 1 ;i100<= 3 ;i100++){
- if ((i1+i2+i3+i4+...+i34+i1..+i100)== 100 ){
- sum++;
- break ;
- } else if ((i1+i2+i3+i4+...+i34+...+i100)> 100 ){
- break
- }
- }
- }
- }
- }
|
呵呵这算法坑爹.
还有用坐标,算面积,但是还没实现,
----------------------------
原文链接:https://blog.51cto.com/5496190/1088865
程序猿的技术大观园：www.javathinker.net
[这个贴子最后由 flybird 在 2020-03-20 12:00:07 重新编辑]
|
|
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → Java算法题:有关100阶楼梯的算法
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密
