<>一、沙漠问题

<>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、是开锁的

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信