第四天：算法分享

应用方法：递归与分治

• 题目要求：n个不同的苹果，放入m个相同的盘子中，盘子不允许为空，一共有多少种分法？

一、思考

1. 首先我们可以思考，每个苹果在盘子的状态有哪些情况

   ? 有啥状态呢？？ 怎么思考呢？？

   可以联系递归的思想： 一个苹果的情况会有哪些

     * 单独在一个盘子里
     * 和别的苹果混合放在一个盘子里
   

   此时已经包括了一个苹果的所有可能情况，现在我们分别思考两种情况如何表示

   （1）单独在一个盘子里

   假设有S(n,m)种不同的方法表示苹果放入盘中的情况。

   则 第一种情况可表示为 S（n-1， m-1）

   因为一个苹果单独占了一个盘子， 即剩下n-1个苹果去排剩下m-1个盘子

   得到一个排序数目 S（n-1，m-1）

   （2）和别的苹果混合放在一个盘子里

   此时可以先安置 n-1个苹果到m个盘子中。接着剩余的一个苹果可以放到任意一个盘子中

   即 有m种放法 ，即所有方法为 1*M *S（n-1，m）即m * S（n-1，m）

   不难分析出，两种情况包含了一个苹果所有可能性，根据递归思想所有苹果的情形都可表示

2. 接着我们找出结束条件

   • 当苹果数和盘子数相等时 ， 显然只有一种放法
   • 当盘子数目为1时， 也只有一种方法
   • 当盘子数目大于苹果数目 或者盘子数目为0时 ，有零种放法

3. 数学表达式为：

   ? 0 m=0或者m>n

   ? S（n，m） = 1 m=1或者m=n

   ? m*S(n-1,m)+S(n-1,m-1) 0<m<n

4. 算法为：

   public static int Stirling(int a, int b){
           if ((a==b) || (b == 1)){
               return 1;
           }else if ((b > a) || (b ==0)){
               return 0;
           }return  b* Stirling(a-1,b) +Stirling(a-1, b-1);
   

二、总结

通过这次算法的分析，更加深刻的理解了递归的魅力

思考的时候要抓住所有可能的状态进行分析可能性

一定要静下心来，认真分析。

希望能够有所帮助。

“苹果算法”