C语言程序课程设计--沙漠穿越问题

《C语言程序课程设计--沙漠穿越问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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加

4、仑汽油，这样才能保证吉普车能从i=1处到达终点i=0处。此时我们将距离设为distance，储油点存放油量设为oil。那么从这个例子中我们知道，distance[1]=500,oil[1]=500。那么继续推导，为了在i=1处存放500加仑汽油，那么吉普车至少从i=2处开两趟满载油的车道i=1处。所以我们可以知道i=2处至少要存放2*500=1000加仑汽油，即oil[2]=1000。加上从i=1返回至i=2处一趟空载，总共往返三次。而在这三次往返路程的耗油量按要求只能为500加仑，即distance12=500

5、/3km。那么我们可以继而推出distance[2]=distance[1]+distance12=500+500/3。为了直观的了解情况，详情情况如下图：而同样的，为了在i=2处存放1000加仑汽油，吉普车至少从i=3处开三趟装满油的车至i=2处。所以i=3处至少存放3*500=1500加仑汽油，即oil[3]=1500。加上前面一段的返程空车，总共五次往返。路途的耗油量也应为最低标准的500仑，即distance23=500/5。而可以得出distance[3]=distance[2]+distance23=

6、500+500/3+500/5。详情情况如下图：所以我们继续推导下去的话，我们可以发现：为了在i=k处存放k*500加仑汽油，吉普车至少要从i=k+1处开k趟载满油的车到i=k处。而我们根据前面例子的公式可以推出:oil[k+1]=(k+1)*500=oil[k]+500，加上从i=k处返回i=k+1的返趟，总共2k-1次。而同样的这2k-1次的总耗油量都按照最低标准，即distancekk+1=500/(2k-1)，distance[k+1]=distance[k]+distancekk+1=distance[

7、k]+500/(2k-1)。而我们现在可以知道最后i=n至终点的距离为1000-distance[n]，oil[n]=500*n。为了在i=n处取得n*500加仑汽油，吉普车至少从始点开n+1次满载车到i=n，加上i=n返回始点的n趟返程空车，总共2n+1次，而这总耗油量为(1000-distance[n])*(2n+1)，即始点存放油量为oil[n]+(1000-distance[n])*(2n+1)。则我们可以通过输入代码来求出我们想得到的值。三、程序框图或流程图，程序清单与调用关系intkk=k+1!(d>

8、=1000)distance[k]-1000i=0ivoidmain(){intk;/*定