pascal中级教程第一章回溯法

1.9 驾车旅游

源程序名 tour.???（pas, c, cpp） 可执行文件名 tour.exe 输入文件名 tour.in 输出文件名 tour.out 【问题描述】

如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价(如3.25元/L)。驾车者一般都有以下的习惯：

（1）除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来； （2）在第一个停下的加油站总是将油箱加满；

（3）在加油站加油的同时，买快餐等吃的东西花去20元。 （4）从起始城市出发时油箱总是满的。

（5）加油站付钱总是精确到0.1元(四舍五入)。

（6）驾车者都知道自己的汽车每升汽油能够行驶的里程数。 现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。 【输入】

第一行是一个实数，是从出发地到目的地的距离(单位：km)。

第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量(单位：I。)；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用(单位元)；一个整数是1到50间的数，表示从出发地到目的地线路上加油站的数目。

接下来n行都是两个实数，第一个数表示从出发地到某一个加油站的距离(单位：km)；第二个实数表示该加油站汽油的价格(单位：元)。 数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离。 【输出】 就一个数据，是精确到0.1元的最小的加油和吃饭费用 【样例】 tour.in tour.out 600 379.6 40 8.5 128 3 200 3.52 350 3.45 500 365 【算法分析】

驾车者从出发地出发后对于每个加油站都可能有两种操作，一是进去加油买食品，二是不进去继续前行(如果当前汽车的余油可以的话)，这样有n个加油站最多可能有2n种选择。由于加油站数目不太多，可以采用回溯的算法来解决问题。从第一个加油站开始，依次选择所要停下的下一个加油站，从而找出总费用最少的方案，加油站数目最多为50，这样回溯不会进行得很深。在选择下一个要停下的加油站时比较麻烦，不能完全一个一个地试过去，

这样时间太长。可以用这样的方法：先找出第一个要停下的加油站，判断其后面的加油站是否可以到达，如果不可到达就必须在这里停下来加油；否则就找出可以到达但如果只用一半汽油则无法到达的所有加油站，依次进行停靠。

1.10关路灯

源程序名 power.???（pas, c, cpp） 可执行文件名 power.exe 输入文件名 power.in 输出文件名 power.out 【问题描述】

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

现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。 【输入】

文件第一行是两个数字n(0

接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。 【输出】 一个数据，即最少的功耗(单位：J，1J＝1W·s)。 【样例】 power.in power.out 5 3 270 {此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序} 2 10 3 20 5 20 6 30 8 10

【算法分析】

设老张开始所在位置为c，以起始点c为分界点，算出左右两部分总的功率p_left和p_right，再来分别看向左与向右的情况。

向左走时，相应地可以减小左边应费的功，而增加右边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_left+w[i])*t，增加的功为p_right*2t。

向右走时，相应地可以减小右边应费的功，而增加左边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_righ+w[i])*t，增加的功为p_left*2t。

比较向左与向右的情况，找出比较好的一种确定方法。大部分情况能够解出最小值，但不能求出所有情况下最佳的解。

对于每一个所处位置，都可以选择向左或向右，不管是向左还是向右，相应耗电的变化都跟上面所述一样。所以可以选择回溯的算法来实现有限的搜索，对每一个点试探向左与向

右的情况，在所有可能的情况中找出最优解。 【思考与提高】

上面的程序运算的范围很有限，当n比较大时就会栈溢出，如n>30时速度就比较慢了。实际情况调头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考：

最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种； 最后一次关的是第一个灯的话，说明最后的方向是从最后到最前(右边到左边)，最后倒数第二次的方向为从左到右，起点可能是原始起点(此时是第一趟)，也可能是原始起点左边的点(此时至少是第二趟)，一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。

如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度去思考。