8-2-15.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include <stdio.h>
#define N 100
int a[N];

int sum(int total, int d[],int n){ 
int s, p, t, b[N], none = 1;
b[0] = 0;  t = d[0]; p = 1;
do{
if (t == total){ /* 找到了一个解，把当前解输出 */
printf("%4d = %d",total, d[b[0]]);
for(s = 1; s < p; s++)
printf(" +%d",d[b[s]]);
printf("\n");
none = 0;   /*  置找到过解的标志  */
}
else {
for(s = b[p-1] + 1; s < n-1 && t + d[s] > total;s++);
if (s < n && t + d[s] <= total) {
b[p++] = s;  t += d[s];
continue; 
}
}
t -= d[b[p-1]];     /*  回溯 */
if ( p > 1 && b[p-1] == n-1){
p--; t -= d[b[p-1]];
}
if ( p == 1 && b[0] == n-1) break;  /*  回溯到底，退出找解循环  */
t += d[++b[p-1]]; /*  回溯后，调整  */
} while(1);
return !none; /* 返回找到过解答的标志  */
}

main( ){ 
int i,n, total, d;
printf("输入  total!\n"); scanf("%d",&total);
printf("输入  n!\n");  scanf("%d",&n);
for(i = 0; i < n;) {
printf("输入数组的第 %d 个正整数( > 0 且 <= %d)\n",i+1,total);
scanf("%d", &d);
if (d < 1 || d > total){
printf("出错，请重新输入！\n");
continue;
}
a[i++] = d;
}
if (!sum(total, a, n)) printf("没有找到解答！\n");
printf("\n\n");
}