©2020-2024 ioDraw All rights reserved
<>一、沙漠问题
<>1、问题描述
一辆吉普车来到1000km宽的沙漠边沿。吉普车的耗油量为1L／km，总装油量为500L。显然，吉普车必须用自身油箱中的油在沙漠中设几个临时
加油点，否则是通不过沙漠的。假设在沙漠边沿有充足的汽油可供使用，那么吉普车应在哪些地方、建多大的临的加油点，才能以最少的油耗穿过这块沙漠?
<>2、问题分析
从这个题目来看，这是一个极限问题，求得是最少耗油的量，所以只有唯一答案。
1、为了穿越这个沙漠，同时耗油量最少，那么吉普车就应该每次出发的时候都要满油量出发。
2、为了保证每一次都是满油量的从每个临时加油站出发，那么每一个临时加油站的油量储备都应该是500L的倍数。
3、为了保证耗油量最少，每一次建立一个临时加油站的时候，运输的次数也是越少越好，减少重复的路段。
4、如果这道题通过递推法正推的话很难确定第一个临时加油站的地点。
5、所以这里我们用倒推法来做。
6、假设我们已经到达了B点，这个时候B点的储油量应该0,这是可以倒推C1点的储油量应该为500L，这时候可以刚好到达终点B。好了现在我们知道C1点的储油量了，也就知道了C1到B点的距离为500米。
7、这时候我们应该想，如果向C1点运输500L的油量，C2点应该存储多少油呢？根据上面的步骤2（临时加油站的油量储备都应该是500L的倍数）和步骤3(运输的次数也是越少越好，这里肯定是两次或者两次以上才能向C1点运输500L油，这里取2次)，那么我们就知道了C2点的储油量应该是500L*2,也就是1000L油。这时，C2到C1的距离为500/3。
8、如果想C2点运输1000L的油，重复步骤7可知，C3点存储油量为500×3L,C3到C2的距离为500/5。
9、所以到达临时加油站Cn的时候，储油量应该是500×n，Cn到Cn-1的距离为500/2n-1。
所以这里通过下面这个式子算出n：
500+500/3+500/5+500/（2n-1) = 1000;
然后就可以得出最少耗油量。
<>3.实现
public class Desert { public double totaldistance;//总长度 public double speed;
//单位距离的油耗速度 public double oilper;//单次的最大负载 public void result(double total,
double speed,double oilper) { this.oilper=oilper; this.speed=speed; this.
totaldistance=total; //假设都是满载行驶 double distance = oilper/speed;//每段路的距离 if(
totaldistance<= distance) { System.out.println("总距离小于第一段距离，可以一次通过。"); }
//需要设置补给站点，每个站点的存储量为单次的最大负载的整数倍 double dis=distance; int i=0;//站点个数 while(dis <
totaldistance) { //每一个站点的距离之和，即计算设置多少个站点才能通过totaldistance总长 i++; dis+=1.0/(2*i+1
)*distance; } int num=i; double totalOil = 0; while(i>0) { dis-=distance/(2*i+1)
; i--; if(totalOil==0) { totalOil=oilper*i+(totaldistance-dis)*(2*i+1)/speed; }
System.out.println("第"+(num-i)+"个站点为距离起点"+(totaldistance-dis)+"处，存储量为"+oilper*i+
"L"); } System.out.println("总耗油量为"+totalOil+"L"); } public static void main(
String[] args) { double total=1000.0; double speed=1.0; double oilper=500.0;
Desert desert=new Desert(); desert.result(total,speed,oilper); } }
<>4.结果
第1个站点为距离起点22.433122433122435处，存储量为3000.0L 第2个站点为距离起点60.89466089466089处，存储量为
2500.0L 第3个站点为距离起点106.34920634920638处，存储量为2000.0L 第4个站点为距离起点161.90476190476193
处，存储量为1500.0L 第5个站点为距离起点233.33333333333337处，存储量为1000.0L 第6个站点为距离起点
333.33333333333337处，存储量为500.0L 第7个站点为距离起点500.0处，存储量为0.0L 总耗油量为3291.630591630592L
<>二、狱吏问题
<>1、问题描述
某王国对囚犯进行大赦,让一狱吏n次通过一排锁着的n间牢房,每通过一次按所定规则转动门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后,门锁开着的,牢房中的犯人放出,否则犯人不得获释.转动门锁的规则是这样的,第一次通过牢房,要转动每一把门锁,即把全部锁打开；第二次通过牢房时,从第二间开始转动,每隔一间转动一次；第k次通过牢房,从第k间开始转动,每隔k-1
间转动一次；问通过n次后,哪些牢房的锁仍然是打开的?
<>2、问题分析
牢房可以视作一个一元数组，1代表锁着，0代表开锁。
规律：当锁的标号为一个数的平方时，那么最后它会开着。
<>3.实现
public class Warder { public void WarderResult(int n) { //1表示锁着，0表示开锁 System.
out.println("暴力法"); int room[] = new int[n]; int i; for (i=0;i<n;i++) {
//初始状态都是锁着 room[i]=1; } System.out.println("牢房数为"+n+"时"); int k,j; for(i=1;i<=n;
i++) { //i表示通过牢房次数 System.out.print("第"+i+"次通过牢房"); for(k=i;k<=n;k+=i) { if(room
[k-1]==1) { room[k-1]=0; }else { room[k-1]=1; } } for(j=0;j<n;j++) { if(room[j]
==0) { System.out.print(j+1+"、"); } } System.out.println("是开锁的"); } } public
void LawWarder(int n) { System.out.println("规律法"); System.out.println("牢房数为"+n+
"时"); for(int i=1;i<+n;i++) { if(i*i<=n) { System.out.print(i*i+"、"); } } System
.out.println("是开锁的"); } public static void main(String[] args) { int n=10;//牢房间数
Warder warder= new Warder(); warder.WarderResult(n); warder.LawWarder(n); } }
<>4.结果
暴力法 牢房数为10时 第1次通过牢房1、2、3、4、5、6、7、8、9、10、是开锁的 第2次通过牢房1、3、5、7、9、是开锁的 第3次通过牢房1、5、6
、7、是开锁的 第4次通过牢房1、4、5、6、7、8、是开锁的 第5次通过牢房1、4、6、7、8、10、是开锁的 第6次通过牢房1、4、7、8、10、是开锁的
第7次通过牢房1、4、8、10、是开锁的 第8次通过牢房1、4、10、是开锁的 第9次通过牢房1、4、9、10、是开锁的 第10次通过牢房1、4、9、是开锁的
规律法 牢房数为10时 1、4、9、是开锁的