彻底解决了穿越沙漠问题:
穿越沙漠问题,呵呵,终于弄明白了,原题我就不复述了,这倒题要使用逆推法.就是求最优化,最省油的办法,
从前边开始推倒你会觉得无从下手,束手无策,呵呵,这道题憋屈我一个礼拜了,
逆推法,就是从汽车最后一次开出沙漠起推倒,因为它是要求最节省油的方法,所以,我们,可以知道,最后一次开出沙漠,前加的油必然是500L,然后开出沙漠,没有浪费一滴油,就是,到最后一个加油站,加满500L,然后开出沙漠,所以,最后一个加油站储藏的必然是500L的油,
我们用一个变量K来存储加油站的个数,既然是倒推,也就是k=1的时候,加油站里边有500L油,然后逆推到第二个加油站,可以这样想,要想满足第一个加油站有500L油,那么第二个加油站需要放多少呢?有一点我们肯定知道,就是肯定是比500大的,如果距离很长,往后边还要排好多加油站的话,最多比500多500L,也就是1000L是做多的了,需要输入油多少次呢, 因为距离过程中需要消耗油,所以去一次肯定不能直接存500L,肯定这个数值是小于500,所以至少需要两次,第一次是往反的,第二次在送去就够了,旧不用再回去了,就是3次
所以 向第一个加油站运送500L油的任务需要3次来完成,如果后边还有很多个加油站的话,我想,最大化,第二个加油站就是存1000L,最大化是个问题,后边我们再说,最大化,就是一个汽车最多带500升,
那么它需要平均分出3份,去一份,放那一份,回来一份,也就是去是500/3,放那500/3,回来500/3,再去,500/3,放那500/2,凑够500,加满油,就开出去了。
所以倒数第二个油战需要放1000升油,也就是分三次送完,路程就是500/3,耗油量就是1000升,接下来,再来推导要想保持倒数第二个油战有1000升,首先估算一下需要的送几次,肯定每次送到的油都小于500,因为还有路程可走,还得耗油,不可能直接飞过去呀,所以呀,呵呵,两次不到1000,只能是3次,单向3次,你想还得回来取两次油呀,所以就是5次,最后一次就直接往前开了,估算出了5次,是吧?下面我们就可以这样想了,我们要送前一个加油站1000升油,途中用油最少是500升,那么它走过的路程就是500/5,第三个加油站就得准备1500升,如此,战的数量和汽车往返的次数就形成了一个数量关系,就是2*k-1,,当然公里数就是 500/2*k-1,知道了这个程序就不难写了,
大家都知道了吗? 为了便于理解,我再换一种思维,也为了自己掌握的巩固和提高,
就是怎么的呢。
问题1, 如果这段沙漠就500公里长,好,就在起始点加满500生,一路彪过去,欧了,呵呵,
问题2,如果这段沙漠是600公里,也就是比500公里大,怎么办,还是按照刚才上边的方法,逆推法,当然,逆推不了几步,就是为了简单明了才选择600公里的,呵呵,逆推法,再500公里处,建设一个500升容量的加油站,那么要再起始点放多少油呢,按照上边的推导,肯定要放3次,600-500,这个很有用的啊,就是看还剩多少公里,算出来了,是100公里,往返3次,就是300公里,也就是300升油的消耗,路上消耗300升,再加上要运送到第一个加油站的500生,就是800升,所以答案就是800升,
问题3,也就是我们再考虑,如果不是600哪,600多呢,上边的两步超过多少就得再建第三个加油站了哪,就是超过500+500/3,也就是耗油最多是汽车的承受能力,即500升,所以分3次,除以3,就是500+500/3,超过这个就得再建设加油站了,前加油站就得需要500+500,也就是1000升,依次类推,不难推出一个整体
下面再建,你就把500+500/3看作一个整体来看,所以,程序就出来了,我也是经过仿佛的调试,所以有点乱,呵呵。
main()
{
float sum=500,s=500,t;
int k=1;
while(s<1000)
{
k++;
t=500/(2*k-1);
s=s+t;
}
算到这里以后,循环完毕,肯定这个路程超过1000了,所以现在要求出这个不到1000的时候的直,就是
s=s-t;
这个时候的s就是最大化的时候数值,然后再看零头
就是
t=1000-s;就是除去最大化的,剩下的
最后建设站数就是K的值,耗油量就是
(k-1)*500,就是把最大化那个乘上,还有那个零头肯定不是最大化的,所以就是t*(2*k-1),就是剩下的公里零头就是耗油量,但是要走(2×k-1)次,所以用乘法,加在一起就是总耗油量,呵呵,作完了这道题。