昨天在网上看到一算法题:有解决方法,但是我没有去看解决方法,而是自己想了一个算法,不过此题看上去虽简单,实则有点难度.好了我们先看题目.

原题：

        有一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;  
2.  
3. import java.math.BigDecimal;  
4.  
5.  
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);  
17.  
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);  
34.                           
35.                         if(i>0)bigDecimal1=getBigDecimal(i);  
36.                         else bigDecimal1=new BigDecimal(1);  
37.                           
38.                         if(j>0)bigDecimal2=getBigDecimal(j);  
39.                         else bigDecimal2=new BigDecimal(1);  
40.                           
41.                         if(k>0)bigDecimal3=getBigDecimal(k);  
42.                         else bigDecimal3=new BigDecimal(1);  
43.                           
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.         } 

呵呵这算法坑爹.

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