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

dfxing · 2000-01-11

请各位大虾帮忙救救急!现急需一C语言的算法：
输入一组数 n1,n2……nk,s,(k<=100，数串以-1做为结束标志)全都为
正整数，且无重复，求s是否等于它前面从n1到nk中部分数的和? 如果是，则按
原顺序输出这些数(且已知其中只有一组数符合要求)。要求既可以用键盘输
入，也可以从一个文件中读入一组数，然后将结果写入另一个文件中。

Hexi · 2000-01-11

排列组合问题。
用递归。

张国龙 · 2000-01-12

这是一个典型的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 &
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");
}
我可是这里最穷的人, 给点银子吧!!

张国龙 · 2000-01-12

#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 &
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");
}
变量初始化和输入输出, 就请自己去写了
阵惨, 连丢了两次, 这是第三次敲!

张国龙 · 2000-01-12

#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 &
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");
}
变量初始化和输入输出, 就请自己去写了
阵惨, 连丢了两次, 这是第三次敲!

张国龙 · 2000-01-12

#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 &lt s &&
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");
}
变量初始化和输入输出, 就请自己去写了
阵惨, 连丢了两次, 这是第三次敲!

张国龙 · 2000-01-12

原来是 &lt 在作怪,
各位朋友传代码是要注意了:>

SuperMMX · 2000-01-12

这种东东都要现成的算法，//faint,
至多给个提示就行乐。
//agree Hexi

dfxing · 2000-01-14

感谢张国龙！
此算法可以求出有没有几个数字等于 S ，但无法标记出是哪几个数,
而这正是本题所要求的.在 b[n] 中存储的是在求解过程中参与过的
数,而非是最后所求的可以组成 S 的数.
烦劳各位大虾再给提示一下!

Tangqs · 2000-01-14

to dfxing
张国龙的算法应该可以满足你的需要的.
只需要在print()中稍微变一点就可以了.

kingbb · 2000-01-14

那就结束问题吧!

sonie · 2000-01-14

清华大学出版的那本《数据结构》的习题集上好像有答案。

wjiachun · 2000-01-14

&lt

张国龙 · 2000-01-14

阵不好意思, 笔误!!
b[n]=i 应为 b[n]=1;
明白了?

dfxing · 2000-01-14

感谢诸位！问题也经解决。
还是　b[n]=i 好些。
再次感谢大家！

dfxing · 2000-01-14

感谢大家！问题已经解决。
还是　b[n]=i 好些。
再次感大家。

张国龙 · 2000-01-15

真没面子, 被你蒙住了,
确实应为 b[n]:=i;
因该可以打印出结果了.

张国龙 · 2000-01-20

是不是该给点'阿堵物' 了?

张国龙 · 2000-02-02

把我给忘了?

wjiachun · 2000-08-31

接受答案了.

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

dfxing

Unregistered / Unconfirmed

Hexi

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

SuperMMX

Unregistered / Unconfirmed

dfxing

Unregistered / Unconfirmed

Tangqs

Unregistered / Unconfirmed

kingbb

Unregistered / Unconfirmed

sonie

Unregistered / Unconfirmed

wjiachun

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

dfxing

Unregistered / Unconfirmed

dfxing

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

张国龙

Unregistered / Unconfirmed

wjiachun

Unregistered / Unconfirmed

Similar threads