急！求c语言算法：求s等于数组d中哪些元素相加的和?(200分)

  • 主题发起人 主题发起人 dfxing
  • 开始时间 开始时间
D

dfxing

Unregistered / Unconfirmed
GUEST, unregistred user!
请各位大虾帮忙救救急!现急需一C语言的算法：
输入一组数 n1,n2……nk,s,(k<=100，数串以-1做为结束标志)全都为
正整数，且无重复，求s是否等于它前面从n1到nk中部分数的和? 如果是，则按
原顺序输出这些数(且已知其中只有一组数符合要求)。要求既可以用键盘输
入，也可以从一个文件中读入一组数，然后将结果写入另一个文件中。
 
排列组合问题。
用递归。
 
这是一个典型的NP问题, 类似于0/1背包问题;
算法大致如下, 思路应该没错, 疏漏之处,
你就自己补起来吧.
#include <stdio.h>
int a[100];
int b[100];
int sum=0;
int
int go(int n)
{ int i;
for(i=0;i<=1;i++)
{ sum+=a[n]*i;
b[n]=i;
if (sum==s) print()
else
if ( sum<s &amp;
a[n+1]!=-1) go(n+1);
b[n]=0;
sum-=a[n]*i;
}
}
int print()
{ int i=0;
ok=1;
while (a[++i]!=-1)
if ( b=1 ) printf("%d",a);
}
void main()
{ 读入 a;
b 清零;
go(1);
if (!ok ) printf("No answer");
}
我可是这里最穷的人, 给点银子吧!!

 
#include
int a[100];
int b[100];
int sum=0;
int
int go(int n)
{ int i;
for(i=0;i<=1;i++)
{ sum+=a[n]*i;
b[n]=i;
if (sum==s) print()
else
if ( sum<s &amp;
a[n+1]!=-1) go(n+1);
sum-=a[n]*i;
b[n]=0;
}
}
int print()
{ int i=0;
ok=1;
while(a[++i]!=-1)
if (b) printf("%d ",a);
}
void main(void)
{ 变量初始化;
go(1);
if (!ok) printf("No answer");
}
变量初始化和输入输出, 就请自己去写了
阵惨, 连丢了两次, 这是第三次敲!



 
#include
int a[100];
int b[100];
int sum=0;
int
int go(int n)
{ int i;
for(i=0;i<=1;i++)
{ sum+=a[n]*i;
b[n]=i;
if (sum==s) print()
else
if ( sum<s &amp;
a[n+1]!=-1) go(n+1);
sum-=a[n]*i;
b[n]=0;
}
}
int print()
{ int i=0;
ok=1;
while(a[++i]!=-1)
if (b) printf("%d ",a);
}
void main(void)
{ 变量初始化;
go(1);
if (!ok) printf("No answer");
}
变量初始化和输入输出, 就请自己去写了
阵惨, 连丢了两次, 这是第三次敲!



 
#include
int a[100];
int b[100];
int sum=0;
int
int go(int n)
{ int i;
for(i=0;i<=1;i++)
{ sum+=a[n]*i;
b[n]=i;
if (sum==s) print()
else
if ( sum &amp;lt s &amp;&amp;
a[n+1]!=-1) go(n+1);
sum-=a[n]*i;
b[n]=0;
}
}
int print()
{ int i=0;
ok=1;
while(a[++i]!=-1)
if (b) printf("%d ",a);
}
void main(void)
{ 变量初始化;
go(1);
if (!ok) printf("No answer");
}
变量初始化和输入输出, 就请自己去写了
阵惨, 连丢了两次, 这是第三次敲!



 
原来是 &amp;lt 在作怪,
各位朋友传代码是要注意了:>
 
这种东东都要现成的算法，//faint,
至多给个提示就行乐。
//agree Hexi
 
感谢张国龙！
此算法可以求出有没有几个数字等于 S ，但无法标记出是哪几个数,
而这正是本题所要求的.在 b[n] 中存储的是在求解过程中参与过的
数,而非是最后所求的可以组成 S 的数.
烦劳各位大虾再给提示一下!
 
to dfxing
张国龙的算法应该可以满足你的需要的.
只需要在print()中稍微变一点就可以了.
 
那就结束问题吧!
 
清华大学出版的那本《数据结构》的习题集上好像有答案。
 
阵不好意思, 笔误!!
b[n]=i 应为 b[n]=1;
明白了?
 
感谢诸位！问题也经解决。
还是　b[n]=i 好些。
再次感谢大家！
 
感谢大家！问题已经解决。
还是　b[n]=i 好些。
再次感大家。
 
真没面子, 被你蒙住了,
确实应为 b[n]:=i;
因该可以打印出结果了.
 
是不是该给点'阿堵物' 了?
 
把我给忘了? :(
 
接受答案了.
 
您必须登录或注册才可回复。

Similar threads

悟
两道C语言考试题,在线等待,马上给分.(150分)
回复
11
查看
543
zhuhuix
Z
T
c++与delph混合编程中怎样来回传递Double型数组？？？急！！！(50分)
回复
6
查看
393
zhaoray
Z
X
关于数据库的计算(急!!!在线等待)(200分)
2
回复
26
查看
271
zqflying
Z
Z
急救阿！急救阿！急救阿！帮我实现图中所示的数据输入DBGRID!!!!!(50分)
回复
13
查看
214
zk1
Z
V
stringgrid1内数据修改到数据库方法求教！(200分)
回复
9
查看
220
vip1977
V
后退
顶部