文档章节

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

一贱书生
 一贱书生
发布于 2017/04/12 09:57
字数 948
阅读 14
收藏 0

题目概述

师徒四人西天取经,途中必需跨过一座桥,四个人从桥的同一端出发,你得帮助他们到达另一端,天色很暗而他们只有一支手电筒,一次同时最多可以有两个人一起经过桥。而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒不能用丢的方式来传递,四个人的步行速度各不同,若两人同行则以较慢者的速度为准,大师兄需花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;
    }

}

运行的结果:
这里写图片描述

本文转载自:http://blog.csdn.net/two_water/article/details/52590899

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
2018/01/21
0
0
机器学习实习生面试总结(阿里 腾讯等)

今年来一直在找暑期实习,现在基本已经确定了,前后历经差不多2个月吧,发现了很多自己的缺点,同时也希望写出来供需要的人参考了解 先说下我自己的情况吧,决定去腾讯TEG的机器学习岗实习了...

Gavin__Zhou
2017/05/01
0
0
百度2010暑期实习笔试面试全面备战

百度2010暑期实习笔试面试全面备战 百度2010暑期实习网申将于2010年5月29日截止。 笔试阶段 5月30日前,对于通过了简历筛选的申请人百度将会通过系统发送笔试通知。注册时请务必填写正确有效...

长平狐
2013/01/06
156
0
在appstore里面搜索android会出现哪些鬼?

  曾经一个朋友建议我去麦当劳买完套餐,然后去KFC吃,看看会有什么效果。我当时的一次反应是会不会被KFC的工作人员打呢?这是赤裸裸的砸场子唉,就好像07年我最早研究SEO的时候,在谷歌搜...

程序员客栈
2016/05/23
32
0
九月十月百度,迅雷,华为,阿里巴巴最新校招笔试面试二十题(10.12)

九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试二十题 题记 本博客自2010年10月11日开通以来,已经帮助了一大批人找到工作,特别是连续三年在每一年的9、10月份陪伴了至少三届毕业生...

mickelfeng
2013/10/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins系列_插件安装及报错处理

进入Jenkins之后我们可以进行插件的安装,插件管理位于以下模块: 发现上面报了一堆错误,是因为插件的依赖没有安装好,那么这一节,就先把这些错误解决掉吧。解决完成后,也就基本会使用插件...

shzwork
今天
2
0
mysql mysql的所有查询语句和聚合函数(整理一下,忘记了可以随时看看)

查询所有字段 select * from 表名; 查询自定字段 select 字段名 from 表名; 查询指定数据 select * from 表名 where 条件; 带关键字IN的查询 select * from 表名 where 条件 [not] in(元素...

edison_kwok
昨天
9
0
解决多线程并行加载缓存问题(利用guava实现)

依赖 com.google.guava:guava:20.0 import com.google.common.cache.Cache;import com.google.common.cache.CacheBuilder;import java.util.concurrent.ExecutionException;import j......

暗中观察
昨天
3
0
利用VisualVM 内存查看

准备工作,建几个测试类。等下就是要查看这几个类里面的属性 package visualvm;public class MultiObject { private String str; private int i; MultiObject(String str...

冷基
昨天
2
0
组装一台工作游戏两用机

一、配置清单如下: 分类 项目 价格(元) 主板 华硕(ASUS)TUF Z370-PLUS GAMING II 电竞特工 Z370二代 支持9代CPU 1049 CPU 英特尔(Intel) i7 8700K 酷睿六核 盒装CPU处理器 2640 风扇 九...

mbzhong
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部