算法——台阶问题

问题描述：

 

楼梯有20阶台阶,上楼可以一步上1阶、2阶或3阶三种走法,计算共有多少种不同的走法。

 

 

算法：

 

最简单情况，不考虑三种走法的顺序，那么可以用穷举法计算。原理是： 1X+2Y+3Z=20。结果是44种。

 

如果考虑顺序，那么对于每一种（X、Y、Z）走法都要计算他们的排列组合数，然后相加。

 

源码程序如下：

package zieckey.datastructure.study.recursion;

public class StaircaseProblem
{

    /**
     * @param args
     */
    public static void main( String[] args )
    {
        long ans = calc( 20 );
        System.out.println( "The answer is : " + ans );
    }

    public static long calc( int n )
    {
        long ans = 0;
        for ( int out = 0; out <= n; out++ )
        {
            for ( int mid = 0; mid <= n / 2 + 1; mid++ )
            {
                for ( int in = 0; in <= n / 3 + 1; in++ )
                {

                    if ( out + mid * 2 + in * 3 == 20 )
                    {
                        long temp = permutationCombination( out, mid, in );//考虑顺序

                        //long temp = 1;//不考虑顺序
                        System.out.print( "1step:" + out );
                        System.out.print( "        2step: " + mid );
                        System.out.print( "        3step: " + in );
                        System.out.println( "    permutationCombination: " + temp );
                        ans = ans + temp;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * @param big
     * @param small
     * @return 从 big 个元素取 small 个，不进行排列（即不排序）。
     */
    public static long combination1( int big, int small )
    {
        if ( big == 0 || small == 0 )
        {
            return 1;
        }else if ( big==small )
        {
            return 1;
        }

        long ans = 1;
        int loop = small;
        long numerator = 1;//分子

        for ( int i = 1; i <= loop; i++ )
        {
            ans = ans * (big-i+1);
            numerator = numerator * i;
        }

        ans = ans / numerator;
        return ans;
    }

    /**
     * 三个参数，oneNo,towNo,threeNo代表三种不同物品的个数。 sum = oneNo+towNo+threeNo
     * 将这三种些物品排成一列，公有多少种排放法
     *
     * @param oneNo
     * 物品1的个数，有可能为0
     * @param towNo
     * 物品2的个数，有可能为0
     * @param threeNo
     * 物品3的个数，有可能为0
     * @return 将这三种些物品排成一列，共有多少种排放法
     */
    public static long permutationCombination( int oneNo, int towNo, int threeNo )
    {
        long ans = 0;
        int totalNo = oneNo + threeNo + towNo;
        int[] arrayNo = sortArray( oneNo, towNo, threeNo );
        ans = combination1( totalNo, arrayNo[2] )
                * combination1( totalNo - arrayNo[2], arrayNo[1] );
        return ans;
    }

    /**
     * @param oneNo
     * @param towNo
     * @param threeNo
     * @return 返回由三个参数构成的数组，数组已经从大到小排序好
     */
    public static int[] sortArray( int oneNo, int towNo, int threeNo )
    {
        int[] array = new int[3];
        array[0] = oneNo;
        array[1] = towNo;
        array[2] = threeNo;

        int temp;

        for ( int out = 0; out < 3; out++ )
        {
            for ( int in = out + 1; in < 3; in++ )
            {
                if ( array[out] < array[in] )
                {
                    temp = array[out];
                    array[out] = array[in];
                    array[in] = temp;
                }
            }
        }

        return array;
    }
    
    
    /**
     * 递归算法
     * @param a
     * @param arrayindex
     * @param sum
     * @return
     */
    public static int func(int a[],int arrayindex, int sum )
    {
        if(arrayindex==0)
            return 1;
        else
        {
            int count = 0;
            int temp = a[arrayindex];
            for (int i = temp; i <= sum; i+=temp) {
                if(sum-i>0)
                count += func(a,arrayindex-1,sum-i);                
            }
            if(sum%temp==0)
             count+=1;
            count += func(a,arrayindex-1,sum);
            return count;
        }
        
    }
}