过桥问题 问题描述:晚上有四个人要过桥,只有一个手电筒,每次过桥都需要手电筒,每次最多可同时过两个人,其中甲过桥要1分钟,乙要2分钟,丙要5分钟,丁要10分钟。求最短的过桥时间。 对于这个问题:我们可以引申到一个人,二个人,三个人至N个人过桥的问题上;
当一个人过桥时 那么直接过桥就行了 这很简单 当两个人过桥时,也是直接过桥 时间 = 走路最慢的那个人的时间; 当三个人过桥的时候 ,我们可以穷举三个人过桥的可能性,发现 总共花费的最短时间 = 三个人的过桥时间和 当四个人过桥的时候 过桥的时间最短有两种模式: - 模式一 :让速度最快的人 依次带速度最慢的人和速度次慢的人 过桥 - 模式二 :让速度最快的人和速度次快的人带速度最慢的人和速度次慢的人过桥
当五个人过桥的时候 过桥的时间最短有两种模式:
- 模式一 :让速度最快的人 依次带速度最慢的人和速度次慢的人 过桥,然后再看剩下三个人怎么办 - 模式二 :让速度最快的人和速度次快的人带速度最慢的人和速度次慢的人过桥,然后再看剩下三个人怎么办
当五个人过桥的时候 过桥的时间最短有两种模式:
- 模式一 :让速度最快的人 依次带速度最慢的人和速度次慢的人 过桥,然后再看剩下四个人递归方法 - 模式二 :让速度最快的人和速度次快的人带速度最慢的人和速度次慢的人过桥,然后再看剩下四个人递归方法
模式一和模式二具体看这个链接的第十条:http://www.360doc.com/content/08/0706/02/37063_1402145.shtml 假设 :A : 速度最快 B :速度次快 C:速度次慢 D:速度最慢 模式二: times = time1+2+3+4; a,b —> a,b time1 a <— a time2 z,y —> z,y time3 b <— b time4
下面是用JAVA写的完整代码
import java.util.Arrays;
import java.util.Scanner;
public class guohe {
public static void main(String[] args) {
System.out.println("请输入过河人数:\n");
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
System.out.println("请分别输入这"+n+"个人过河时间");
int[] arr=new int[n];
for(int i=0;i<arr.length;i++){
arr[i]=scanner.nextInt();
}
Arrays.sort(arr);//数组从小到大排序
System.out.println(shorts(arr,n));
}
static int shorts(int arr[],int n) {
int end = n;//n表示人数
int times = 0;//最短时间和
if (1 == n) {
return arr[n - 1];
}
if (2==n){
return arr[n-1];
}
if (3==n){
return arr[0]+arr[1]+arr[2];
}
if (n>=4){
//a是最快,b次最快,z最慢,y次最慢
int a=arr[0],
b=arr[1],
z=arr[n-1],
y=arr[n-2];
//a先把b运过去,然后最快的a把z,y分别别来回运过去表示2*a+z+y
//a先把b运过去,然后a过来,z和y一块过去,b过来再把a运过去
if (2*a+z+y>2*b+a+z){
times=2*b+a+z;
end=end-2;//上面的times只是把前四个里面的最慢和次最慢运过去了,所以在下面的代码中再调用
}else{
times=2*a+z+y;
end=end-2;
}
times=times+shorts(arr,end);//此处递归调用方法
}
return times;
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。