数学高手请进，一个算法问题，谢谢，有难度 ( 积分: 50 )

  • 主题发起人 主题发起人 gzxyq
  • 开始时间 开始时间
G

gzxyq

Unregistered / Unconfirmed
GUEST, unregistred user!
请教一个问题，这个问题如何写程序算？
求
a(m)数组中，那n个数的和等于X，当然n<=m，即a(m)中有那些数相加等于X（组合问题），比如
可能a(1)+a(3)=x
a(1)=x
a(2)+a(5)+a(8)=x
.............
结果可输出到一个文本文件,如
a(1)+a(3)=x
a(1)=x
a(2)+a(5)+a(8)=x
 
program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

const
MaxM = 65535;

type
TNode = record
Sum: Integer;
d: Integer
end;

var
m, X: Integer;
a: array [1..MaxM] of Integer;
Stack: array [1..MaxM] of TNode;
Top: Integer;
i: Integer;

begin
Write('m=');
ReadLn(m);
for i:=1 to m do
begin
Write('a(', i, ')=');
ReadLn(a)
end;
Write('X=');
ReadLn(X);

Top:=1;
Stack[Top].Sum:=0;
Stack[Top].d:=0;
while Top>0 do
begin
while Stack[Top].d<m do
begin
Inc(Stack[Top].d);
if (a[Stack[Top].d]+Stack[Top].Sum)<X then
begin
Inc(Top);
Stack[Top].Sum:=Stack[Top-1].Sum+a[Stack[Top-1].d];
Stack[Top].d:=Stack[Top-1].d
end
else if (a[Stack[Top].d]+Stack[Top].Sum)=X then
begin
for i:=1 to Top-1 do
Write('a(', Stack.d, ')+');
WriteLn('+a(', Stack[Top].d, ')=', X)
end
end;
Dec(Top)
end;
ReadLn
end.
 
请参考 http://www.delphibbs.com/delphibbs/dispq.asp?lid=555596 ——也是求和问
题，稍加修改就可以用了。
 
to LeeChange ,谢谢,好象你的算法不完整,能不能给个完整的,谢谢!!
 
给个算法思路：
i:=0;
while i< high(a)的2次方 do
begin
inc(i);
然后检测i哪个位为1，把位为1的相对应的值相加，和是x，输出

end;

对于楼主的问题，我觉得没有比这更简单的算法了。
 
ufo能不能具体些呀??
 
从楼主的问题看来，组合排列运算量很大。数组元素不可能超过64个，真要有64个元素，估计pc电脑1000年也算不完。

下面给个具体一点的，i用的是无符号整形值
i:=0;
while i< high(a)的2次方 do
begin
inc(i);
k:= 0;
然后检测i哪个位为1，把位为1的相对应的值相加，和是x，输出
for J := 0 to 31 do
if (i shr J) and (1 shl J) then
k:= k + a(j); //a就是你的数组
if k= X then 输出
end;

这个算法速度还能优化，在优化算法方面creation-zy是高手，呵呵。
 
对了，判断位是否为一，应该用下面的代码：
if i and (1 shl J) then
k:= k + a(j); //a就是你的数组
 
我在上面的链接帖子中首先执行了排序，求和时按顺序递推，首先进行合法检验，然后再
进行求和——这样能够避免很多无效的运算。楼主所要做的不过是将该帖中每次遍历都删除
元素的部分去掉即可。
 
我大致看了下creation-zy转的帖子，代码多达百行
而我的代码只需10行，呵呵。
如果优化，觉得可以从这几个方面入手
1。首先进行一次全部元素求和，如果刚好等于或者小于X，那么退出，不用接着算了。
2。接着，可以把单个大于等于X的元素剔除。
3。接下来的元素从新排序，运算，当然，新位置要和老位置有个对应关系记录。
每次找到相等关系时，只需输出 i的integer值，
全部计算完毕后对这些ingteger值进行处理，显示出其二进制对应位是1的数组即可。
当然，如果数组元素不多，也就7-8个，那么无需优化都没关系了
 
to 楼主：
俺给的是可直接编译执行的代码啊？哪个部分不完整啊？
不过到是在算法上偷懒了，只在搜索上加了一两个剪枝条件，效率上不会太高。建议你还是研究一下creation的方法，他是从取最少的数开始往多个数算的，每次算完都能有效的减少下一次的搜索空间，虽然程序长一点，但是执行效率会好很多，解决64个数应该没什么大问题。
 
首先,谢谢各位!!!特别是ufo,creation-zy,LeeChange.
to LeeChange:你的算法比较合适我,因为我要把它转换成excel的宏,在excel里执行的。其实我是从一个数开始和X比较（可能我的实际需求会简单些）：
1.如果数组中有一个数等于x，那么比较完成，把数组中这个数删除，计算完成。
2.如果数组中任何一个数都不等于x，再找是否有两个数和等于x，如果有，那么把这两个数删除，计算完成。
依次类推3,4,5
6.如果以上都不能完成计算，是否有6个数和等于X，如果有，那么删除这6个数，完成计算。如果没有，那么也完成计算，设置标志notfind=true。即最多只计算到6个数和。并且加数越少越好！！！
LeeChange兄，能不能帮完善下你的程序，谢谢！！！！！！！这几天天天加班到很晚，头昏眼花的，你和程序我看了好久才明白一些。
 
creation-zy，leechange都回答了，我来了也没用。自己慢慢琢磨一下把，人家不能什麽都帮你准备好，大家都要上班，不是专职回答问题的，哈哈；这样你印象也更深刻
 
to 楼上: 快把system那个问题解决了吧,俺想把System关小黑屋都关不了.[:(]

按照最多6个取最优的要求改了一下:
program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils;

const
MaxM = 65535;

type
TNode = record
Sum: Integer;
d: Integer
end;

var
m, X: Integer;
a: array [1..MaxM] of Integer;
Stack: array [1..6] of TNode;
Top: Integer;
i: Integer;
BestArr: array [1..6] of Integer;
Best: Integer;

begin
Write('m=');
ReadLn(m);
for i:=1 to m do
begin
Write('a(', i, ')=');
ReadLn(a)
end;
Write('X=');
ReadLn(X);
Best:=7;

Top:=1;
Stack[Top].Sum:=0;
Stack[Top].d:=0;
while Top>0 do
begin
while (Stack[Top].d<m) and (Top<Best) do
begin
Inc(Stack[Top].d);
if (a[Stack[Top].d]+Stack[Top].Sum)<X then
begin
Inc(Top);
Stack[Top].Sum:=Stack[Top-1].Sum+a[Stack[Top-1].d];
Stack[Top].d:=Stack[Top-1].d
end
else if (a[Stack[Top].d]+Stack[Top].Sum)=X then
begin
Best:=Top;
for i:=1 to Best do
BestArr:=Stack.d
end
end;
Dec(Top)
end;

if Best<7 then
begin
Write('a(', BestArr[1], ')');
for i:=2 to Best do
Write('+a(', BestArr, ')');
WriteLn('=', X)
end
else
WriteLn('Not found');
ReadLn
end.
 
to: creation-zy,这个system问题很像是论坛的人工智能啊，论坛不停的给自己发贴子要求提意见“给本论坛页面“/delphibbs/dispq.asp?lid=3729594”评论和建议。”

哈哈，玩笑玩笑。

另外，趁这次修改论坛代码的机会，给论坛增加几个小功能吧。
 
小学生的问题，还有难度呢，
当然不否定有市场
 
呵呵，要玩就玩大的——不知道现在论坛的硬件环境以及访问频度如何？我想用自己平台
的B/S支撑技术在本地搞个类似的模拟一下 :) 希望各位老大能够提供支持哈[:D]

ps: 这里不是放广告的地方[:D]
等我先找找前几年的数据模拟一下，如果效果还过得去的话再进行实战模拟吧。 :)
 
请creation-zy先介绍一下你的bs平台有哪些功能？
 
to LeeChange,能不能说下你的QQ?
 
to LeeChange,不好意思,还是不理解你的思路,能不能说说???谢谢
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
L
关于最小二乘法，帮忙看看这段代码啥意思？ 啊-----加分，100分吧 (10分)
回复
19
查看
318
lcl_003
L
L
(200分求算法)我以为我半个小时就搞定了,结果用了两天也没结果.看似简单的问题却内藏玄机.你能做出这个算法吗?(200分)
回复
10
查看
547
lncd
L
L
JohnsonGuo在不在？关于最小二乘法(10分)
回复
13
查看
243
lcl_003
L
L
关于软件容错设计，高手必进！！！！ (100分)
2
回复
26
查看
1K
dop
D
后退
顶部