/*将整数n分成k份，且每份不能为空，任意两种分法不能相同（不考虑顺序）。 　　例如：n=7,k=3,下面三种分法被认为是相同的。 　　1，1，5； 1，5，1； 5，1，1； 　　问有多少种不同的分法。 输入：n,k (6<n≤200,2≤k≤6) 输出：一个整数，即不同的分法。 [样例]： 　 输入：7 3 　 输出：4 [说明]：（此部分不用输出） 　　样例中的4种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;*/

这个题目的难点在与重复输出问题，我想大家可以去想一想，题目不难，

但绝对需要你的思考。如果说结构是程序的骨架，算法就是程序的灵魂，而这

个灵魂需要我们来注入——还是那句话：算法第一，代码第二。

大家一起来体会思考的快乐吧。

[此贴子已经被作者于2004-07-21 14:44:45编辑过]

不重复是难点，解决了这个问题就都好办了。

楼上的5种情况讨论是怎么做的？可以说出来大家交流交流

[此贴子已经被作者于2004-07-23 09:47:39编辑过]

先想想嘛，或许你可以找到比我更好的也说不定，思考是快乐的，不是吗？

你在XP下不能编？应该不会吧，你用的是什么编译器？

这个想法 神vLinux飘飘已经提到过了，但这只能解决分3份的问题，要是我让你分4份或

更多呢？ 再想想。

knocker的算法和我想的差不多——排序，递归

从第一个数开始搜索，保证后面搜到的数大于等于前面的就可以了

（递归时可以适当剪枝，确定一个比较好的搜索范围）

knocker真的好厉害，这个算法应该算最好的了。

有兴趣的朋友可以按这个算法编一个程序，贴上来，大家交流

2004的方法也不错，实现我这道题的要求很有用，但如果要求打印结果的话……

所以还是觉得排序好。出这道题的目的就是想让大家多思考一下，体会一下好的算法，

好了如果需要的话我可以把自己的代码贴上来（如果那位兄弟想自己试试，我就先不贴了）

我把自己的代码也贴出来吧，再WUN-TC下编译通过：

int count=0,k; /*count 为计数函数*/ void do1(int min,int max,int left,int c) /*递归函数*/ { int i,l,m;

if(c==1)count++ ;

else for(i=min;i<=max;i++) /*搜索范围是优化代码的关键*/

{l=left-i;m=l/(c-1);do1(i,m,l,(c-1));}} /*最小值为前一个数，最大值为剩下的数除以剩下的数字的个数*/ main() {int n,i=1,j=1;

while(i) {printf("Input the number\n"); scanf("%d",&n); if(n>6&&n<=200)i=0; else printf("The number must be bigger than 6 and smaller than 200!\n");}

while(j){ printf("Input the how many parts you want:\n"); scanf("%d",&k); if(k>=2&&k<=6)j=0; else printf("The part must be more than 2 and less than 6!\n");} do1(1,(n/k),n,k); printf("There are %d posibilities.",count);getch();}