精华区文章阅读

发信人: GREnTOFEL (Crazy Plucking), 信区: Algorithm
标  题: 剪枝搜索----加括号(转载)
发信站: 哈工大紫丁香 (2002年07月06日21:52:20 星期六), 站内信件

【以下文字转载自 Programming 讨论区】
【原文由 zjliu 所发表】
发信人: violinist (巷战狙击手), 信区: Algorithm
标  题: 剪枝搜索----加括号
发信站: 日月光华 (Fri Jul  5 08:31:28 2002)

剪枝搜索

加括号

------------------------------------------------------------------------------

--

〖题目描述〗
输入两个数字(i,j)，在第一个数字i中间添上若干个加号，使得这个代数式的值等于第二

个数字j 。

〖问题分析〗
这道题采用的算法是剪枝搜索，逐一在第一个数字i各个数字之间添上加号，并计算出当前

代数式的值，如果等于第二个数字j，则退出循环，打印结果“YES”；如果不是，则继续

循环；当循环结束后，还未能得出第二个数j，则打印结果“NO”。

〖算法流程〗
1、首先将以字符串输入的第一个数字i切成一个数字e段，放进一个数组a[e]里。
2、接着进行循环，逐一在第一个数字i各个数字之间添上加号，由于在各个数字之间添上

加号后代数式的值只有两种情况：大于第二个数字j或小于第二个数字j，所以循环的内容

可以如下：
（1）以h,i分别作为当前处理的数字的首位在数组里的位置和在当前数字的第i位添加号。

（2）分别以x1,x2存放添加号后加号前的数值以及加号后的数值，x3将赋值为x1+x2，作为

当前代数式的值。当x3>j时，则进行将h赋值为i，将要处理的数字赋值为加号后的数值，

并将x3赋值为x3-x2，作为加号前的数值；当x3<j时，而且i<=e时，则将i赋值为i+1，在当

前处理的数字添加号的数位的后一位添上加号，并将x3赋值为x3-x2；若i>e时，则将h赋值

为h-1，i赋值为h+1，在当前处理的数字添加号的数位的前一位添上加号，并将x3赋值为x

3-x2-a[i]。
3、当h<=0、h>e、i<=0、i>e、x3<>j时，则退出循环并打印结果“no”；当0<h<=e、0<i<

=e、x3=j时，则退出循环并打印结果“yes”。

〖参考程序〗下载

program aa;
var a,b:text;
    c:string;
    d,e,g,h,i,x1,x2,x3,xx:integer;
    f:array [1..100] of integer;

procedure bb;
begin
     assign(a,'tjh.dat');
     reset(a);
     readln(a,c,d);
     close(a);
end;

procedure cc;
begin
     for e:=1 to length(c) do
         f[e]:=ord(c[e])-48;
     x1:=0;
     x2:=0;
     x3:=0;
     xx:=1;
     h:=1;
     i:=1;
     while x3<>d do
     begin
     for g:=h to i do x1:=x1*10+f[g];
     for g:=i+1 to e do x2:=x2*10+f[g];
     x3:=x1+x2+x3;
     if x3=d then exit;
     if (h<0) or (i<0) then begin xx:=0; exit; end;
     if x3<d then
     begin
          i:=i+1;
          x3:=x3-x1-x2;
          if i=5 then begin h:=h-1; i:=h+1; x3:=x3-f[i-1]; end;
          x1:=0;
          x2:=0;
     end;
     if x3>d then
     begin
          h:=h+1;
          i:=h;
          x1:=0;
          x3:=x3-x2;
          x2:=0;
     end;
     end;
end;

procedure dd;
begin
     assign(b,'tjh.out');
     rewrite(b);
     if xx=1 then writeln(b,'yes')
             else writeln(b,'no');
     close(b);
end;

begin
     bb;
     cc;
     dd;
end.

〖练习〗

1、有一个由数字1，2，3……,9组成的数字串(长度不超过200),问如何将M(M<=20)个加号

("+")插入到这个数字串中,使所形成的算术表达式的值最小.请编一程序解决这个问题.

注意:加号不能加在数字串的最前面或最末尾,也不应有两个或两个以上的另号相邻.M保证

小于数字串的长度.
例如:数字串79846,若需要加入两个加号,则最佳方案为79+84+46,算术表达式的值为133.
--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]

--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.154]

Algorithm 版 (精华区)