（求算法高手！）将一个正整数表示为N个不同的正整数之和。

Question

不限语言。要求输入一个正整数，然后输出所有可以相加为该正整数的正整数组。比如说输入6，便输出如下几组数：
1,5
2,4
1,2,3
三楼的那位，重复的你没有去掉

最近没空上网，回来一看 发现这么多热心的人来回答。可是这分怎么给啊？

高手还是很多的啊。

Answer 1

200分悬赏啊，我要试一试啊。
首先是思路：
n能被拆分成不同的整数之和 =
S(1) = (n-1) + 1能被拆分成不同的整数之和
S(2) = (n-2) + 2能被拆分成不同的整数之和
。。。
S(n-1) = (n-1)能被拆分成不同的整数之和
最后一步：求并集
S(n) = Union( S(1), S(2), S(3), ..., S(n-1) )
=========================================
手动模拟一下这个算法:
n=6 能被拆分成不同的整数之和
5 + 1能被拆分成不同的整数之和 => S1 = [5,1]
4 + 2能被拆分成不同的整数之和 => S2 = [4,2]
3 + 3能被拆分成不同的整数之和
这一步要递归
3能被拆分成不同的整数之和
= 2 + 1能被拆分成不同的整数之和 => [2,1]
= 1 + 2能被拆分成不同的整数之和 => 重复
=>S3 = [3,2,1]
2 + 4能被拆分成不同的整数之和，重复，S4=[]
1 + 5能被拆分成不同的整数之和，重复，S5=[]
S = Union( S1, S2, S3, S(4), S(5) )
= [[5,1], [4,2], [3,2,1]]

=========================================
最后就是代码啦，python实现的
有2个函数，NumberSplit计算所有的拆分，checkuniq用来去重复的，去重复用了点python技巧，C++的话用hash_set应该也可以。
def NumberSplit( n ):
if n<0:
raise Exception
if n<3:
return [[n]]
sumArray = list()
for i in range(1,n):
t = NumberSplit(n-i)
for item in t:
if i in item:
continue
item.append(i)
sumArray.append(item)
return sumArray

def checkuniq(x):
for item in x:
item.sort()
return list(set(map(tuple, x)))

========================
试一下结果：
>>> checkuniq(NumberSplit(9))
[(1, 3, 5), (2, 7), (2, 3, 4), (1, 2, 6), (1, 8)]
整个大点的数字，呵呵有点慢，没有优化。
>>> g=checkuniq(NumberSplit(20))
>>> g.sort()
[(1, 2, 3, 4, 10), (1, 2, 3, 5, 9), (1, 2, 3, 6, 8), (1, 2, 3, 14), (1, 2, 4, 5, 8), (1, 2, 4, 6, 7), (1, 2, 4, 13), (1, 2, 5, 12), (1, 2, 6, 11), (1, 2, 7, 10), (1, 2, 8, 9), (1, 2, 17), (1, 3, 4, 5, 7), (1, 3, 4, 12), (1, 3, 5, 11), (1, 3, 6, 10), (1, 3, 7, 9), (1, 3, 16), (1, 4, 5, 10), (1, 4, 6, 9), (1, 4, 7, 8), (1, 4, 15), (1, 5, 6, 8), (1, 5, 14), (1, 6, 13), (1, 7, 12), (1, 8, 11), (1, 9, 10), (1, 19), (2, 3, 4, 5, 6), (2, 3, 4, 11), (2, 3, 5, 10), (2, 3, 6, 9), (2, 3, 7, 8), (2, 3, 15), (2, 4, 5, 9), (2, 4, 6, 8), (2, 4, 14), (2, 5, 6, 7), (2, 5, 13), (2, 6, 12), (2, 7, 11), (2, 8, 10), (2, 18)]

Answer 2

给您老人家写好了，用的C语言，记得采纳给分哦，咱们干技术的，彼此都不容易啊
#include"stdio.h"
int **out;

void show(int num,int position){
int i,num0=num+1;
printf("N=");
for(i=0;i<position;++i)
printf("%d+",out[num][i]);
printf("%d\n",out[num][i]);
for(i=0;i<=position;++i)
out[num0][i]=out[num][i];
}

void count(int num,int position,int n){
int i,avg=n>>1;
if(position==0){
for(i=1;i<=avg;++i){
out[0][0]=i;out[0][1]=n-i;
if(i<n-i){show(0,1);count(1,1,n-i);}
}
return;
}
if(n<out[num][position-1]*2+3) return;
for(i=out[num][position-1]+1;i<=avg;++i){
out[num][position]=i;
out[num][position+1]=n-i;
if(i<n-i){
show(num,position+1);
count(num+1,position+1,n-i);
}
}
}

int main(){
int i,N;
char input[10];
printf("please input a num:");
gets(input);
N=atoi(input);
int length=(int)sqrt(N<<1);
out=(int **)malloc(sizeof(int *)*length);
for(i=0;i<length;i++) out[i]=(int *)malloc(sizeof(int)*length);
count(0,0,N);
system("pause");
}本回答被提问者采纳

Answer 3

难得到高分区打个酱油，发现还是有很好玩的东西啊....于是果断来凑热闹
算法也比较直观，sum-list是一个函数，接受两个参数,n和start，计算n这个数可以分解成的所有加法组合，其中的加数至少从start开始

比如10这个数从1开始加，那么先放一个1，接下来就要求10-1也就是9这个数如何从2开始加，这就变成了sum-list函数的递归调用。然后递归的结果前面都加上1这个数即可。

语言：common lisp
略为不爽的是：
1. 不知道怎么写partial application，以至于要用lambda....
2. 在递归前判断了3个边界条件，感觉逻辑有点复杂了，感觉最好控制在2个判断以内，会比较像样...
3. 最后一步去掉一个元素，因为按照sum-list函数，6这个数除了题目中的3种加法以外，还会把6本身也算进去。这在递归中是必要的，但是最后结果是不需要的，所以必须去掉。对于单链表来讲，去掉最后的元素是性能比较弱的，不过这个问题可以通过给sum-list在加个参数解决，代码就不改了....

(defun sum-list (n start)
(cond ((= n 0) (list nil))
((< n start) nil)
((= n start) (list (list n)))
(t (loop for x from start to n append
(mapcar #'(lambda (l) (cons x l))
(sum-list (- n x) (1+ x)))))))
(defun sum-lists (n) (butlast (sum-list n 1)))

运行结果：
CL-USER> (sum-lists 10)
((1 2 3 4) (1 2 7) (1 3 6) (1 4 5) (1 9) (2 3 5) (2 8) (3 7) (4 6))

Answer 4

#include<stdio.h>
#include<math.h>
void main()
{
long int num;
int a,b,c,d,e,place;
printf("please input a number(0--99999):%d\n",num);
scanf("%ld",&num);
if(num>=10000)
place=5;
else if(num>=1000)
place=4;
else if(num>=100)
place=3;
else if(num>=10)
place=2;
else
place=1;
printf("输入数的位数是：%d\n",place);
printf("每位数字为:");
e=num/10000;
d=(int)(num-e*10000)/1000;
c=(int)(num-e*10000-d*1000)/100;
b=(int)(num-e*10000-d*1000-c*100)/10;
a=(int)(num-e*10000-d*1000-c*100-b*10);
switch(place){
case 5:printf("%d,%d,%d,%d,%d",e,d,c,b,a);
printf("\n反序数字为:");
printf("%d,%d,%d,%d,%d\n",a,b,c,d,e);
break;
case 4:printf("%d,%d,%d,%d",d,c,b,a);
printf("\n反序数字为:");
printf("%d,%d,%d,%d\n",a,b,c,d);
break;
case 3:printf("%d,%d,%d",c,b,a);
printf("\n反序数字为:");
printf("%d,%d,%d\n",a,b,c);
break;
case 2:printf("%d,%d",b,a);
printf("\n反序数字为:");
printf("%d,%d\n",a,b);
break;

case 1:printf("%d",a);
printf("\n反序数字为:");
printf("%d\n",a);
break;
}

Answer 5

dim x,y,z
m=6
for i=1 to 6
for j=1 to 6
if i+j=m then
print i,j
end if
next j
next i