谢谢pcrazyc的思路:
#include<stdio.h>
int a[100],m;
void find(int k,int l)
{
int i;
if(l==m)
{
if(k<=a[l-1]&&k!=0)
{
for(i=0;i<m;i++)
printf("%d ",a[i]);
printf("%d\n",k);
}
}
else
{
if(l==0)
i=k-m+l;
else
i=k-m+l+1>=a[l-1]?a[l-1]:k-m+l;
for(;i>=k/(m-l+1);i--)
{
a[l]=i;
find(k-i,l+1);
}
}
}
void main()
{
int n;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(m==1)
printf("%d\n",n);
else
{
m--;
find(n,0);
}
}
}
[此贴子已经被作者于2007-4-17 20:36:20编辑过]
----------------解决方案--------------------------------------------------------
谢谢crackerwang，我下下来好好研究一下。
----------------解决方案--------------------------------------------------------
能不能解释一下，if(k<=a[l-1]&&k!=0)，a[L-1]=A[-1]嘛，什么意思啊
----------------解决方案--------------------------------------------------------
本来这时候已经分出了m-1堆,k其实就是最后一堆.如果k比a[l-1]大了显然是不行的.
如果k==0了说明其实只分了l-1堆.
所以要过滤这两个情况.其实主要是我这个地方没有写好:
else
i=k-m+l+1>=a[l-1]?a[l-1]:k-m+l;//这里是来控制该堆的最大值的首先不能超过前一堆的数值,而且还要留写一部分给剩的k-m+l堆,至少每一堆留一个//
for(;i>=k/(m-l+1);i--)//我说一下这个地方我的思路.因为现在只剩余k了,而后面还有m-l+1堆(其实也就是以后每堆都相等)所以最小不能小于i>=k/(m-l+1);否则后面肯定有一个数要大于当前这一堆
{
a[l]=i;
find(k-i,l+1);
}
如果刚开始的加粗的地方控制好的话就不用那个条件判断了
昨天快要断电了
[此贴子已经被作者于2007-4-16 22:04:43编辑过]
----------------解决方案--------------------------------------------------------
运行了一下LS大哥的程序，觉得结果很令人满意，赞一个。可惜啊，这程序有一堆判断，还有递归，就是没有注释说明，小弟我看起来困难啊。
----------------解决方案--------------------------------------------------------
最主要的注释我已经在楼上的楼上注释过了
其实就是用第归一次一次的给数组赋直;
只是在给值的时候要注意值的大小,首先不能比数组前一个数字大,
其次你要考虑到留数据给剩余的堆
比如说把10分成3组
根据程序来的话应该是这样的
首先给a[0]值;
a[0]的值不能小于10/3;如果小于3了那么后面两堆肯定有一堆是要大于3的! //一个组合数学里抽屉原理
其次a[0]的值不能大于8,如果大于8后面肯定就有一堆没有值 //还是一个组合数学里抽屉原理
假如a[0]=7;
那么剩余3,还有2堆;
继续上面的分析
准确来说红色部分我做的还是不够准确.所以才会多了if(k<=a[l-1]&&k!=0)过滤
[此贴子已经被作者于2007-4-18 17:25:03编辑过]
----------------解决方案--------------------------------------------------------
谢谢crackerwang给出这么详细的解释。 我在运行这个程序的时候，编译器报 i j a[100]没有使用，不知是为什么。
我想再将这个问题拓展一下：
1如果在题目之初，可以输入变量F作为第一堆内苹果的最大数，如何对程序进行适当的修改？
2 如果想将所有列举出来的组合都放到数组中，我们怎么很好的定义这个数组呢？
谢谢大家的积极参与
----------------解决方案--------------------------------------------------------
谢谢你提出来的错误
因为那天快要断电了所以就没有优化就提交了.i j a[100]确实是没有用的.
我刚才已经改过来了
不好意思
第一个问题很容易解决,最大肯定是放在a[0],之后又回到把m-F分成n-1堆的问题上去了
你的第2个实现的可能性比较小.
如果种类比较多的要把所有的都列出来的话数据比较多.c语言中对数组大小的限制比较苛刻
不过要是比较小的话可以定义二维的在定义一个全局变量q,q控制行数,输入完一个组合q就加一
[此贴子已经被作者于2007-4-17 20:44:21编辑过]
----------------解决方案--------------------------------------------------------