pascal中级教程第一章回溯法.doc

《pascal中级教程第一章回溯法.doc》由会员分享，可在线阅读，更多相关《pascal中级教程第一章回溯法.doc（24页珍藏版）》请在三一文库上搜索。

1、第一章 回溯法1.1 马拦过河卒源程序名 knight.?（pas, c, cpp）可执行文件名 knight.exe输入文件名 knight.in输出文件名 knight.out【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【输入】

2、一行四个数据，分别表示B点坐标和马的坐标。【输出】一个数据，表示所有的路径条数。【样例】knight.in knight.out6 6 3 36【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。1.2出栈序列统计 源程序名 stack1.?（pas, c, cpp）可执行文件名 stack1.exe输入文件名 stack1.in

3、输出文件名 stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，n，经过一系列操作可能得到的输出序列总数。【输入】一个整数n（1=nY被用来表示当集合X中的域被赋值后，集合Y的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号”（S）、“姓名”（N）、“地址”（A）、“电话”（P）的域，并且每个人都与某个特定的互不相同的S值

4、相对应，根据域S就可以确定域N、A、P的值。这就记作S-NAP。 写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如，如果组里包括依赖A-B、B-C和A-C，那么第三个依赖是冗余的，因为域C可以用前两个依赖得到（域A确定了域B的值，同样域B确定了域C的值)。在A-B、B-C、C-A、A-C、C-B和B-A中，所有的依赖都是冗余的。 现在要求你编写一个程序，从给定的依赖关系中找出冗余的。【输入】输A的文件第一行是一个不超过100的整数n，它表示文件中函数依赖的个数。从第二行起每一行是一个函数依赖且互不重复，每行包含用字符“-”和“”隔开的非空域列表。

5、列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如A-A）。虽然文件中没有对函数依赖编号，但其顺序就是编号1到n。【输出】每一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的，先是一个FD，然后是依赖函数号，接着是is redundant using FDs：”最后是说明的序列号。如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些函数依赖中不包含冗余依赖，则输出“No redundant FDs”信息。【样例1】【样例2】redund.inredund.out redund.in redund.out3FD 3

6、is redundant using FDs: 1 2 6 FD 3 is redundant using FDs: 1A-BD即C可以通过1、2得到 P-RST FD 5 is redundant using FDs: 4 6 2BD-C VRT-SQPA-C PS-TQ-TRQS-PSR-V【算法分析】一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？假设判断的依赖为“a-b”，先找出所有形式为“a-*”的依赖，再由*开始找相关依赖，直到出现“#-b”为止(这里a、b、*、#都表示任意一个域名)。如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗

7、余(如果有的话)还不说明工作就已结束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的(最短的也可能并不惟一，因此本题答案有可能并不惟一)，最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证明序列中就有可能还有冗余依赖。1.5走迷宫 源程序名 maze.?（pas, c, cpp）可执行文件名 maze.exe输入文件名 maze.in输出文件名 maze.out【问题描述】 有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这

8、个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。【输入】 第一行是两个数m，n(1m，n”表示方向。如果没有一条可行的路则输出-1。【样例】maze.in5 61 0 0 1 0 11 1 1 1 1 10 0 1 1 1 01 1 1 1 1 01 1 1 0 1 11 15 6maze.out(1,2)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)

9、-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(3,4)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(4,4)-(4,5)-(5,

10、5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(4,3)-(4,4)-(3,4)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2

11、,3)-(3,3)-(4,3)-(4,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)【算法分析】 用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：14x,y23对应的位置为：(x-1, y)，(x, y+1)，(x+1, y)，(x, y-1)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应

12、点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。 这个查找过程用search来描述如下：procedure search(x, y, b, p)；x，y表示某一个点，b是已经过的点的情况，p是已走过的路 begin for i:1 to 4 do分别对4个点进行试探 begin 先记住当前点的位置，已走过的情况和走过的路； 如果第i个点(xl，y1)可以走，则走过去； 如果已达终点，则输出所走的路径并置有路可走的信息， 否则继续从新的点往下查找search(xl，y1，b1，p1)； end； end；【思考与提高】该程序通过引进新的变量和数组来继

13、续新的查找，如果不引进新的变量和数组，那么每一次返回时要将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想换条路再试。这类问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束程序时，在程序的输出部分后面加上一个halt就行了。 有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”明显无用的节点可以先行“剪掉”，从而提高搜索速度。1.6 单向双轨道 源程序名 tr

14、ack.?（pas, c, cpp）可执行文件名 track.exe输入文件名 track.in输出文件名 track.out【问题描述】入口A出口DB C 如图所示l，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站(从左到右以a、b、c、d编号)，右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。 从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“h L R”的字母序列，其中h为火车编号，L为h车原先所在位置(位置都以A、B、C、D表示)，R为新

15、位置。或者输出NO表示不能完成这样的调度。【输入】一个数n(1n27)及由n个小写字母组成的字符串。【输出】可以调度则输出最短的调度序列，不可以调度时则输出NO。【样例】track.intrack.out3c A Bcbab A Ca A Db C Dc B D【算法分析】 这是一道类似于栈的操作题目，只不过是有两个栈B和C可以操作，而对于A序列里的元素，既可以进入B，也可以进入C，或直接到D。解决问题可以从D序列出发反过来看，当前要到D的字符在哪里，如果在A，再看它前面有没有字符，如果有，先让它们进栈(B或C)，否则直接到D；如果在B，看是否是栈顶元素，如果是，直接到D，否则将上面的字符进C

16、；如果在C，看是否是栈顶元素，如果是，直接到D，否则无法进行操作，因为只能向右不能向左，这时要回溯。如果所有的情况都检测过，某个字符不能进行到D的操作，则输出无解信息。 由于A里的非直接进入D的字符可以进入B或C，可以跟二进制建立起对应关系，将所有情况列举一遍，再找出其中步骤最少的输出。1.7组合的输出 源程序名 track.?（pas, c, cpp）可执行文件名 track.exe输入文件名 track.in输出文件名 track.out【问题描述】 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且rn)，我们可以简单地将n个元素理解为自然数1，2，n，从中任取

17、r个数。 现要求你不用递归的方法输出所有组合。 例如n5，r3，所有组合为： l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5【输入】一行两个自然数n、r(1n21，1rn)。【输出】 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。【样例】compages.incompages.out5 31 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5【算法分析】如果通过循环加递归来实现回溯比较简单，相应程序为：const

18、 max=20;var a:array0.maxof integer; n,r:1.max;procedure compages(k:integer);选取第k个元素 var i,j:integer; begin当前所选元素最小为前一个元素加1，最大为n-(r-k)，因为后面还有(r-k)个元素要选取，至少为每次选取留一个 for i:=ak-1+1 to n-(r-k) do begin ak:=i; 选取一个元素 if k=r then begin for j:=1 to r do write(aj:3); writeln; end else compages(k+1); end; end

19、;begin main readln(n,r); compages(1); 从第一个元素开始选取给合数end. 本题要求不用递归来实现回溯，关键要定好回溯的条件。如果选取第i个元素时选择了ai，根据输出条件应有ai-in-r，如果不满足这个条件说明当前第i个元素已再无数可取，要进行回溯，将其值减1，退到上一步将上一步原来的值再增加1，重复上述过程。当全部选取完时，i回到了0，a0的值增加1后变为1，这是整个选取过程结束的条件。1.8售货员的难题 源程序名 salesman.?（pas, c, cpp）可执行文件名 salesman.exe输入文件名 salesman.in输出文件名 sales

20、man.out【问题描述】 某乡有n个村庄(1n40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0s1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。【输入】村庄数n和各村之间的路程(均是整数)。【输出】最短的路程。【样例】salesman.in salesman.out3 村庄数30 2 l 村庄1到各村的路程1 0 2 村庄2到各村的路程2 1 0 村庄3到各村的路程【算法分析】 题目给定的村庄数不多(40)

21、，所以可以用回溯的方法，从起点(第一个村庄)出发找出所有经过其他所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。用一个过程road(step，line：byte)来描述走的状况，其中step是当前已到村庄数、line是当前所在的村庄。如果stepn，下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值的路径可能不止一条，不便于测试，题目没要求输出路径)。如果step还小于n，那么将还没有到过的村庄一个一个地试过去，再调用下一步road(step+1，新到的

22、村庄号)。1.9驾车旅游 源程序名 tour.?（pas, c, cpp）可执行文件名 tour.exe输入文件名 tour.in输出文件名 tour.out【问题描述】 如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价(如3.25元/L)。驾车者一般都有以下的习惯： （1）除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来； （2）在第一个停

23、下的加油站总是将油箱加满； （3）在加油站加油的同时，买快餐等吃的东西花去20元。 （4）从起始城市出发时油箱总是满的。 （5）加油站付钱总是精确到0.1元(四舍五入)。 （6）驾车者都知道自己的汽车每升汽油能够行驶的里程数。 现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。【输入】 第一行是一个实数，是从出发地到目的地的距离(单位：km)。 第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量(单位：I。)；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用(单位元)；一个整数是1到50间的数，表示从出

24、发地到目的地线路上加油站的数目。 接下来n行都是两个实数，第一个数表示从出发地到某一个加油站的距离(单位：km)；第二个实数表示该加油站汽油的价格(单位：元)。 数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离。【输出】就一个数据，是精确到0.1元的最小的加油和吃饭费用【样例】tour.intour.out600379.640 8.5 128 3200 3.52350 3.45500 365【算法分析】 驾车者从出发地出发后对于每个加油站都可能有两种操作，一是进去加油买食品，二是不进去继续前行(如果当前汽车的余油可以的话

25、)，这样有n个加油站最多可能有2n种选择。由于加油站数目不太多，可以采用回溯的算法来解决问题。从第一个加油站开始，依次选择所要停下的下一个加油站，从而找出总费用最少的方案，加油站数目最多为50，这样回溯不会进行得很深。在选择下一个要停下的加油站时比较麻烦，不能完全一个一个地试过去，这样时间太长。可以用这样的方法：先找出第一个要停下的加油站，判断其后面的加油站是否可以到达，如果不可到达就必须在这里停下来加油；否则就找出可以到达但如果只用一半汽油则无法到达的所有加油站，依次进行停靠。1.10关路灯 源程序名 power.?（pas, c, cpp）可执行文件名 power.exe输入文件名 pow

26、er.in输出文件名 power.out【问题描述】 某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能

27、会更省一些。 现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。【输入】 文件第一行是两个数字n(0n50，表示路灯的总数)和c(1c30时速度就比较慢了。实际情况调头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考： 最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种； 最后一次关的是第一个灯的话，说明最后的方向是从最后到最前(右边到左边)，最后倒数

28、第二次的方向为从左到右，起点可能是原始起点(此时是第一趟)，也可能是原始起点左边的点(此时至少是第二趟)，一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。 如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度去思考。1.5走迷宫 源程序名 maze.?（pas, c, cpp）可执行文件名 maze.exe输入文件名 maze.in输出文件名 maze.out【问题描述】 有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可

29、以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。【输入】 第一行是两个数m，n(1m，n”表示方向。如果没有一条可行的路则输出-1。【样例】maze.in5 61 0 0 1 0 11 1 1 1 1 10 0 1 1 1 01 1 1 1 1 01 1 1 0 1 11 15 6maze.out(1,2)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,

30、5)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(3,4)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(

31、5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(4,3)-(4,4)-(3,4)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(4,3)-(4,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)【算法分析】 用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪