思维拓展：用java实现巧妙过桥问题

你的名字 2023-02-22 03:50 125阅读 0赞

问题：小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要 2 分钟，小明 的弟弟要 5 分钟，小明的爸爸要 6 分钟，小明的妈妈要 9 分钟，小明的爷爷要 13 分钟。每次 此桥最多可以过两人，而过桥的速度根据过桥最慢者而定，而且灯在点燃后 40 分钟就会熄灭。 问小明一家如何过桥时间最短？

代码如下：

public class demo { 
        static int index;                            //过桥临时方案的数组下标
        static int size = 64;
        static int N = 5;
        static int mintime = 40;                    //最小过桥时间总和，初始值30
        static int[] transit = new int[size];        //进行下标中转的数组
        static int program[] = new int[size];         //最短时间内过桥的方案;
        // static int time[] = {1, 3, 6, 8, 12}; //每个人过桥所需要的时间;
        static int time[] = { 2, 5, 6, 9, 13};         //每个人过桥所需要的时间;
        /* * 将人员编号：小明 location[0]，弟弟location[1]， * 爸爸location[2]，妈妈location[3]，爷爷location[4] 每个人的当前位置：0--在桥左边， 1--在桥右边 */
        static int location[] = new int[N];
    
        /* * 参数说明：notPass:未过桥人数;usedtime:当前已用时间;Direction:过桥方向,1--向右,0--向左 */
        public static void Find(int notPass, int usedtime, int Direction) { 
            if (notPass == 0) {                  //所有人已经过桥，更新最少时间及方案
                mintime = usedtime;
                for (int i = 0; i < size && transit[i] >= 0; i++) { 
                    program[i] = transit[i];
                }
            } else if (Direction == 1) {          //过桥方向向右，从桥左侧选出两人过桥
                for (int i = 0; i < N; i++) { 
                    if (location[i] == 0 && (usedtime + time[i]) < mintime) { 
                        transit[index++] = i;
                        location[i] = 1;
                        for (int j = 0; j < N; j++) { 
                            int TmpMax = (time[i] > time[j] ? time[i] : time[j]);
                            if (location[j] == 0 && (usedtime + TmpMax) < mintime) { 
                                transit[index++] = j;
                                location[j] = 1;
                                Find((notPass - 2), (usedtime + TmpMax), 0);
                                location[j] = 0;
                                transit[--index] = -1;
                            }
                        }
                        location[i] = 0;
                        transit[--index] = -1;
                    }
                }
            } else {  //过桥方向向左，从桥右侧选出一个人回来送灯
                for (int j = 0; j < N; j++) { 
                    if (location[j] == 1 && usedtime + time[j] < mintime) { 
                        transit[index++] = j;
                        location[j] = 0;
                        Find(notPass + 1, usedtime + time[j], 1);
                        location[j] = 1;
                        transit[--index] = -1;
                    }
                }
            }
        }
    
        public static void main(String[] args) { 
            String s1 = "", s2 = "", s3 = "";
            for (int i = 0; i < size; i++) { 
                program[i] = -1;
                transit[i] = -1;                //初始方案内容为负值，避免和人员标号冲突
            }
            Find(N, 0, 1); // 查找最佳方案
            System.out.println("最短过桥时间为：" + mintime);        //输出最短过桥时间
            System.out.println("最佳过桥组合为：");                // 输出最佳过桥组合
            for (int i = 0; i < size && program[i] >= 0; i += 3) { 
                switch (program[i]) { 
                    case 0:
                        s1 = "小明";
                        break;
                    case 1:
                        s1 = "弟弟";
                        break;
                    case 2:
                        s1 = "爸爸";
                        break;
                    case 3:
                        s1 = "妈妈";
                        break;
                    case 4:
                        s1 = "爷爷";
                        break;
                }
                switch (program[i + 1]) { 
                    case 0:
                        s2 = "小明";
                        break;
                    case 1:
                        s2 = "弟弟";
                        break;
                    case 2:
                        s2 = "爸爸";
                        break;
                    case 3:
                        s2 = "妈妈";
                        break;
                    case 4:
                        s2 = "爷爷";
                        break;
                }
                switch (program[i + 2]) { 
                    case 0:
                        s3 = "小明";
                        break;
                    case 1:
                        s3 = "弟弟";
                        break;
                    case 2:
                        s3 = "爸爸";
                        break;
                    case 3:
                        s3 = "妈妈";
                        break;
                    case 4:
                        s3 = "爷爷";
                        break;
                    case -1:
                        s3 = "没人";
                        break;
                }
    
                System.out.println(s1 + "和" + s2 + "一道过桥，" + s3 + "再回来");
            }
        }
    }

执行结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200701133046244.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh,size_16,color_FFFFFF,t_70