假设我有一个数字5,现在表示5的和的可能组合是:
4+1个
3+2个
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
我们如何用C语言为这个创建一个程序?
最佳答案
#include <stdio.h>
#include <stdlib.h>
int *LIST; /* result work list */
int LEVEL=-1;/* partition level */
void print (void){
int i;
for(i=LEVEL;i>=0;--i){
printf("%d",LIST[i]);
if(i!=0)
printf(" + ");
}
printf("\n");
}
void part(int n){
int i, first; /* first is last-1 */
if(n<1) return ;
LIST[++LEVEL]=n; /* add list tail */
print();
first=(LEVEL==0) ? 1 : LIST[LEVEL-1];
for(i=first;i<=n/2;i++){ /* candidate > first */
LIST[LEVEL]=i; /* last element replace */
part(n-i);
}
LEVEL--;
return;
}
int main(int argc, char **argv){
int N;
N=(argc>1)?atoi(argv[argc-1]):5;
LIST=(int *)calloc(N, sizeof(int));
if(LIST==NULL){
fprintf(stderr, "not enough memory\n");
return -1;
}
part(N);
free(LIST);
return 0;
}
/* result
5
4 + 1
3 + 1 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
2 + 2 + 1
3 + 2
*/