求算法分苹果问题输入MN,M个苹果放到N个篮子里可以有空篮子并且122和212算一种放法问一共多少种放法不需要代码只要告诉我算法就可以了谢谢啦

Question

求算法 分苹果问题
输入M N ,M个苹果放到N个篮子里 可以有空篮子 并且122和212算一种放法
问一共多少种放法
不需要代码 只要告诉我算法就可以了 谢谢啦

Answer 1

算法说明太复杂,后面给你代码.简单说明：
122 212 221是同种方法,则取代表 221
123 .321 是同种方法,则取代表 321
能当“代表”的组合的特点是,前面的不小于后面的.
这是一个限制条件.
想来想去用递归最好.
比如10个放入3个篮子,变成：
第一个放10,再把0个放入剩余2个篮子
第一个放9,再把1个放入剩余2个篮子
第一个放8,再把2个放入剩余2个篮子
第一个放7,再把3个放入剩余2个篮子
.
总之,M个苹果,N个篮子,
第一个放a个,a的范围是从M减小到0,
而再将(M-a)个苹果放入N-1个篮子.
但是放的时候要一定满足“前面的不小于后面的”.
代码：
#include
void PutApple(long nRemainApple, long nRemainBasket,
long nLevel, long nAllLevel, long * npBuffer,
long nLimit, long * npSum)
{
long k;
if (nLevel == nAllLevel-1)
{
if (nRemainApple =0; k--)
{
npBuffer[nLevel]=k;
PutApple(nRemainApple-k, nRemainBasket-1,
nLevel+1, nAllLevel, npBuffer, k, npSum);
}
}
main()
{
int nApple = 10;
int nBasket = 3;
printf("Please input apple count:");
scanf("%d", &nApple);
printf("Please input basket count:");
scanf("%d", &nBasket);
if (nApple200)
return 0;
if (nBasket30)
return 0;
long * npBuffer = new long [nBasket];
long nCount=0;
PutApple(nApple, nBasket, 0,
nBasket, npBuffer, nApple, &nCount);
delete []npBuffer;
printf("Count = %d\n", nCount);
return 0;
}
对10个苹果,3个篮子,运行结果：
Please input apple count:10
Please input basket count:3
10 0 0
9 1 0
8 2 0
8 1 1
7 3 0
7 2 1
6 4 0
6 3 1
6 2 2
5 5 0
5 4 1
5 3 2
4 4 2
4 3 3
Count = 14
Press any key to continue