递推法:穿越沙漠问题

吉普车试图穿越 x km 宽的沙漠,吉普车耗油率1L/km,总装油量 500L,对于 x > 500,吉普车需要设置临时储油点,以穿越沙漠。现在,我们需要对于输入的 x 值,计算最少的耗油量。其中, 0 ≤ x ≤ 3000.

在思考这道题之前,我们先考虑几个常识性问题:

     1、越往沙漠深处的储油点送油,所消耗的油量更多(在往返的路上必然会消耗更多的油量)

     2、要使总耗油量最少,那么需要使得绝对单位路径上的长度最小。

(其中,绝对路径指完全行驶的距离,即不再需要返回。

     3、要使得耗油量最少,那么我们需要满足以下条件:

         a、每次车应该满载而去,空载而归

         b、从第 i 个储油点将油送到第 i + 1个必然消耗的比从起点而始耗油量要少。

         c、在到达终点的时候,必然有:所有储油点、车上的油量均为0。

         d、储油点存储的油量必然是500的整数倍——这一点可由 3.a 推得。

     4、考虑将油从第 i 个储油点送至第 i + 1个的过程:假设需要送 n 趟,那么在最后一趟时,吉普车到达第 i + 1个储油点时,这时候,吉普车将没必要回到前面的储油点,假设这期间的距离为d,那么所在运输中所消耗的油量为 (2n - 1)d。

 

现在,我们有充足的知识储备来解决这道题了。

1、根据常识1,最后一个储油点应该设置在离终点500km的地方,此时耗油量最少,同时,考虑到在此时车会直接载满油冲向终点,那么最后一个储油点需要500L油。

2、我们倒推到第二个储油点。不过在这之前,我们需要证明:若在运输油的途中,若两个储油点间单位路径耗油量最少,那么需要将油从第 i 运输到第 i + 1个储油点的途中,需要吉普车满载的次数最少。

证明如下:假设满载次数为 n ,同时第 i + 1 个除油站需要 500c 的油量,那么由在途中的往、反累计 2n - 1 次——其中由于在最后将不会回返。那么设期间距离为 d,那么易得(2n - 1)d + 500c = 500n,进而得出:d = \frac{500(n - c)}{2n-1},而单位路径耗油量将以500(n - c)除以这个值,从而得到这两个储油点间单位路径耗油量为 2n - 1。(注意:我们计算的储油点的油存储量并非仅仅单个储油点的存储量,而同时包括了后续油站的存储量)显然其为n的线性函数,那么n在最小值时将取得最大值——这与路径长度无关。

而最后一个储油点需要500L的油量,那么从倒数第二个储油点出发应该至少满载两次——行驶途中必然会消耗油量。那么带入 n = 2, c = 1,得到 d = 500/3,而两次满载,也就意味着从第倒数二个储油点需要1000L的汽油——即能够支持从第倒数二个储油点到终点的汽油量。

同时,我们继续向后推,便得到倒数第三个储油点需要至少满载3次,而得到距离 d =500/5 = 100km,同时我们也能得出它需要1500L汽油支持从其到终点。

那么,显然的,我们可以观察出,在两个储油点之间 n - c = 1恒为常数,而 n 与倒数第 i 个储油点的 i 值成正相关,那么从终点到由终点起开始计数的第 n 个储油点的距离为:d_{sum} = \sum_{i = 1}^{n}\frac{500}{2n - 1} = 500\sum_{i = 1}^{n}\frac{1}{2n - 1},而该数列显然发散,因此可以从出发点走到终点。

现在,考虑在从终点开始数的最后一个储油点——它可能会多出一段并不属于该数列中的长度,我们假设它的储油点数目是n,那么由之前的推论可得,它需要500n的油量以支持从该处到达终点。同时,我们有从起点到该处的距离为:d = x - d_{sum} =x- \sum_{i = 1}^{n}\frac{500}{2n - 1} =x- 500\sum_{i = 1}^{n}\frac{1}{2n - 1} < \frac{1}{2n+1}

那么起点需要的满载的次数满足:500cnt - (2cnt - 1)d = 500n,那么起点的满载次数为:Oil = 500cnt = 500\frac{500n +d}{500-2d},那么所需要的油量就为:

 

 

以下是C语言实现:

#pragma warning(disable : 4996)
#include<stdio.h>

int main(void)
{
	int x, count = 1;
	double oil, dis = 500;   //count代表储油点的编号,同时dis表示终点前的距离
	scanf("%d", &x);
	if (x <= 500)
		oil = x;
	else
	{
		do
		{
			++count;
			dis += 500 / (2 * count - 1);
			oil = 500 * count;
		} while (dis < x);//退出循环时,dis >= x,同时储油点的数量正确

		oil = 500 * count + (x - dis) * (2 * count - 1);
		//此处的运算思路与我的不同——程序运用了油量必须用完的条件,
		//使得条件式:总耗油量油量 = 第一个储油点的油量加上路径上消耗的油量
		//其中,由于最后一次小于1/(2n + 1),因此其满载次数不变。
	}
	printf("%.2f\n", oil);
	return 0;
}

 


版权声明:本文为Ho_mu_ra原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。