2017完美世界研发部笔试题_取经

一、题目概述

师徒四人西天取经,途中必需跨过一座桥,四个人从桥的同一端出发,你得帮助他们到达另一端,天色很暗而他们只有一支手电筒,一次同时最多可以有两个人一起经过桥。而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒不能用丢的方式来传递,四个人的步行速度各不同,若两人同行则以较慢者的速度为准,大师兄需花1分钟过桥,二师兄需花2分钟过桥,三师兄需花5分钟过桥,师傅需花10分钟过桥。请问他们最短在多少分钟内过桥?()
A. 18
B. 17
C. 19
D. 16


二、思路

一开始直接想到,用最小的那个数来回跑,也就是大师兄来回跑,算出来是19,可是又想了下,如下:
1、大师兄和二师兄过桥,算二师兄的时间也就是2分钟
2、大师兄独自拿手电回来 1分钟
3、三师弟和师傅那手电过桥,算师傅的时间也就是10分钟
4、二师弟拿手电回来 2分钟
5、最后大师兄和二师弟过桥 2分钟
总共17分钟

这里写图片描述

虽然结果出来了,感觉有点不实在,这其中的规律是怎样的呢?有没有什么规律解决这类似的问题呢,比如只有三个人过桥呢?二师兄不过桥,结果又是什么呢?再比如,多一个人过桥呢?多了个白龙马过桥,白龙马过桥的时间时6分钟,结果又是什么呢?有没有什么规律呢,或者说有没有个公式来计算呢?用编程怎么解?

求教大神?先睡了,尝试下编程解决!


三、编程解决

2016年10月7日01:39:55
本来当时写博客的第二天就用编程解决了这个问题的,可是因为种种原因,还没有时间把代码贴上来!

import java.util.ArrayList;

public class Pilgrimage {

    final static int times[] = { 1, 2, 5, 10 };// 花费时间
    final static String names[] = { "大师兄", "二师兄", "三师兄", "师傅" };// 人物

    public static void main(String[] args) {
        Integer other_bridges[] = { 0, 0, 0, 0 };// 桥另一边
        Integer bridges[] = { 1, 1, 1, 1 };// 当前桥这边 ,1表示存在,0表示不在

        // 开始递归
        loop(bridges, other_bridges, 0, new StringBuffer());
    }

    private static void loop(Integer[] bridges, Integer[] other_bridges,
            int time, StringBuffer msg) {
        ArrayList<Integer> positions = new ArrayList<Integer>();// 记录还在起始端人的下标
        for (int i = 0; i < bridges.length; i++) {
            if (bridges[i] == 1) {
                positions.add(i);// 记录下标
            }
        }
        int len = positions.size();

        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) { // 循环取结合
                // 记录状态
                Integer[] zt_bridges = bridges.clone();
                Integer[] zt_other_bridges = other_bridges.clone();
                int zt_time = time;
                StringBuffer zt_msg = new StringBuffer(msg);

                // 过桥---------
                time += times[positions.get(j)];// 花费时间直接取最大的
                move(bridges, other_bridges, 1, positions.get(i));
                move(bridges, other_bridges, 1, positions.get(j));
                msg.append(" 过桥:" + names[positions.get(i)] + "&"
                        + names[positions.get(j)]);
                // System.out.print(" 过桥:" + names[positions.get(i)] + "_"
                // + names[positions.get(j)]);

                // 回来接人------
                if (isend(other_bridges)) {
                    msg.append(" 总共花费:" + time);
                    System.out.println(msg.toString());
                    // System.out.println(" 总共花费:" + time);
                    return;
                }
                int k = 0;
                for (int ii = 0; ii < other_bridges.length; ii++) {// 选择最快的回来
                    if (other_bridges[ii] == 1) {
                        k = ii;
                        break;
                    }
                }
                time += times[k];
                move(bridges, other_bridges, 0, k);
                msg.append("  回来:" + names[k]+"  ***  ");
                // System.out.print(" 回来:" + names[k]);

                // 继续循环遍历
                loop(bridges.clone(), other_bridges.clone(), time,
                        new StringBuffer(msg));

                // 还原状态
                bridges = zt_bridges;
                other_bridges = zt_other_bridges;
                time = zt_time;
                msg = zt_msg;
            }
        }
    }

    /**
     * 移动的那个人
     * 
     * @param bridges
     * @param other_bridges
     * @param direction
     *            方向
     * @param position
     */
    private static void move(Integer[] bridges, Integer[] other_bridges,
            int direction, int position) {
        if (direction == 1) {// 往另一端走
            bridges[position] = 0;
            other_bridges[position] = 1;
        } else {// 回来接人走
            bridges[position] = 1;
            other_bridges[position] = 0;
        }
    }

    // 判断是否已经结束了
    // 当other_bridges {1,1,1,1}表示结束
    private static boolean isend(Integer[] other_bridges) {
        for (int i : other_bridges) {
            if (i == 0)
                return false;
        }
        return true;
    }

}

运行的结果:


这里写图片描述
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,189评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,577评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,857评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,703评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,705评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,620评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,995评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,656评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,898评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,395评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,982评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2 342

推荐阅读更多精彩内容

  • 楔子 擎苍,你以为过了七万年就可以快活了么? 我是青丘的白浅,也是当年的司音。今日便是拼了这条命,我也要将你再锁上...
    女少月半阅读 9,840评论 6 62
  • 楔子 擎苍,你以为过了七万年就可以快活了么? 我是青丘的白浅,也是当年的司音。今日便是拼了这条命,我也要将你再锁上...
    女少月半阅读 7,227评论 10 27
  • 唐七公子的《三生三世枕上书》中有这么一段:白浅曾经教导凤九,做神仙最重要的是不怕丢脸,因不怕丢脸是一种勇气,赐予一...
    燕臻阅读 654评论 0 1
  • 最近看到乔任梁离世消息以及微博上的一些评论,感触颇深。有人说,多么乐观和开朗的男孩,实在不相信这是真的。突然间很...
    雅姒矜阅读 223评论 0 1
  • 感恩 今天终于突破了困境 今天灵性炼金依然陪伴我 今天很充实 今天高我依然很爱自己 今天我顿悟了很多 今天开心地和...
    fc8c4755608d阅读 318评论 0 0