|
#2
okgays2010-03-23 19:13
你的程序逻辑上有错误，导致运行时会出现段错误，在程序中c[i]值永远不可能为1，只能到0；故程序一直不能跳出循环，输出aaaaaaa，导致溢出错误。
我自己写了一个，你可以参考一下： #include <stdio.h> //定义一个结点 struct node{ int data; //存放集合中的元素 int flag; //标记集合中的元素，若为1，表示该元素在目标集合中，若为0，表示不在其中 }; /****从集合的num个元素中查找满足以下要求的元素，并输出。要求如下： *****被选中的元素之和为指定值y *****/ void search(struct node *pnode, int num, int y) { int tmp = y; //y的值在下面会发生改变，故先记下初始值，当再次扫描元素时保证y值不变 int count = 0; //判断是否有满足要求的集合，若有则大于0，否则等于0 for (int k = num - 1; k >= 0; --k) //从最后一个节点的元素值开始扫描 { if (pnode[k].data <= y) //若元素值小于等于y则记下此元素，并将y值减去此元素的值 { int t = k; while ( t >= 0 && y >0 ) { if ( pnode[t].data <= y ) { y = y - pnode[t].data; pnode[t].flag = 1; } --t; } if (y == 0) //当y为0时表示满足要求的元素已找到，输出这些被标记的节点的元素值 { ++count; printf("the target set is : { "); for (int i = 0; i < num; ++i) { if (pnode[i].flag == 1) { printf("%d ", pnode[i].data); } } printf("}\n"); } for (int i = 0; i < num; ++i) //重新初始化各个元素的标记状态为0，一边下次扫描 pnode[i].flag = 0; y = tmp; } } if (!count) printf("the target set is not existed\n"); } int main() { int n = 6; //集合中元素的个数 int tar = 60; struct node Anode[6]; //由集合中的每个元素和相应的标记组成的结点数组 for (int i = n - 1; i >= 0; --i) { Anode[i].flag = 0; Anode[i].data = 10 * (i + 1); } //初始化结点中元素的标记为未标记状态，并给集合中元素赋值 search(Anode, n, tar); return 0; } |
给定一个n个整数的集合X={x1,x2....xn}和整数y,找出和等于y的X的子集Y.比如：若X={10,20,30,40,50,60}和y=60,则有三种不同长度的解,它们分别是{10,20,30},{20,40},{60}.这个问题可以用另一种方法明确表达，使得解是一种明显的长度为n的布尔向量，于是上面的三个解可以用布尔向量表示为：
{1，1，1，0，0，0}，{0，1，0，1，0，0}，{0，0，0，0，0，1}。
今天试图用c语言实现该算法，但是总也调不出来。请大虾帮忙！我的程序代码如下：
#include <stdio.h>
int isLegal(int a[],int c[],int n,int y){
int i;
int sum=0;
for(i=0;i<n;i++){
if(c[i]==1){
sum=sum+a[i];
}
}
if(sum==y){
return 1;
}else{
return 0;
}
}
int isPart(int a[],int c[],int n,int y){
int i;
int sum=0;
for(i=0;i<n;i++){
if(c[i]==1){
sum=sum+a[i];
}
}
if(sum<y){
return 1;
}else{
return 0;
}
}
int partition(int A[],int c[],int n,int y){
int k,j;
int flag=0;
for(k=0;k<n;k++){
c[k]=-1;
}
k=0;
while(k>=0){
while(c[k]<=0){
c[k]=c[k]+1;
if(isLegal(A,c,n,y)){
flag=1;
/*储存或输出解向量*/
printf("\n");
for(j=0;j<n;j++){
printf("%d ",c[j]);
}
break;
}
else if(isPart(A,c,n,y)){
k=k+1;
printf("aaaaa\n");
}
}
c[k]=-1;
k=k-1;
}
return flag;
}
void main(){
int A[6]={10,20,30,40,50,60};
int flag=0;
int c[6]={-1,-1,-1,-1,-1,-1};
flag=partition(A,c,6,60);
if(flag){
printf("find the answer!");
}
else{
printf("can not find the answer!");
}
getch();
}