当前位置:首页 >> 学科竞赛 >>

搜索及应用——向期中


万能的解题金钥匙——搜索

长郡中学 向期中

基础概念
?

?

? ? ?

?

在我们遇到的一些问题当中,有些问题不能够确切 的建立数学模型,或即便有数学模型但该模型的准 确方法也不一定能运用现成算法。在要求枚举方案 时,常常会遇到这一类问

题。 解决这一类问题,我们一般采用搜索的方法解决, 即从初始状态出发,运用题目所给出的条件和规则 扩展所有可能情况,从中找出满足题意要求的解答。 状态:指当前所面临的具体问题 转移:指从一个状态到另一状态的一种决策 状态和转移可能是题目中已经给出,也可能是需要 自己分析出的。一道题的状态与决策可能有多种。 产生式系统:把状态通过转移得到的一颗状态树, 称作产生式系统

广度优先搜索
?

在搜索算法中,我们对每个节点进行拓展, 深度越小的结点越先得到扩展,就是广度 优先搜索法,下面通过一个具体实例来讨 论广度优先算法的一般规律。

例题一
?

八数码难题:在3×3的棋盘上,摆有八个棋子,每个棋子上标 有1至8的某一数字。棋盘中留有一个空格(空格用0表示)。 空格周围的棋子可以移到空格中。要求解的问题是:给出一种 初始布局(初始状态)和目标面局(目标状态),找到一种最 少步骤的移动方法,实现从初始布局到目标布局的转变。

初始状态
? ?

目标状态

以上图为例,从初始状态到目标状态的最少步数方案如下: 将8移到空位,将7移到空位,将4移到空位,将5移到空位,将 6移到空位,将3移到空位,将2移到空位,将1移到空位。

分析
?

?

由于题目要找到的解是达到目标最少步骤,因 此解题的方法为:从初始状态出发,先把移动 一步后的布局全部找到,检查是否达到目标布 局,如果没有,再从这些移动一步的布局出发, 找到移动两步后的所有布局,再判断是否有达 到目标的,如此继续,一直达到目标状态为止, 输出结果。 由于是按移动步数从少到多产生新布局的,所 以找到的第一个目标一定是移动步数最少的一 个,也就是最优解。

分析
? ?

具体实现使用产生式系统: 那么对于当前的一个状态,我们记录如下 信息:一个3*3的矩阵ch用于表示矩阵的布 局,其中ch[i,j]表示第i行,第j列所放的数 字;为了方便程序编写,我们记录空格的 位臵(si, sj)以及深度dep,即从初始状态到 达这个状态的最少步数。

分析
?

因为新产生的结点深度(也即从初始布局 到该结点的步数)一般要比数据库原有结 点大(或相等),按步数大的后扩展的要 求,应该放在数据库的后面。而当前扩展 的结点从数据库前面选取,即符合先产生 的先扩展,后产生的后扩展规律。所以数 据库的结构用队列的结构形式较合适。用 上述记录为元素的数组data来表示数据库, 并设臵两个指针:closed为队列的首指针, open为队列的尾指针。

分析
?
? ? ? ? ? ? ? ? ? ? ? ? ?

产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一 种角度观察,也可看作空格向四周移动。这样处理更便于编程。如果 空格位臵在(si,sj),则有四条规则: (1)空格向上移动。 If si-1>=1 then ch(si,sj):=ch(si-1,sj); ch(si-1,sj):=0 (2)空格向下移动。 If si+1<=3 then ch(si,sj):=ch(si+1,sj); ch(si+1,sj):=0 (3)空格向左移动。 If sj-1>=1 then ch(si,sj):=ch(si,sj-1); ch(si,sj-1):=0 (4)空格向右移动。 If sj+1<=3 then ch(si,sj):=ch(si-1,sj); ch(si,sj+1):=0 用数组DI和HJ来表示移动的行列增量,则有: R 1 2 3 4 方向 左 上 右 下 DI 0 -1 0 1 HJ -1 0 1 0

程序实现(伪代码)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Program num8; 初始化;把初始布局存入数据库data; 设首指针closed:=0; 尾指针open:=1; Repeat Closed增1,取出队列首记录为当前被扩展结点; For r:=1 to 4 do {r是规则编号} Begin If 新空格位臵合法 then Begin Open增1,并把新布局存入队尾; If 新布局与队列中原有记录重复 then 删除新产生的布局 Else if 达到目标 then 输出并退出; End; End; Until closed>=open; {队列空} 具体程序实现参照ppt附带的num8.pas

总结与拓展
? ?

从上例可以看出,广度优先搜索法可以求出步数最少的解, 即深度最少的解。 与深度优先搜索类似,不同的问题,用广度优先搜索的基本 算法是一样的,但在数据库的表示方法、产生的结点是否符 合条件和重复的判断上可以有不同的编程技巧,程序的运行 效率也有所不同。以八数码问题为例,上面的程序中用3*3 的二维数组表示布局比较直观,但在判断重复,判断是否达 到目标方面,却给程序增加了复杂性,也影响了运行速度。 可以改用字符串形式来表示布局,第1..3个数表示第一行的 三个数,第4..6个数,表示第二行的三个数,第7..9个数表示 第三行的三个数。例如初始布局表示为“123456780”,目 标布局表示为“012563478”。

总结与拓展
? ? ? ? ? ? ? ?

产生规则也必须作相应改动。设空格当前位臵是SI,则有: (1)空格向上移动:空格的位臵减3,即交换SI和SI-3的字符; (2)空格向左移动:空格的位臵减1,即交换SI和SI-1的字符; (3)空格向右移动:空格的位臵加1,即交换SI和SI+1的字符; (4)空格向下移动:空格的位臵加3,即交换SI和SI+3的字符。 如设规则编号为k,则上述四条规则可归纳为一条: 交换SI和SI+(2*k-5)的字符 布局用字符串表示,使得判断重复过程和判断目标的过程变得 很简单,只需判断两个字符串是否相等就可以了。按照上述的 改进,读者可自己编制的解八数码问题的程序。

一般广度优先搜索的基本框架
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

根据八数码问题的基本框架,与一般广度优先搜索的基本思想,我们可以 得到如下一般广度优先搜索的基本框架。 Program BFS; 初始化;建立数据库data;初始状态存入数据库data; 设队列首指针closed:=0; 队列尾指针open:=1; Repeat Closed增1,取出closed所指结点进行扩展; For r:=1 to rmax do {r为产生规则编号} Begin If 子结点符合条件 then Begin Open增1,并把新结点存入数据库队尾; If 新结点与原有结点重复 then 删去该结点(open减1) Else if 新结点即目标 then 输出并退出; End; End; Until closed>=open; {队列空}

例题二
?

? ? ? ? ? ? ? ?

翻币问题。有N个硬币(N≥6)正面朝上排成一排,每次 将5个硬币翻过来放在原位臵,直到最后全部硬币翻成反 面朝上为止。编程让计算机找出步数最少的翻法并把翻币 过程及次数打印出来(用O表示正面,*表示反面)。 例如N=6的情况: step step step step step step step 0: 1: 2: 3: 4: 5: 6: oooooo *****o oooo** ***ooo oo**** *ooooo ******

分析
?

? ? ?

由于问题要求找出最少步骤,用广度优先搜索法 来求解。表面看,翻币的过程与正反面硬币的排 列位臵有关,但只要经过仔细分析会发现:实际 上翻币过程仅与硬币正反面的个数有关,与它们 的位臵是无关的。例如下面两种状态: O*O*O*OO ***OOOOO 都只要把5个正面朝上的硬币翻过来就达到了目标。 因此在搜索过程中只需考虑当前状态正面朝上的 个数。

分析
? ? ? ?

又如,如果当前状态是:* * * O O * * * 翻第1,2,4,6,8个得到:O O * * O O * O 而翻第3,5,6,7,8个得到:* * O O * O O O 这两种翻法虽翻的硬币不同,但都是把原状态中4 个反面朝上1个正面朝上的硬币翻过来。结果状态 不同,但都有5个硬币正面朝上,再翻一次就都可 以达到目标。所以产生规则也只需考虑翻正面朝 上的硬币的个数不同就可以了。

分析
?

?

?

?

?

?

建立产生式系统。其中:综合数据库。综合数据库 中每个记录设计为三项:当前状态中硬币正面朝上 的个数,父结点位臵,由父结点翻了几个正面朝上 的硬币得到当前状态。数据库本身用队列形式。 产生规则有六条,即翻R(0<=R<=5)个正面朝上的硬 币: if 当前结点正面朝上的硬币个数M≥R且反面朝上的 个数≥5-R then 子结点data=(M-R)+(5-R) {R=0,1, 2,……,5} 搜索策略。采用广度优先搜索法求解。 具体程序见目录下coin.pas

例题三
?

?

有两个无刻度标志的水壶,分别可装x升和 y升(x、y为整数,x、y<=100)的水,设 另有一水缸,可用来向水壶灌水或倒出水 ,两水壶间,水也可以相互倾灌。 已知x升壶为满壶,y升壶为空壶。问如何 通过倒水或灌水操作,用最少步数能在y升 壶中量出z(<=100)升的水来。

例题三
? ? ? ? ? ? ?

?
? ?

?

例如,X=5,Y=6,Z=3时,有如下方案: setp 0: x=5 y=0 setp 1: x=0 y=5 setp 2: x=5 y=5 setp 3: x=4 y=6 setp 4: x=4 y=0 setp 5: x=0 y=4 setp 6: x=5 y=4 setp 7: x=3 y=6 setp 8: x=3 y=0 setp 9: x=0 y=3

分析
?

?

?

本题要求最少步数,显然应采用广度 优先搜索。设A水壶内有a升水,B水 壶内有b升水,则最多会有六种产生规 则: (1)当a>0且b<y时,可以从水壶A倒 (a,y-b)升水给水壶B。这时水壶A内有 a-MIN(a,y-b)升水;水壶B内有 b+MIN(a,y-b)升水; (2)当b>0且a<x时,可以从水壶B倒 MIN(b,x-a)升水给水壶A。这时水壶A 内有a+MIN(b,x-a)升水;水壶B内有 b+MIN(b,x-a)升水;

A水壶

B水壶

A水壶

B水壶

A水壶

B水壶

分析
?

?

(3)当a>0时,可以从水壶A 倒a升水给水缸,这时水壶A 内有0升水.水壶B内有b升 水; (4)当a<x时,可以从水缸倒 x-a升水给水壶A;这时水 壶A内有x升水,水壶B内 有b升水;

分析
?

?

(5)当b>0时,可以从 水壶B倒b升水给水缸 ,这时水壶A内有a升 水;水壶B内有0升水 (6)当b<y时,可以从 水缸倒y-b升水给水壶 B,这时水壶A内有a 升水水壶B内有y升水

分析
? ? ? ? ? ?

?

?

初始时,水壶A内有x升水,水壶B内有0升水。 综合数据库: 可用一个记录类型描述一个状态: atype=record father,a,b:word; end; father记录当前节点的父亲节点的编号,a、b表示当前状 态中,水壶A和水壶B里各有多少水。 整个数据库可用一个以为数组DATA[1..10000] of atype;另 外用一个标志数组bool,当bool[I,j]为真,表示水壶A为I 升,水壶B为j升的状态还没有产生过,反之则表示已产生 过。使用广度优先搜索求解即可。 源程序见目录下battle.pas

例题四
?

黑白棋游戏的棋盘由4×4方格阵列构成。 棋盘的每一方格中放有1枚棋子,共有8枚 白棋子和8枚黑棋子。这16枚棋子的每一种 放臵方案都构成一个游戏状态。在棋盘上 拥有1条公共边的2个方格称为相邻方格。 一个方格最多可有4个相邻方格。在玩黑白 棋游戏时,每一步可将任何2个相邻方格中 棋子互换位臵。对于给定的初始游戏状态 和目标游戏状态,编程计算从初始游戏状 态变化到目标游戏状态的最短着棋序列。

分析
?

? ?

首先分析状态量,16个格子,每个格子可 以是黑或者白,所以状态不超过216,这个 状态量是很小的,完全可以进行广搜。 状态:一个4*4的棋盘 决策:将任何2个相邻方格中棋子互换位臵

分析
? ?

?

那么广搜的判重就可以用hash表来解决 把16个格子的黑白棋看成是一个二进制数 ,那么一个状态就对应一个数,这是最简 单的hash函数 通过这样的hash函数,hash是可以不用挂 链的

例题五

分析
?

?

看到这一问题,首先想到的自然是广度优 先搜索。但是搜索中必然会出现许多重复, 大大的增加了时空复杂度,比如连用两次 规则A显然是浪费的,因此需要判重。如果 是用传统的比较方法来排除重复的话,无 疑将花去很多的时间,事实上也的确如此。 因为,我们需要找到一种更为便捷的方法, 来进行判重。

分析
?

?

?

?

受多维数组元素地址的计算方法的启发, 可以将矩阵的每一种状态按以下规则对应 于一个双字节的整数K: (1)用一维数组S[1..8]表示一种状态。例 如初始状态S[i]=i; (2)令T[i]表示S[1..i-1]这i-1个数中,比S[i] 小的数的个数; 8 (3) K ? ? T [i ] * (i ? 1)!
i ?1

分析
?

? ?

?

?

可以证明0—40319之间的每一个整数都唯一的 对应了一个T数列,也就是说,魔板的每一个状 态都与每一个整数一一对应。 ∵n!=(n-1)*(n-1)!+(n-1)! ∴n!=(n-1)*(n-1)!+(n-2)*(n-2)!+(n-3)*(n3)!+……+2*2!+1*1!+1 n!-1=(n-1)*(n-1)!+(n-2)*(n-2)!+(n-3)*(n3)!+……+2*2!+1*1! 这一式子类似于10k-1=9*10k-1+9*10k2+……+9*100,对于上面的结论就很容易证明了。

?

?

?

因此可以用一个0—40319的布尔型映射数组,初始状态 为假。如果一种状态已经搜索到,则将其对应的数组元素 标记为真。判断一种状态是否与以前的状态重复的时候, 只需要检查该状态所对应的数组元素,若为真则该状态一 定已经搜索到了。这样省略了查找工作的时间量,虽然多 花了40k的空间,却大大提高了时间效率。 在广度搜索当中,扩张出来的新的节点总是有很大的重复, 必须对这些节点进行判重操作,最简单判重方法是相当耗 时的,它需要将新的节点与已经生成的节点分别进行比较, 在搜索的初期阶段,这一步的耗时是不明显的,但随着节 点数目增大,判重的耗时相对就大大增加,从而降低了算 法的时间效率。为了省去这一个判重工作,往往是利用数 据结构当中的哈希表。 源程序见目录下exchange.pas

哈希表的缺点
?

但是哈希表的运用并不是万能的,因为哈 希表本身也存在着一个很大的缺点,就是 其所占用的空间很大,在很多搜索问题当 中哈希表都是无法定义的,但是有的时候 表面上看来哈希表示无法定义的,但是可 以采用压缩存储的方法进行定义。看下面 这一个例题。

例题六
?

?

?

补丁与错误。(CTSC99) 错误就是人们所说的Bug。用户在使用软件时总是希望其错 误越少越好,最好是没有错误的。但是推出一个没有错误 的软件几乎不可能。所有很多软件公司都在疯狂地发放补 丁(有时这种补丁甚至是收费的)。T公司就是其中之一。 上个月,T公司推出了一个新的字处理软件,随后发放了一 批补丁。最近T公司发现其发放的补丁有致命的问题,那就 是一个补丁在排除某些错误的同时,往往会加入另一些错 误。此字处理软件只可能出现n个特定的错误,这n个错误 是由软件公司本身决定的。T公司目前公发放了m个补丁, 对于每一个补丁,都有特定的适用环境,某个补丁只有在 当前软件中包含某些错误而同时又不包含另一些错误时才 可以使用,如果它被使用,它将修复某些错误而同时加入 某些错误。另外,使用每个补丁都要耗一定的时间(即补 丁程序运行的时间)。

例题六
? ?

?

更准确地说明如下: 此字处理软件中可能出现的n个错误为集合B={b1,b2,……,bn}中 的元素,T公司目前共发放了m个补丁:p1,p2,……,pm。对于 每一个补丁pi,都有特定的适用环境,某个补丁只有在软件中 包含某些错误而同时又不包含另一些错误时才可以使用,为了 说明清楚,设错误集合:Bi-、Bi+,当软件包含了Bi+中的所有 错误,而没有包含Bi-中的任何错误时,补丁Pi才可以被使用, 否则不能被使用,显然Bi+、Bi-交集为空。补丁Pi将修复某些 错误而同时加入某些错误,设错误集合为Fi-、Fi+,使用过补 丁Pi之后,Fi-中的任何错误都不会在软件中出现,而软件将包 含Fi+中的所有错误。同样Fi-,Fi+交集为空。另外,使用每个 补丁都要耗一定的时间(即补丁程序的运行时间)。 现在T公司的问题很简单,其字处理软件的初始版本不幸包含 了集合B中的全部n个错误,有没有可能通过使用这些补丁(任 意顺序地使用,一个补丁可以使用多次),使此字处理软件成 为一个没有错误的软件。如果可能,希望找到耗时最少的方案。

分析
?

这显然是一道求最优解的题目,以各类错误的出 现情况为状态,可以计算出所有状态的总数 为 220 ? 1048576 。如果采用深度优先搜索的话, 由于递归的层数过多,是不可行的。自然想到了 广度优先搜索。但是状态判重编程是棘手的问题, 是否还能够采用哈希表呢?表面上看来,哈希表 需要的空间为 2 20 byte ? 1024Kb 。但是一个 ? 1Mb Byte型的整数,是由8个二进制为构成的,因此对 于8个布尔类型的数,可以把它压缩成占一个字节 的Byte型整数,这样一来哈希表所占用的空间就 只需要128Kb了,程序是完全可以承受的。

分析
?

?

?
? ? ?

在具体的实现过程当中,为了满足最优性,每次对权值最小的节点 进行扩展,然后对新生成的节点进行处理,如果某一个节点已经被 扩展了,就不对其进行处理。如果这一个节点处在队列之中还未被 扩展,则调整队列当中的这个节点的权值。如果这个节点既不在队 列之中,又未被扩展则加入队列当中。 对于一个状态可以把其描述成为一个01串,串的长度为错误的总个 数,0表示没有这个错误,1表示有这个错误。然后把这个01串看作 成一个二进制数,把它化成对应的十进制数,这个十进制数就是一 个对应的状态了。在搜索的过程当中,主要是利用哈希表来判断状 态是否已经进行过扩展。下面是对哈希表的定义: type TList=array[1..128]of Byte; var Hash: array[1..1024]of ^Tlist;

分析
?

?

?

将状态K(0≤K<1048576)是进行了扩展,那么把 Hash[k div 1024]^[k div 8 mod 128]←Hash[k div 1024]^[k div 8 mod 128]+2 k mod 8。在判断如果某一个 状态k已经被扩展了,那么Hash[k div 1024]^[k div 8 mod 128] div 2 k mod 8 mod 2 = 1。 状态存储的多少,是广度优先搜索的关键,为了提高 算法解决问题的规模,必须使每一个状态尽可能的简 化,存储状态也可以运用类似于上面提到的哈希表的 压缩存储方法。因此说在记录每一个状态的时候也可 以采用二进制的方法进行存储,这样一来可以大大的 减少存储的空间。 源程序见目录下bug.pas

深度优先搜索
?

深度优先搜索法,与广度优先搜索法不同 的是,它优先拓展后拓展出的节点,这种 算法也叫做回溯法,是搜索算法中的一种 控制策略,也是求解特殊型计数题或较复 杂的枚举题中使用频率最高的一种算法。 何谓深度优先搜索,首先从一个具体例子 入手,逐步引入深度优先搜索的解题的一 般规律。

例题一
?

? ?

4皇后问题:设有一个4×4的棋盘(即每行 每列有四个正方形格的棋盘),用四个皇 后布到格子中,要求满足以下条件:任意 两个皇后不在同一行或同一列或同一对角 线上。试问有多少种棋局? 例如:下列棋局便是满足方案的一种: 红圆圈表示皇后

分析
?

?

问题要求输出所有解,所以只能采用穷举的算法。 因为每一行只有一颗棋子,所以只要枚举每一行 的旗子所在的列数即可。 状态表示:用一个一维数组来描述这个4×4的棋 盘,A[I](I∈1..4)表示第I行的旗子摆在第 A[I]列。题目要求任意两个棋子不在同一行、 列、对角线,所以还需要几个数组记录某一行或 列或是对角线是否已有棋子:

分析
?
?

?

行:因为枚举是按行的,一行只有一颗棋子,所以 不必判断。 列:可以用一个b[1..4]的布尔数组记录,当b[i]=true 时表示第i列还没有棋子,否则已有棋子。 对角线:如图每个格子所在的对角线有两条,4*4的 棋盘分别有7条斜向上和斜向下的对角线,可用两个 布尔数组c,d[1..7]判断。
1 7

状态表示

2

6

3

5

4

5

6

7

1

2

3

4

分析
? ?

算法分析: 首先我们枚举第一行的棋子的列坐标I,选 定一个后,把A[1]赋值为I,把它所在的列 (I)、所在的两条对角线(I,I+3)的数 组元素赋值为false,再搜索第二行,如此 递归搜索直到第四行棋子的列坐标确定, 输出。源程序如下:

源程序
? ? ? ?

? ? ? ? ?

?
? ? ? ? ? ? ? ?

procedure try(i:integer); begin for j:=1 to 4 do if b[j] and c[i+j-1] and d[j-i+4] then begin {判断该位臵是否满足题意,即是否有 a[i]:=j; 其它棋子在同一列或同一对角线上 if i=4 then print else begin b[j]:=false; c[i+j-1]:=false; d[j-i+4]:=false; 对这个位臵所对应的标记进 try(i+1); 行赋值 b[j]:=true; c[i+j-1]:=true; d[j-i+4]:=true 将标记还原 end end end; begin {主程序} fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); fillchar(d,sizeof(d),true);{数组清零} t:=0; try(1);{搜索过程} readln End.

? ?

?

? ? ? ? ? ? ? ? ?

可以看出,深度优先搜索法有两个显著特点: (1)对已产生的结点按深度排序,深度大的先得到扩展,即先产生 它的子结点; (2)深度大的结点是后产生的,但先得到扩展,即“后产生先扩 展”。因此用堆栈作为该算法的主要数据结构,存储产生的结点。因 此,深度优先搜索的基本算法如下: 递归过程为: Procedure DFS_TRY(i); begin For I=1 to maxr do If 子结点mr符合条件 then 产生的子结点mr压入栈; If 子结点mr是目标结点 then 输出 Else DFS_TRY(I+1); 栈顶元素出栈(删去Mr) Endif
Enddo

一般深度优先搜索的基本框架

End

例题二
?

?

有p1,p2,……,pn个处理机和j1,j2,……,jm个作业, 每个作业都需要处理一定的时间ti,现在要你 将这m个作业分派到n台处理机,n台处理机可 以同步处理,使完成m个作业的时间最少。 例如,有3个作业,需要的时间分别为1,2,4, 和两个处理机,让第一台处理机处理作业1,2, 所需时间为3,让第二台处理机处理作业3,所 需时间为4,那么完成这3个作业的时间为 max{3,4}=4。

分析
?

? ? ?

首先考虑状态:因为我们需要做的这件事 情有两种方法可以做,所以状态自然就有 两种 方法一:搜索每个作业在哪台处理机完成。 方法二:搜索每台处理机处理那些作业。 两种方法状态量都比较大,为nm,所以只 能用深搜加剪枝

分析
?

?
?

?

?

发现方法二更容易剪枝。 给每个处理机定一个时间上限time[i]。 则我们可以规定time[1]>time[2]>…>time[n],使得 处理机有序化,其中time[1]便是完成所有工作的时 间。 用贪心法可以得到time[1]的上限,并且我们可以计 算出time[1]的下限,然后搜索。 贪心求上限的方法无非是构造一组可行解,使得 time[1]尽量小。比如说我们依次扫描每一个物品, 在满足time[1]>time[2]>…>time[n]的条件下,往背 包内放,这样就可以构造出一组可行解出来,我们 就可以拿这时的time[1]作为上界了。

伪代码
Procedure dfs(i:integer); i表示当前搜索到了哪一个处理机 For i:=1 to m do if (not bo[i]) and 该作业未被之前的处理机处理 (time[i]+t[i]<=time[i-1]) then 满足time[i]<=time[i-1] Begin bo[i]:=true; 标记改作业已被处理 time[i]:=time[i]+t[i]; Dfs(i+1); bo[i]:=false; 取消标记 time[i]:=time[i]-t[i]; End

例题三
生日蛋糕 条件1:V = nπ H=m层 形状:每层都是一个圆柱体。 条件2: 设从下往上数第i(1<=i<=m)层蛋糕是半径为Ri, 高度为Hi的圆柱。 当i<m时,要求Ri>Ri+1且Hi>Hi+1。 条件3: 表面积Q最小,令Q= Sπ 问题: 给出的n和m, 找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。 (除Q外,以上所有数据皆为正整数) 输入 圆柱公式 n (n<=10000), V=πR2H m (m<=20) S侧=2πRH 输出 S底=πR2 S(若无解则S=0)。

解析法?
?1? ?2? ?3?
V ? ? ? Ri * Ri * H i )
i ?1 m

Ri ? R j Hi ? H j

and and
m i ?1

1? i ? j ? m 1? i ? j ? m

其中,S ? ? ( R1 * R1 ? 2? Ri * H i ) Qmin ? min{R1 * R1 ? 2? Ri * H i }
i ?1 m

满足1, 2, 3

转变思路,搜索?
?

数据库
用( i , Ri , Hi , Vi , Si )表示第i层蛋糕的一个状态。其中Ri ,Hi分别为第i层 蛋糕的半径和高,Vi , Si分别表示做完第i层蛋糕后剩下的蛋糕体积和 当前蛋糕的表面积。可见, 初始状态:(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1) 目标状态:(m,Rm,Hm,0,Sm) 于是,我们的目标是找到一条从初始状态到任意目标状态的路径,并 且Sm最小.

?

扩展的规则

( i , Ri , Hi , Vi , Si ) ? ( i+1,Ri+1,Hi+1,Vi+1,Si+1) 满足: (1) Ri > Ri+1 (2) Hi > Hi+1 (3) Vi+1 = Vi - Ri+1* Ri+1* Hi+1 (4) Si+1 = Si + 2 * Ri+1* Hi+1

基本算法
? ? ?

?

确定第一层蛋糕的大小 根据上一层蛋糕的大小确定下一层蛋糕该怎么做 看是否符合条件 1)是否做到了m层 2)是否最终体积为0 3)是否当前面积最小 若上述条件成立,则保留当前最优值,否则继续 做下一层蛋糕,若重做蛋糕

?

Search (i, Ri , Hi , Si , Vi) {对每层蛋糕进行搜索} if (i=m) and (Vi =0) then 更新最优值 else for Ri + 1?Ri -1 downto i for Hi + 1?Hi -1 downto i [ Si + 1?Si + 2 * Ri + 1* Hi + 1 Vi + 1?Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) ]
Problem-Cake {枚举所有的初始状态 ----- 第一层蛋糕的大小} for R1?m to sqrt ( n ) do /*假设 H1=1,只做一层蛋糕 */ for H1?n div (R1*R1) downto m do [ S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) ]

?

优化??
(1)因为知道余下的蛋糕体积,因此可以估算一下余下侧面积, 这样我们可以就加入如下剪枝条件: if 当前的表面积 + 余下的側面积 > 当前最优值 then exit 设已经做了i层蛋糕,则还需做m-i层, Si’:为第i层蛋糕的侧面积, FSi:余下的侧面积,怎么求FSi ? 因为: 2Vi= 2Ri+1 * Ri+1 * Hi+1 + ...+ 2Rm * Rm * Hm = Ri+1 * Si+1’ + ...+ Rm * Sm’ ≤ Ri+1 * (Si+1’+ ...+ Sm’) = Ri+1 * FSi 所以: FSi ≥ 2Vi / Ri+1 因此剪枝条件为: if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit

优化??
(2)如果剩下的蛋糕材料太少,不能保证做到m层,那么没

有必要继续往下做了,设, 最m层半径和高都为1,Rm=Hm=1 第m-1层半径和高都为2,Rm-1=Hm-1=2 ………… 第 i +1层半径和高都为i, Ri = Hi = m – i 这样, 余下的m-i层的最小体积为

MINi ? ? k 3
k ?1

m ?i

因此,剪枝条件为, if Vi< MINi then exit

优化??
(3)如果剩下的蛋糕材料太多,以最大的方式做完m层, 仍有材 料剩余,那么没有必要继续往下做了,设, 第i+1层半径和高分别为,Ri+1 = Ri – 1 , Hi+1 = Hi –1 第i+2层半径和高分别为,Ri+2 = Ri – 2 , Hi+2 = Hi –2 ………… 第 m层半径和高分别为,Ri+m = Ri –m ,Hi+m= Hi –m 这样, 余下的m-i层的最大体积为
MAXi , R, H ? ? ( R j ? j ) 2 * ( H j ? j )
j ?i M

因此,剪枝条件为, if Vi > MAXi,R,H then exit

初始化
?

?

计算MINi for i?1 to n do [ S? S + i * i * i; MINm-i ? S ] 计算MAXi,R,H for R?1 to sqrt(n) do for H?1 to n div (R*R) do [ S? 0; for i?m downto 1 do [ S? S +(R-i)*(R-i)*(H-i); MAXi,R,H ? S ] ]

?

Search (i, Ri , Hi , Si , Vi) {对每层蛋糕进行搜索} if Si + 2 * Vi / Ri >当前最优值 then exit; {剪枝1} if Vi < MINi then exit; {剪枝2} if Vi > MAXi then exit; {剪枝3} if i<m then for Ri + 1 ?Ri downto i for Hi + 1?min(Vi div (Ri + 1*Ri + 1), Hi) downto i [ Si + 1?Si + 2 * Ri + 1* Hi + 1 Vi + 1?Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) ] Else if Vi =0 then 更新最优值 Problem-Cake 1. 计算MINi和MAXi R,H ; 2. for R1?m to sqrt ( n ) do /*假设 H1=1,只做一层蛋糕 */ 3. for H1?n div (R1*R1) downto m do [ 4. S1=2 * R1* H1+ R1* R1 5. V1=n - R1* R1 * H1 6. Search (1, R1, H1, S1, V1) 7. ]

?

小结
? 最优化剪枝
剪枝1: if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit
?

可行性剪枝
剪枝2:if Vi< MINi then exit 剪枝3:if Vi > MAXi,R,H then exit

? 剪枝原则
正确、高效

深度搜索消耗时间 ≈ 每个节点操作系数 × 节点个数

优化 1)减少节点个数——这就是剪枝优化; 2)减少每个节点的操作系数——即程序操作量。

例题四
?

?

对任意的正整数N,我们有整数方程:1/ X1+1/X2+…+1/Xn=1,该整数方程的一 个解集{x1,x2,……,xn}是使整数方程成立的 一组正整数,例如{n,n,n,…,n}就是一个解 集,在统计解集时,把数据值相同但顺序 不一样的解集认为是同一个解集,例如: 当n=3时,我们把{2,3,6}和{3,6,2}看为是同 一个解集。 现在的任务是:对于一个给定的n,m ,在最 多只允许1个xi大于m时,求出整数方程不 同解集的个数。(n<=20,m<=100)

分析
? ?

?

?

这道题只能用搜索来做,每次搜索一个Xi 首先规定搜索顺序:从小到大进行搜索, X1<=X2<=….<=Xn,因为搜索的解和顺序无 关,所以可以这么规定 最优性剪枝:因为要搜索所有解,所以无 最优性 样例:n=3 m=10 3个解

分析
?

?

?

可行性剪枝:假设当前要搜Xi ,而和已经 是t1/t2 若以后的(n-i+1) 个数都取最大值,即1/XI-1 ,也不可能达到1,则必然是无解的 如果后(n-i+1)个数中,最后一个分数无穷 小,而后(n-i)个分数都取最小值,即1/m, 它们的和也会大于1,则必然也是无解的

例题五
?

?

?

乔治有一些同样长的小木棍,他把这些木 棍随意砍成几段,直到每段的长都不超过 50。 现在,他想把小木棍拼接成原来的样子, 但是却忘记了自己开始时有多少根木棍和 它们的长度。 给出每段小木棍的长度,编程帮他找出原 始木棍的最小可能长度。(木棍数<=60)

分析
?

?

? ? ?

题目大意:给出一个序列,把它们分成k 组,使得每组和相等,求最大的k 基本思路:枚举木棍长度,再判断是否可 行。也就是说先枚举,再搜索判断。 样例:5 2 1 5 2 1 5 2 1 答案:{5,1}{5,1}{5,1}{2,2,2} 原木棍长度=6

分析
?

?

?

枚举时,拼出来的木棍长度必须符合以下 规则:不能小于原木棍长度里面最大的, 不能大于所有木棍长度之和,且所有木棍 长度之和mod该长度=0。 枚举顺序:从大到小比较好,因为可以剪 枝 枚举剪枝:如果长度为L的木棍已经判断为 不能拼出来,那么长度为L的约数的木棍也 均不能拼得

分析
?

?

?

搜索状态:哪些木棍用了,哪些木棍没用 ,当前拼到第几根木棍了 搜素顺序:先用木棍长度较大的,因为搜 索时,假设当前能用长度为s的木棍去拼( 恰能拼出已定长度),是一定比用s1, s2, s3, …, sn这n根长度较小木棍去拼要优的( 其中sum(s1, s2, …, sn) = s),也就是说先 用长度较大的拼更容易得到答案 没有最优性与可行性剪枝

例题六
?

? ?

?

n(n<=10)个点的有向完全图,每条边都有 一个实数权值,现在我们要找一条长度为n 的路使得路上的边权和最接近一个数x。 注意:每个点都有自环。 自环指的是对于一个点,存在一条边,从 这个点出发,指向这个点本身。 这条路径允许经过重复的点和重复的边。

分析
? ?

?

考虑搜索状态:将所有的路径都搜索出来。 状态量:当n=10时,状态量高达1010,所 以广搜是不行的。 那么考虑进行深搜,考虑深搜的剪枝
? ? ?

搜索顺序(无关紧要) 可行性剪枝(不行,每条路径都可行) 最优性剪枝(有可能)

经典剪枝(二分法)
? ?

?

?

我们可以将一条路径分两次搜索,每次搜一半。 先搜出所有的长度为n/2的路径,并存下来, 当做路径的前半段。 用f[i][j]数组存下所有以i结尾的长度为n/2的路 径权值和,并将j这一维按权值和排序。即f[i][1] 表示所有路径中权值和最大的, f[i][2]表示权 值和第二大的,以此类推。 然后搜后半段路径,每搜出一条路径,若这条 路径以i开头,权值和为y,则在f[i]中二分查找 一个离x-y最近的权值和,构成完整的路径。
Noi2001方程的解数也是用这个方法。

?

例题七
? ?

?

?

15数码问题。 联系8数码问题,用广搜来做,状态量太大, 有15!种状态。 所以我们确定要用深搜做。但是深搜做一 个状态会一直搜到最底层,时间无法承受。 传统的搜索已经无法适应这一道题目了。 怎么办?

引入
?

?

?

?

?

迭代加深算法:从小到大枚举ans,用深搜 判断ans是否可行。 因为ans越小越容易进行可行性剪枝。 因为ans枚举出来了,所以不存在最优性剪 枝。 其实也可以理解成枚举ans,更好地进行最 优性剪枝。 搜索顺序的优化就要根据题目讨论了。

估价函数
? ? ?

? ?

s——问题的某种状态。 h*(s)——s到目标的实际最短距离。 h(s)——s的估价函数,表示s到目标距离的 下界,h(s)<=h*(s),若h函数是相容的,则 还需要满足h(s1)<=h(s2)+c(s1,s2),其中 c(s1,s2)表示s1转移到s2的距离。 g(s)——到达s状态之前经过的距离。 f(s)——s的启发函数,f(s)=g(s)+h(s),f(s) 单调递增。

估价函数
?

当估价函数确定以后,我们每到达一个状 态s,可以用f(s)进行最优性剪枝,ans表示 当前最优答案,若f(s)>=ans,则当前状态 舍去,进行最优性剪枝。

本题的估价函数
?

?

?

考虑到每次移动时除0以外的其他数最多有 一个向目标位臵靠近一格。 所以h(s)=∑d(k,k) 1<=k<=15 h(s)满足两个条件
? ?

h(s)<=h*(s) h(s1)<=h(s2)+c(s1,s2)

A*算法与IDA*算法
?

?

?

?

将估价函数运用到广搜的算法称为A*算法, 需用堆来实现。 A*算法是理论上时间最优的算法,但所需 空间太大。 为了解决A*算法的空间问题,IDA*算法被提 出,它是将估价函数与迭代加深算法结合 起来的算法。 所以此题用深搜,通过IDA*算法进行优化即 可。

练习一下:例题八
?

?

给你一个1~n的任意排列,你需要进行最少 的操作将它变成从小到大的排列。 一次操作是指将排列中的任一段剪贴出来 并粘贴到任意位臵。

分析
?

?

?

这是一道IDA*的练习题,我们直接分析估计 函数 首先很容易想到h(s)=后继正确的个数。 但这样h(s)并不满足相容性,考虑到我们一 次操作会改变3个数的后继,所以将h(s)/3 即可。

综合运用
?

讲了这么多道对于深搜的优化, 下面请各 位尝试着想出一些对下面这道题目的优化 来。

例题九
?

给你n(n<=1000)个字符串,每个字符串长 度范围是5~11,且都由小写字母组成。现 在告诉你其实每个字符串都是一个数学等 式(其中只包括+、*、=、0..9),问你能 否确定每个字母所表示的是什么。如果能 唯一确定,则输出。

例题九
? ? ?

?
? ? ? ?

样例输入: abcdec cdefe 样例输出: a6 b* d= f+

分析
?

?

?

?

首先这题根据分析后可得到搜索量是13!, 用广搜肯定承受不了的,所以我们来讨论 深搜加剪枝。 由于此题并不存在最优值问题,所以最优 性剪枝就不可能了。 搜索顺序优化:我们要先搜索更易剪枝的 信息。 可行性剪枝:此题约束条件很多。

搜索顺序
?

?

?
? ?

= 每个等式中有且仅有一个,并且不在最 左边和最右边。 * 不在最左边与最右边且不与=,*相邻。 + 不在最左边与最右边且不与=,*,+相邻。 0 不能出现前导0。 1~9 搜完后n个等式都要满足。

剪枝一
? ?

估算等式两边的最大值与最小值。 用0或9取代所有没搜出来的字符。

剪枝二
?

若当前还未搜索的字母都已确定是多解并 且搜过的字母与当前答案一致时就可以回 溯了,没必要往下继续搜索,因为再搜索 也不会影响结果。

?

源代码见目录下ex7.pas

总结
?

通过这一次的学习,我们可以经过归纳, 总结出分析搜索问题的一般步骤,与对搜 索问题优化的大致方向。

分析搜索问题的一般步骤
? ?

?

根据题意确定出状态,并算出状态量 若状态量不是很大,直接广搜,用hash表 优化判重 若状态量很大,就深搜,可以考虑重新选 定状态或者进行深搜优化

优化
?

广搜(优化空间并不大,所以我们主要讨 论深搜)
– –

用hash表在判重时优化 与动规优化类似,优化状态量与转移。 搜索顺序优化 最优性剪枝 可行性剪枝

?

深搜
– – –

?

所有优化都是以这些为核心的。

神经网络(NOIP2003-1)
?

在兰兰的模型中,神经网络就是一张有向 图,图中的节点称为神经元,而且两个神 经元之间至多有一条边相连,下图是一个 神经元的例子

图中,X1—X3是信息输入渠道,Y1-Y2是信息输出渠道, C1表示神经元目前的状态,Ui是阈值,可视为神经元的一 个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰 的模型之中,神经网络中的神经无分为几层;称为输入层、 输出层,和若干个中间层。每层神经元只向下一层的神经 元输出信息,只从上一层神经元接受信息。

神经网络

兰兰规定,Ci服从公式:(其中n是网络中所有神经元的数目)

公式中的Wji(可能为负值)表示连接j号神经元和 i号神经元 的边的权值。当 Ci大于0时,该神经元处于兴奋状态,否则 就处于平静状态。当神经元处于兴奋状态时,下一秒它会向 其他神经元传送信号,信号的强度为 Ci 。 如此.在输入层 神经元被激发之后,整个网络系统就在信息传输的推动下进 行运作。现在,给定一个神经网络,及当前输入层神经元的 状态(Ci),要求你的程序运算出最后网络输出层的状态。 【输入格式】 第一行是两个整数 n ( 1≤n≤20 )和 p 。接下来 n 行,每行两 个整数,第 i + 1 行是神经元 i 最初状态和其阈值( Ui ),非 输入层的神经元开始时状态必然为0。再下面P行,每行由两 个整数 i , j 及一个整数 Wij ,表示连接神经元 i 、 j 的边权值 为Wij。 【输出格式】 输出包含若干行,每行有两个整数,分别对应一个神经元的 编号,及其最后的状态,两个整数间以空格分隔。仅输出最 后状态非零的输出层神经元状态,并且按照编号由小到大顺 序输出! 若输出层的神经元最后状态均为 0,则输出 NULL。

分析
?

理解问题的第一步就是认真“读题”。那么我们 先来看一看这个题目涉及的问题。研究一下题目 中所给的图的一些性质,可以发现如下特点:

1.图中所有的节点都有一个确定的等级,我们记

作Level(i) 2.图中所有的边都是有向的,并且从Level值为 i-1的节点指向Level值为i的节点
?

我们不妨将其抽象为“阶段图”。 更一般地,我们可以发现所有的阶段图都是有向 无环的,这样我们可以通过拓扑排序来得到期望 的处理节点的顺序。

可行算法
?

由于阶段图的性质使得该图的所有边所连接节点的等级都 是相邻的,因此就可以设计出一个基于宽度优先搜索(即 BFS)的算法:
1.初始时将所有输入层的节点放入队列; 2.取出队列中的一个元素,不重复地扩展并处理该节点所发出的边 的目标节点; 3.如果队列非空,则转向2; 4.输出输出层中所有满足条件的节点。

?

但是由于本题在问题描述中并没有明确的给出判断一个节 点是否是输入节点,因此需要在算法进行的过程当中额外 地考虑一些边界情况的数据(这个过程即便是真实数据没 有这样出也是要有的),下面给出的更一般的算法可能会 更好的跳过这些边界情况。
1.对原图中所有的节点进行一次拓扑排序; 2.按照拓扑顺序处理每一个节点; 3.输出输出层中所有满足条件的节点。

虫食算(NOIP2004-4)
?

【问题描述】 所谓虫食算,就是原先的算式中有一部分被 虫子啃掉了,需要我们根据剩下的数字来判定 被啃掉的字母。来看一个简单的例子: 43#9865#045 + 8468#6633 44445506978 其中#号代表被虫子啃掉的数字。根据算式 ,我们很容易判断:第一行的两个数字分别是 5和3,第二行的数字是5。

?

现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算。这里的加 法是N进制加法,算式中三个数都有N位,允 许有前导的0。 其次,虫子把所有的数都啃光了,我们只知 道哪些数字是相同的,我们将相同的数字用相 同的字母表示,不同的数字用不同的字母表示 。如果这个算式是N进制的,我们就取英文字 母表午的前N个大写字母来表示这个算式中的 0到N-1这N个不同的数字:但是这N个字母并 不一定顺序地代表0到N-1)。输入数据保证N 个字母分别至少出现一次。

?

BADC + CRDA DCCC 上面的算式是一个4进制的算式。很显然 ,我们只要让ABCD分别代表0123,便可以 让这个式子成立了。你的任务是,对于给 定的N进制加法算式,求出N个不同的字母 分别代表的数字,使得该加法算式成立。 输入数据保证有且仅有一组解,

?

【输入文件】 输入文件alpha.in包含4行。第一行有一个 正整数N(N<=26),后面的3行每行有一个由 大写字母组成的字符串,分别代表两个加 数以及和。这3个字符串左右两端都没有空 格,从高位到低位,并且恰好有N位。 【输出文件】 输出文件alpha.out包含一行。在这一行中 ,应当包含唯一的那组解。解是这样表示 的:输出N个数字,分别表示A,B,C…… 所代表的数字,相邻的两个数字用一个空 格隔开,不能有多余的空格。

?
?

样例: 【样例输入】 5 ABCED BDACE EBBAA 【样例输出】 10342 【数据规模】 对于30%的数据,保证有N<=10; 对于50%的数据,保证有N<=15; 对于全部的数据,保证有N<=26。

解决方案1
?

要求一一对应的关系,就可以枚举 这些一一对应的关系,找出符合的 一项。这样,关系总数有O(N!)个 ,最坏情况下必须枚举所有的关系 ,并且加以判断,复杂度高达 O(N*N!)!

解决方案2:
? ?

? ? ? ? ?

?

?

大体上,从算式最后一位开始模拟运算情况,当可递推时递推,不可递 推则枚举。 对于一竖列,先处理两个加数,当遇到的字母的值不确定时,则枚举当 前位(注意与前面的情况判重);否则不作为处理和,当遇到的字母的 值不确定时,可从加数部分确定的值来确定(注意与前面的情况判重和进 位);否则看加数部分确定的值是否能得到和部分(注意进位)。引出 矛盾就回溯。 如题目的样例: 5 ABCED BDACE EBBAA 它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举D,E的情况; A 则可以由D,E的值递推而来。对于倒2位, (E+C+最后一位进位) mod N=A ;E的值可以用前面的结果;枚举C;判断A是否为(D+C+最后一位 进位) mod N…… 虽然复杂度还是O(N!),但这种方法限制很多(相当于剪枝)。

?

?

观察题目的条件已经限制得很苛刻:N个变量, 每个至少出现一次;而且正好一共有N位的算式。 这样就构成了解方程的动机。这N个变量的对应N 个未知量,有N位的算式对应N个方程;N个未知 量,N个方程,正好可以得到唯一解。这里要注 意,对解的要求很严格:必须是0至N-1的每个整 数都正好出现一次。 但对每位式子的进位关系并不清楚,而进位关 系正好影响了方程的常数项。枚举每位是否进位。 用时O(2n), (因为首位不可能进位,无须枚举)。 然后,用高斯消元法来解方程。可以在枚举之前 先解出方程,枚举的时候再把参数带入。带入求 解的复杂度是O(n2) 。

解决方案3

解决方案4
?

?

?

在解决方案3的基础上,我们可以对进位的枚举剪 枝。观察这个竖列:A+B=C,若无进位则有A<=C 且B<=C; 若有进位则有A=>C且B>=C. 若能推导出A<=B 且B>=A (A,B为任何不相等 字母),则当前的枚举不可行。可用递归枚举,从 后向前枚举,处理一个竖列时则加上2个不等式, 看是否矛盾。数据结构用邻接矩阵。(规定A<=B, 再有向图中有边<A,B>)。 若加进不等式A>=B ,要加入所有x(x>=A) >=y(B>=y),枚举x,y用O(n^2)得时间。再判断是 否有x<=y 且x>=y.

传染病控制 (NOIP2003-4)

染病的传播具有两种很特殊的性质: 第一是它的传播途径是树型的,一个人 X 只可能被某个特定 的人 Y 感染,只要 Y 不得病,或者是 XY 之间的传播途径被切断, 则X就不会得病。第二是,这种疾病的传播有周期性,在一个 疾病传播周期之内,传染病将只会感染一代患者,而不会再 传播给下一代。 这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经 得到了国内部分易感人群的潜在传播途径图(一棵树)。但 是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同时 也缺乏强大的技术,以致他们在一个疾病传播周期内,只能 设法切断一条传播途径,而没有被控制的传播途径就会引起 更多的易感人群被感染(也就是与当前已经被感染的人有传 播途径相连,且连接途径没有被切断的人群)。当不可能有 健康人被感染时,疾病就中止传播。所以,蓬莱国疾控中心 要制定出一个切断传播途径的顺序,以使尽量少的人被感染。 你的程序要针对给定的树,找出合适的切断顺序 。

贪心
我们首先来通过对样例数据和其它的一些比较 简单的数据进行一些观察,很容易得到一种 贪心的算法,对这种算法可做如下的描述:

1.我们用Sum(i)表示以i为根节点的子树上的 节点总数。那么我们每次砍掉当前层中还未 砍掉的节点里面使得Sum(i)取到最大值的那 个节点; 2.重复第1步直到当前层中的节点为空。
这样在我们构造的许多数据中,这个算法 似乎总是能得到正确的结果。那么这样的算 法是否就令人满意呢?在算法的正确性没有 被彻底证明之前,尝试去找一些反例总不失 为一个好的习惯,比如说对于这个贪心算法 我们就能找到如下一个反例。

随机化搜索
1.我们通过随机函数来选择即将被砍掉的节点,可 以通过设臵权值来使得算法更大可能地去选择 “看起来最优”的决策; 2.重复第1步直到当前层中的节点为空; 3.对前两步执行多次并选取所得到的最优结果。
这个算法被设计出来以后,就很难在构造出能使这 个算法失败的数据了,因此在考场上能够设计出 来这个算法就已经很令人满意了,而事实也恰恰 如此(这个算法可以通过所有的测试数据)。

火柴棒等式
?
?

问题描述:
给你n根火柴棍,你可以拼出多少个形如“A+B=C” 的等式?等式中的A、B、C是用火柴棍拼出的整数 (若该数非零,则最高位不能是0)。用火柴棍拼数 字0-9的拼法如图所示:

?
? ?

注意:
1. 加号与等号各自需要两根火柴棍 2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A 、B、C>=0) 3. n根火柴棍必须全部用上

?

? ?

? ?

? ? ? ?

?

【输入】 输入文件matches.in共一行,仅一个整数 n(n<=24)。 【输出】 输出文件matches.out共一行,表示能拼 成的不同等式的数目。 【输入输出样例1】 matches.in matches.out 14 2 【输入输出样例1解释】 2个等式为0+1=1和1+0=1。

? ? ? ?

?
? ? ? ? ?

【输入输出样例2】 matches.in matches.out 18 9 【输入输出样例2解释】 9个等式为: 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11

解题分析
?

注意到+号和=号需要用掉4根火柴,记S(i) 为数i需要用的火柴棍数目,那么题目的要 求实质上是枚举i,j,求满足 S(i)+S(j)+S(i+j)=n-4的方案数,通过枚举可 以发现,如果i,j中任有一个数是四位数或者 四位以上,那么S(i)+S(j)+S(i+j)+4必然超过 了n,所以,我们只需要枚举所有的低于四 位的i,j数对即可,时间复杂度为10^6,比赛 的时候如果为了求稳,可以将i,j枚举的范围 设得比较大。

?

编程注意:

1、 注意最高位不能为零,即除非该 数为零,最高位不为零。 ? 2、 注意个数为0时的特殊处理。
?

?

由于给出的数据N比较小,有一 种最好的方法是直接打表输出


相关文章:
2014年信息检索期中考试
2014年信息检索期中考试_理学_高等教育_教育专区。云南...CNKI 数据库分为若干应用性、针对性的专业数据库。...先查找有 无专门的检索工具,专门的检索工具可以提供...
信息检索期中考题
信息检索期中考题_工学_高等教育_教育专区。信息检索...要查找李平老师所发表的文章,首选途径为( A ) A...项目管理在建筑工程设计管理中的应用研究 关键词:...
2014《信息技术应用》期中卷及答案
2014《信息技术应用期中卷及答案_理学_高等教育_教育...(A) 搜索的关键字越长,搜索的结果越多 (B) ...1. 明确建立网页的目标, 即确定网页需要向哪些用户...
期中测试(附答案)
期中测试(附答案)_计算机软件及应用_IT/计算机_专业...它能够提供以一列或多列的值为基础,迅速查找的功能...如果表 S(A,B,C)中,设置 A 为主键,当向 S ...
向期中考试进军
搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 初中教育 语文 ...《向期中考试进军》 向期中考试进军》亲爱的老师、同学们: 我今天国旗下演讲的...
13-14学年第二学期期中八年级综合
2013-2014 学年度第二学期中卫五中八年级期中测试卷...向某保险公司投了 20 份个人长期人身保险,保险总...这种随意搜索、 公布他人信息的做法 () A.是网民...
初中思品期中试题
下列对 “人肉搜索”认识正确地有( ) A.这触犯了刑法,应受到严厉制裁 B....①③④ 20、作为中学生向吴大观学习,要做到 ①立志航空事业,把航空发动机的研究...
期中测试
期中测试 阅读下列三遍材料, 阅读下列三遍材料,使用...(1)网站建设 网站是服装企业通向互联网的大门, ...例如在 google 3 搜索李宁,李宁公司的官方直营店排...
期中考试
期中考试_法学_高等教育_教育专区。座位号 电大天水...7、 搜索引擎 Search Engines 是一个对 Internet ...(5)向自己提问。不时地向自己询问“是什么”“...
语文基础下期中测试卷
语文基础下期中测试卷_语文_小学教育_教育专区。语文...如果有疑问,点击一下“搜索” ,一分钟后屏幕上就会...工作为我们提供了一条回归轨道的方 向。如果生命是...
更多相关标签:
数学四上期中应用题 | 计算机应用期中考试 | 搜索引擎应用 | solr应用之电商搜索 | win10搜索应用 | 应用内搜索 | 小娜打开应用变成搜索 | 应用搜索 |