1、/M 个苹果放进 N 个盘子 算法思路int MtoN(int m, int n)int iTemp2MAX;int i, j;int a , b; /标记数组行数a = 0;b = 1;for(i = 0; i = m; i+)iTemp0i = 1; / 初始化, 表 2iTempb0 = iTempa0; / 表 3 for(i = 2; i=n; i+)iTempbi-1 = iTempai-1; / 表 3 表 5for(j = i; j = m; j+)iTempbj = iTempbj-i + iTempaj; / MtoN(m, n-1) + MtoN(m-n, n)a = a
2、b; /交换 a 和 bb = ba;a = ab;return iTempam;把个苹果放进个盘子 MtoN(m, n)，我们可以把它分解成两种情况之和：（）每个盘子都有苹果 MtoN(m-n, n)（）至少有一个盘子为空 MtoN(m, n-1)故有：MtoN(m ,n) = MtoN(m, n-1) + MtoN(m-n, n);根据这个关系我用（动态规划）来写程序我先创建一个二维数组表： 0 1 不管有多少个苹果，放进 1 个盘子，只有一种方法表 2：（苹果放进个盘子的情况） 0 1 1 1 1 1 1 1 一个苹果放进两个盘子也只有一种方法：表 3: 0 1 1 1 1 1 1 1
3、1 1 由 MtoN(m ,n) = MtoN(m, n-1) + MtoN(m-n, n);有下表：表 4: (苹果放进个盘子的情况） 0 1 1 1 1 1 1 1 1 1 2 2 3 3 因为 a 个苹果放进 a 盘子 和 a 个苹果放进 a+x 盘子情况是一样的表 5: (苹果放进个盘子的情况） 0 1 1 2 1 1 1 1 1 1 2 2 3 3 由 MtoN(m ,n) = MtoN(m, n-1) + MtoN(m-n, n);有下表：表 6: (苹果放进个盘子的情况） 0 1 1 2 3 4 5 1 1 1 2 2 3 3 依次求出 MtoN(m, n）的情况感谢耐心的查看不知道我说得够不够清楚，如果我说的不清楚，再当面解释一下我的思路方煜宽 2008.7.19
