(200分求算法)我以为我半个小时就搞定了,结果用了两天也没结果.看似简单的问题却内藏玄机.你能做出这个算法吗?(200分)

  • 主题发起人 主题发起人 lncd
  • 开始时间 开始时间
L

lncd

Unregistered / Unconfirmed
GUEST, unregistred user!
一张公式表,字段名为:
id(公式编号) LeftName(公式左边) rightName(公式右边) serid(运算顺序)
1 a m+n 1
2 b x+y 1
3 c a+b 2
...
以上可归纳为:
a=m+n
b=x+y
c=a+b
...
很显然,要先算公式a=m+n;b=x+y再算公式c=a+b才能得出正确结果.
现在的问题是,如何将公式计算顺序算出来,并填到Serid
 
1。第一次遍历整个公式集,得到LeftName(公式左边)的所有元素的集合
以及rightName(公式右边)所有元素的集合
2 rightName(公式右边)集合 - LeftName(公式左边)集合 ,得到的是原子元素
3 肯定存在某个(或者多个)公式的右式为2个原子元素,
那么这个(这些)的为serid为1
4 查找serid为1的和原子元素组成的公式,他们的serid为2
5 。。。。依次类推
 
//首先将所有的计算顺序初始化为0
//然后扫描公式表,产生一张变量依存关系表,为简单起见,用StringList存储,命名 VarList,
//内容如下所示:
a=m,n
m=
n=
b=x,y
x=
y=
c=a,b
....
//当然,m,n,x,y可以不在表中出现
//自己提供以下两个函数
procedure SetSerid(vName:string;
Serid:integer);
//为变量设置顺序号
function SeridOf(vName:string):integer;
//取变量当前顺序号
//用以下函数来计算并设置每个变量(公式)的顺序号
function CalcSerid(vName:string):integer;
function CutFirstName(var s:string):string;
var
P:integer;
begin
P:=Pos(',',s);
if P=0 then
Result:=s
else
begin
Result:=Copy(s,1,P-1);
Delete(s,1,P);
end;
end;
var
DependVarNames:string;
DependSerid:integer;
begin
Result:=SeridOf(vName);
if Result=-1 then
raise Exception.Create('循环引用');
DependVarNames:=DependList.Values[vName];
if (Result=0) and (DependVarNames<>'') then
begin
SetSerid(vName,-1);
//设置正在计算的标志
repeat
DependSerid:=CalcSerid(CutFirstName(DependVarNames));
if DependSerid>=Result then
Result:=DependSerid+1;
until DependVarNames='';
SetSerid(vName,Result);
end;

end;

procedure SetAllSerid;
//主
begin
for i:=0 to VarList.Count-1do
CalcSerid(copy(VarList,1,pos('=',VarList)-1);
end;

//徒手写的,请自己调试
 
以前写过一个计算公式的例程,很烦:
1、对每个变量置一个变量表,有以下几个属性:
o 变量名 VarName
o 有没有完成计算 bResovled
o 计算公式 formula
o 计算结果 answer
2、读表到内存 TList,就是我所上面所说的结构
3、遍历表,如果发现析出公式中的变量,比如 X.bresovled = False;
则应先计算 X,计算过程大多相似。要注意的是:必须置一个循环限制
标志,防止死循环,比如一个相对大的数:64,即最大遍历次数最大为
64,否则,所有未解决的变量全部置零!这一点很重要。
4、还有什么 =========> 不要我说了吧:作一个比较好的表达式求解函数。
OK?
 
至于运算顺序,可以用一个变量,每计算一个项,即每置一个 bResolved = True;
就 Inc(Serid),这不用我多说了吧。
 
[8D]
我觉得,一次把所有公式全部填完,然后再用过程来确定serid(运算顺序),处理起来太复
杂了,而且效率很低。
同时还存在一种可能,就是操作员输入的公式是错误的,即存在“循环引用”的问题,那会
将程序带到灾难性的“死循环”中。即使你在程序中能判断出来,也是要循环很多层才能发
现的。
所以我认为,不妨把思路转一下,不要最后才做这件事,而是在每输入一个公式时,就做一
个判定。
提供一些想法:
在表中增加一个包含“所有引用变量”的列,作用是将本公式所引用的变量(包括变量所再
引用的变量)全部填入。
在输入公式完成后,即用一个过程实现这个的目的,万一发现引用了自己,马上给出错误提
示(这就是循环引用,就不应该输入嘛)。
然后这样判断这个公式:
如果“所有引用变量”是空,则本公式的serid(运算顺序)=1;
如果“所有引用变量”不为空,则本公式的serid(运算顺序)=所有引用变量的serid(运算顺序)最大值 + 1;
应该比一次实现要容易的多,而且有错误可以在输入时发现。
 
上面各位答的也不错,但我觉得如果要一次扫描出来的话,一个最大的问题就是:不知从哪
个开始为好?
第一个公式?——未必吧。
所以,不妨把这个判断交给操作员:想清楚了再填,不要乱七八糟瞎填一通,程序不是神童,
也不是超级保姆,连自己都想不清的公式,却让程序去想,纯粹是捣乱!
这样,操作员只能按层次顺序来填公式,出现错误,马上提示。这样,肯定能成功!(EXCEL
也是输入错误马上提示的)
 
我同意楼上的,说法,你不应要求的太高了,其实现实生活中没几个人用电脑
会比程序员还行的,你把问题简单化就行了么!!@
 
非常感谢大家的参与,
一天后我还是写出了解决办法。速度不太好。(算100个公式大概要3秒)
因为那段时间太忙,没来得及上来看看。
龙丹:特别感谢你,你居然写了那么多代码。太感动了。
pyzfl:你的想法很好,有空我会试试。
其它各位师兄师妹,小生在此一并谢了。
不多说了,散分拉。
 

Similar threads

S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
后退
顶部