m个相同苹果放的n个相同盘子中的算法

m个相同的苹果,放在n个相同的盘子中,由于相同,使用排列组合的方法不好处理。这个问题困扰了我很久

最后由大神“或缺”给出了答案:

以8个苹果放在3个盘子中为例

思路:

8苹果3盘子

=8苹果2盘子+5苹果2盘子(每盘已经放入1个)+2苹果2盘子(每盘已经放入3个)

=(8苹果1盘子+6苹果1盘子(每盘已经放入1个))+ (3苹果1盘子(每盘已经放入1个)+1苹果1盘子)(每盘已经放入1个)+(1苹果1盘子(每盘已经放入1个)+1苹果1盘子)(每盘已经放入3个)

=5+3+2

=10

编程实现:

[cpp][/cpp] view plaincopy

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int func(int m, int n)
  5. {
  6.     cout << “m=” << m << “, n=” << n << endl;
  7.     if (n <= 1)
  8.         return 1;
  9.     int t=0;
  10.     for (int i=m; i>=0; i-=n)
  11.     {
  12.         t += func(i, n-1);
  13.     }
  14.     return t;
  15. }
  16. int main()
  17. {
  18.     int m=0, n=0;
  19.     while (1)
  20.     {
  21.         cout << “请输入苹果数 盘子数:” ;
  22.         cin >> m >> n;
  23.         cout << “您输入的是: m=” << m << n << endl;
  24.         if (m==-1)
  25.         {
  26.             break;
  27.         }
  28.         cout << “共” << func(m, n, “–“) << “种放法” << endl;
  29.         cout << “————” << endl;
  30.     }
  31.     return 0;
  32. }

计算结果:

 

标签