?head?tail?1???2?。 左区间： head‥?连接到左区间开关的导线集合为p1。初如时p1={1

‥m}；

?head?tail?1???2?+1‥tail。连接到右区间开关的导线集合为p2。初始时 右区间： ?p2={}。

待连接的开关状态是同一的，设为state：

?1state???0

待连接的所有开关闭合;待连接的所有开关断开;

初始时，所有开关断开，state=0。我们将开关和导线问题表示为

check (p1，开关区间，state)

即开关区间的当前状态为state。确定p1集合中的哪些导线与该区间中的开关相连，与导线i（i∈p1）相连的开关序号设为ans[i]。 １、分解

若p1非空且当前开关区间至少两个开关((p1<>[ ])and (head<>tail))，则将之一分为二：

?head?tail?1???2?，与之相连的导线集合最初设为p1； 左开关区间：head‥??head?tail?1???2??+1‥tail，与之相连的导线集合p2，最初设为{}； 右开关区间：

然后，经过下述测试，将p1中不与左区间内的开关相连的导线移出，移入p2：

通过c命令和用户应答将左区间的所有开关取反。（开关状态为1-state）。分别对p1中的每根导线发出T命令：若开关状态为闭合且用户应答’N’，或者开关状态为断开且用户应答’Y’((state=0)and (c=‘N’)or (state=1)and (c=‘Y’))，则确定当前导线不与左区间开关相连。该导线从p1集合移出，移入p2集合。

2、解决

递归解两个子问题：

check(p1，左区间，1-state)； check(p2，右区间，state)；

3、合并

若当前开关区间仅剩一个开关(head=tail)且与之相连的导线集合p1非空，则确定p1集合中的所有导线与head开关连接：

ans[i]=head (i∈p1， 1≤i≤m) 由此得出算法：

procedure check (p1，head，tail，state)； begin

if p1<>[ ] {若有导线与区间内的开

关连接}

then if head=tail {若区间仅剩一个开关，则p1集合中的所有导线与之相连}

then for i：=1 to m do if i?p1 then ans[i]←head else begin

?head?tail?1???2?； {计算左区间 i←?尾指针}

for j：=head to i do {通过c命令和用户应答，将左区间的开关状态取反}

begin

输出改变开关j状态的命令cj；输入用户应答； end；{for}

p2←[ ]； {连接右区间开关的导线集合设空}

for j：=1 to m do {测试p1中的每一根导线}

begin

if j? p1 then begin

输出测试导线j的命令Tj； 读用户应答c；

if (state=0)and (c=‘N’)or (state=1)and (c=‘Y’)

then {计算连接右开关区间的导线集合p1和连接右开关区间的导线集合p2}

begin p1←p1-[j]； p2←p2+[j]；end；{then} end；{then} end；{for}

check(p1，head，i，1-state)； {完成p1中导线与左区间开关的连接}

check(p2，i+1，tail，state)； {完成p2中导线与右区间开关的连接}

end；{else} end；{check}

显然，初始时设p1={1‥m}。递归调用check(p1，1，m，0)后得出的ans[1]，ans[2]，?，ans[m]组成了D命令。

§5．3 归纳策略

如果说对应策略的思维核心是举一反三、触类旁通地对已经解决的类似问题和有关事实作联想，外推出事物间的联系的话，那么归纳策略则是通过列举试题本身的特殊情况，经过深入分析，最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。归纳法要比搜索的方法（例如以后将讲解的枚举法、回溯法等）更能反映问题的本质。但是并不是所有实际问题都可以总结归纳出一般规律，即便是可以，归纳也不是一件容易的事情，尤其要归纳出一个数学模型更为困难。而且归纳过程通常没有一定的规则可供遵循。从本质上讲，

归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。通常，归纳的过程分以下四个步骤： ⑴细心的观察 ⑵丰富的联想 ⑶继续尝试

⑷总结归纳出结论

归纳是一种抽象，即从特殊现象中找出一般关系。但在归纳过程中不可能列举所有情况，因而最后得出的结论还只是一种猜测（即归纳假设）。通过精心观察而提出的归纳假设得不到证实或最后证明是错的，也是常有的事。因此归纳假设尽可能加以严格的证明，证明的方法通常使用数学归纳法。即便找不到证明方法，也必须尽可能多地提出那些容易出错和疏漏的边界情况加以验证，使归纳出的结论和解决问题的途径经得起各种测试数据的检验。 问题经过分析归纳后，一般产生四种结果

? 递推式 ? 递归式 ? 制定目标 ? 贪心方案

当然，经过分析直接概括出高度抽象的数学公式亦是一种归纳过程、一种解题的途径。但是怎样进行这种归纳，这个问题太宽泛，与其说它是计算机算法的策略，还不如说它是一种数学知识和数学能力，取决于解题者本身的数学功底。我们已经在对应策略一节中，对如何将试题与数学公式对应的问题作了4一些讨论（主要围绕试题展开），这里不再赘述。

一、递推法

有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：

Fn ＝g (Fn-1 ) 或者Fn-1 ＝g’(Fn )

这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件(或最终结果)入手，一步步地按递推关系式递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项数与前一项数的关系并清楚其起始条件(或最终结果)，问题就好解决，让计算机一步步算就是了。让高速的计算机从事这种重复运算，可真正起到“物尽其用”的效果。递推分倒推法和顺推法两种形式。一般分析思路：

if 求解初始条件F1 then begin {倒推}

由题意(或递推关系)确定最终结果Fn ； 求出倒推关系式Fi-1 ＝g’(Fi )；

i←n； {从最终结果Fn 出发进行倒推}

while Fi≠F1 do begin 由Fi-1＝g(Fi )倒推Fi-1；i←i-1；end；{while} 输出倒推结果F1 和倒推过程； end{then} else begin {顺推}

由题意(或递推关系)确定初始值F1(边界条件)；

求出顺推关系式Fi ＝g (Fi-1 )；

i←1； {由边界条件F1出发进行顺推}

while Fi≠Fn do begin由Fi＝g(Fi-1 )顺推Fi+1；i←i+1；end；{while} 输出顺推结果Fn和顺推过程； end；{else}

我们至所以将递推法划入归纳策略，是因为初始条件（或最终结果）除试题已明确给定外，都是通过对问题的整理与化简而确定的，其递推式也是对实际问题的分析与归纳而得到的。因此递推本质上属于归纳。

1、倒推法

所谓倒推法，就是在不知初始值的情况下，经推理而获知问题的最终解或目标，再倒过来，推知它的初始条件。因为这类问题的运算过程是一一映射的，故可分析得其倒推公式。然后再从最终解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。下面举例说明。

【例题三十二】贮油点

一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个贮油点，使卡车能顺利穿越沙漠，试问司机如何建立这些贮油点？每一贮油点应存多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？

编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。 No． distance(k．m．) oil(litre) 1 ×× ×× 2 ×× ×× 3 ×× ××

算法分析

设dis[i]─第i个贮油点至终点(i=0)的距离； oil[i]─第i个贮油点的存贮油量； 我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。(图5．3-1)表示倒推时的返回点。

终点 始点 └───────────┬──┬──────────────┬┘ i=0 i=1 i=2 ? ?i=n ( 图5．3-1)

从贮油点i向贮油点i+1倒推的策略是，卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油，而每次从i+1处出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500公升汽油的要求(0≤i≤n-1)。具体地讲，第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说 dis[1]=500； oil[1]=500

为了在i=1处贮藏500公升汽油，卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2