概述
夜晚，桥头有 4个人在一起准备过桥，这些人中只有一个人有手电筒，从桥头走到桥尾一次最多只能俩个人同时行进，每个人单独过桥的时间可能不一样，如果两个人在一起走，则这次的花费时间是走的最慢的那个人，假如现在四个人单独过桥的时间分别是 1,2,5,7，将它们放在一个数组中{1,2,5,7}算出最少的过桥时间。
问题解析：这个问题可以用递归解决。定义俩个指针，i和j，这俩个指针只能向前遍历。i从数组的第i位开始挑出一个人，j是在数组挑出第i位之后再从数组中挑出的人，这样就遍历了数组内各种情况的组合。在从四个人中随便抽出俩个过桥，此时从桥尾选出一个耗时最少的人重新回到桥头，这时候就成了3人过桥的问题，3人过桥又是找出各种组合过桥，最终就剩下俩个人在桥头，这时候俩个人就直接过桥，不用再进行组合过桥。可见俩个人过桥就是递归的出口。
以下是代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
public class FourMenPassBridge {
public static void main(String[] args) {
int[] source = {1,2,5,7};
FourMenPassBridge pass = new FourMenPassBridge();
pass.setSrc(source);
pass.passBridge(pass.getSrc(), pass.getDes(), 0);
int min = pass.result.get(0);
for(int i = 0;i
result = new ArrayList
();
public static int count=0;
public FourMenPassBridge(){
des = new Vector();
src = new Vector();
}
public void setSrc(int[] array){
for(int i = 0;i
=3){
for(int i = 0;i
以下是运行结果：先列举出各种情况，最后判断出最少的时间
入口：src-[1, 2, 5, 7]des-[]
i=0-1,j=1-2
先这俩个人过去：1和2
这时从桥尾回来的是：1
[5, 7, 1]des+[2]
入口：src-[5, 7, 1]des-[2]
i=0-5,j=1-7
先这俩个人过去：5和7
这时从桥尾回来的是：2
[1, 2]des+[5, 7]
入口：src-[1, 2]des-[5, 7]
最后俩个人过去的是:1和2
第1种情况=======================总共花的时间是:14
i=0-5,j=2-1
先这俩个人过去：5和1
这时从桥尾回来的是：1
[7, 1]des+[2, 5]
入口：src-[7, 1]des-[2, 5]
最后俩个人过去的是:7和1
第2种情况=======================总共花的时间是:16
i=1-7,j=2-1
先这俩个人过去：7和1
这时从桥尾回来的是：1
[5, 1]des+[2, 7]
入口：src-[5, 1]des-[2, 7]
最后俩个人过去的是:5和1
第3种情况=======================总共花的时间是:16
i=0-1,j=2-5
先这俩个人过去：1和5
这时从桥尾回来的是：1
[2, 7, 1]des+[5]
入口：src-[2, 7, 1]des-[5]
i=0-2,j=1-7
先这俩个人过去：2和7
这时从桥尾回来的是：2
[1, 2]des+[5, 7]
入口：src-[1, 2]des-[5, 7]
最后俩个人过去的是:1和2
第4种情况=======================总共花的时间是:17
i=0-2,j=2-1
先这俩个人过去：2和1
这时从桥尾回来的是：1
[7, 1]des+[5, 2]
入口：src-[7, 1]des-[5, 2]
最后俩个人过去的是:7和1
第5种情况=======================总共花的时间是:16
i=1-7,j=2-1
先这俩个人过去：7和1
这时从桥尾回来的是：1
[2, 1]des+[5, 7]
入口：src-[2, 1]des-[5, 7]
最后俩个人过去的是:2和1
第6种情况=======================总共花的时间是:16
i=0-1,j=3-7
先这俩个人过去：1和7
这时从桥尾回来的是：1
[2, 5, 1]des+[7]
入口：src-[2, 5, 1]des-[7]
i=0-2,j=1-5
先这俩个人过去：2和5
这时从桥尾回来的是：2
[1, 2]des+[7, 5]
入口：src-[1, 2]des-[7, 5]
最后俩个人过去的是:1和2
第7种情况=======================总共花的时间是:17
i=0-2,j=2-1
先这俩个人过去：2和1
这时从桥尾回来的是：1
[5, 1]des+[7, 2]
入口：src-[5, 1]des-[7, 2]
最后俩个人过去的是:5和1
第8种情况=======================总共花的时间是:16
i=1-5,j=2-1
先这俩个人过去：5和1
这时从桥尾回来的是：1
[2, 1]des+[7, 5]
入口：src-[2, 1]des-[7, 5]
最后俩个人过去的是:2和1
第9种情况=======================总共花的时间是:16
i=1-2,j=2-5
先这俩个人过去：2和5
这时从桥尾回来的是：2
[1, 7, 2]des+[5]
入口：src-[1, 7, 2]des-[5]
i=0-1,j=1-7
先这俩个人过去：1和7
这时从桥尾回来的是：1
[2, 1]des+[5, 7]
入口：src-[2, 1]des-[5, 7]
最后俩个人过去的是:2和1
第10种情况=======================总共花的时间是:17
i=0-1,j=2-2
先这俩个人过去：1和2
这时从桥尾回来的是：1
[7, 1]des+[5, 2]
入口：src-[7, 1]des-[5, 2]
最后俩个人过去的是:7和1
第11种情况=======================总共花的时间是:17
i=1-7,j=2-2
先这俩个人过去：7和2
这时从桥尾回来的是：2
[1, 2]des+[5, 7]
入口：src-[1, 2]des-[5, 7]
最后俩个人过去的是:1和2
第12种情况=======================总共花的时间是:18
i=1-2,j=3-7
先这俩个人过去：2和7
这时从桥尾回来的是：2
[1, 5, 2]des+[7]
入口：src-[1, 5, 2]des-[7]
i=0-1,j=1-5
先这俩个人过去：1和5
这时从桥尾回来的是：1
[2, 1]des+[7, 5]
入口：src-[2, 1]des-[7, 5]
最后俩个人过去的是:2和1
第13种情况=======================总共花的时间是:17
i=0-1,j=2-2
先这俩个人过去：1和2
这时从桥尾回来的是：1
[5, 1]des+[7, 2]
入口：src-[5, 1]des-[7, 2]
最后俩个人过去的是:5和1
第14种情况=======================总共花的时间是:17
i=1-5,j=2-2
先这俩个人过去：5和2
这时从桥尾回来的是：2
[1, 2]des+[7, 5]
入口：src-[1, 2]des-[7, 5]
最后俩个人过去的是:1和2
第15种情况=======================总共花的时间是:18
i=2-5,j=3-7
先这俩个人过去：5和7
这时从桥尾回来的是：5
[1, 2, 5]des+[7]
入口：src-[1, 2, 5]des-[7]
i=0-1,j=1-2
先这俩个人过去：1和2
这时从桥尾回来的是：1
[5, 1]des+[7, 2]
入口：src-[5, 1]des-[7, 2]
最后俩个人过去的是:5和1
第16种情况=======================总共花的时间是:20
i=0-1,j=2-5
先这俩个人过去：1和5
这时从桥尾回来的是：1
[2, 1]des+[7, 5]
入口：src-[2, 1]des-[7, 5]
最后俩个人过去的是:2和1
第17种情况=======================总共花的时间是:20
i=1-2,j=2-5
先这俩个人过去：2和5
这时从桥尾回来的是：2
[1, 2]des+[7, 5]
入口：src-[1, 2]des-[7, 5]
最后俩个人过去的是:1和2
第18种情况=======================总共花的时间是:21
-------14
最后
以上就是糟糕蛋挞为你收集整理的java版4人过桥问题的全部内容，希望文章能够帮你解决java版4人过桥问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复