沙漠穿越问题_c语言课程设计

《沙漠穿越问题_c语言课程设计》由会员分享，可在线阅读，更多相关《沙漠穿越问题_c语言课程设计（9页珍藏版）》请在毕设资料网上搜索。

1、 课课 程程 设设 计计 报报 告告 学院、系： 专业名称： 计算机科学与技术 课程设计科目 C 语言程序课程设计 所在班级： 学生学号： 学生姓名： 指导教师： 完成时间： 2012 年 4 月 15 日 穿越沙漠问题 一、设计任务与目标 穿越沙漠问题：一辆吉普车穿越 1000 公里的沙漠，吉普车的总装耗油量为 500 加仑，耗油率为每小时 1 加仑。由于沙漠中没有油库，必须先用这辆车在沙漠中 建立临时油库。 请编程求解，若让吉普车用最少的耗油量穿越沙漠，应该在那些地方建立临时油 库，在每个临时油库存储的油量应该是多少。 具体要求如下； (1) 运行程序后直接输出结果； (2) 显示输出界面

2、； (3) 分条显示结果。 二、方案设计与论证 穿越沙漠问题，是一个极值问题。为达到让吉普车用最少的耗油量穿越沙漠，则 说明该问题只有唯一解。而从问题中我们可以看出， 显然吉普车是不能一次就穿 越沙漠的，需要采取推进的方法，也就是在沙漠中前进一定的距离后就要建立临 时油库为接下的路程做准备。而我们从题目中可以知道最基本的信息，比如必须 要走奇数次，这样才能确保最后到达终点方向。然而我们又要保持效率，就要满 足向终点时要满载和每个储油点都要储油点需要的和路上消耗的油量。 而针对这个问题，我们可以采取倒推的方法进行求解，从终点往起点推，然后记 录每个储油点的位置和储油量。而相反，正推是不可能的，因

3、为我们不知道第一 个储油点与起点的距离，但却可以知道最后一个储油点与终点相距 500km。 而我们可以推出，详细情况如下图： 我们必须要做到 i 与 i+1 点之间往返若干次，而且每次到达 i+1 处，吉普车的油 要消耗完，每次从 i+1 处出发的时候，又要装满油。所以我们可以知道，两点之 间的距离必须满足在耗油最少的条件下，使 i点存够 i*500 加仑汽油的要求。取 第一个例子来说，第一个储油点 i=1 应该距离终点 i=0 处 500km，而且应该在那 个储油点存放 500 加仑汽油，这样才能保证吉普车能从 i=1 处到达终点 i=0 处。 此时我们将距离设为 distance，储油点存

4、放油量设为 oil。那么从这个例子中我们 知道，distance1=500,oil1=500。 那么继续推导，为了在 i=1 处存放 500 加仑汽油，那么吉普车至少从 i=2 处开两 趟满载油的车道 i=1 处。所以我们可以知道 i=2 处至少要存放 2*500=1000 加仑 汽油，即 oil2=1000。加上从 i=1 返回至 i=2 处一趟空载，总共往返三次。而在 这三次往返路程的耗油量按要求只能为 500 加仑，即 distance12=500/3km。那么 我们可以继而推出 distance2=distance1+distance12=500+500/3。 为了直观的了解情况，详情

5、情况如下图： 而同样的，为了在 i=2 处存放 1000 加仑汽油，吉普车至少从 i=3 处开三趟装满 油的车至 i=2 处。所以 i=3 处至少存放 3*500=1500 加仑汽油，即 oil3=1500。 加上前面一段的返程空车，总共五次往返。路途的耗油量也应为最低标准的 500 仑，即distance23=500/5。而可以得出 distance3=distance2+distance23=500+500/3+500/5。 详情情况如下图： 所以我们继续推导下去的话， 我们可以发现： 为了在 i=k 处存放 k*500 加仑汽油， 吉普车至少要从 i=k+1 处开 k 趟载满油的车到 i

6、=k 处。而我们根据前面例子的公 式可以推出:oilk+1=(k+1)*500=oilk+500，加上从 i=k 处返回 i=k+1 的返趟，总 共 2k-1 次 。 而 同 样 的 这 2k-1 次 的 总 耗 油 量 都 按 照 最 低 标 准 ， 即 distancekk+1=500/(2k-1)， distancek+1=distancek+distancekk+1=distancek+500/(2k-1)。 而我们现在可以知道最后 i=n 至终点的距离为 1000-distancen，oiln=500*n。 为了在 i=n处取得 n*500 加仑汽油，吉普车至少从始点开 n+1 次满载车到 i=n， 加上 i=n 返回始点的 n 趟返程空车，总共 2n+1 次，而这总耗油量为 (1000-distancen)*(2n+1)，即始点存放油量为 oiln+(1000-distancen)*(2n+1)。 则我们可以通过输入代码来求出我们想得到的值。 三、程序框图或流程图，程序清单与调用关系 int