IT公司经典推理面试题 - 拿钻石

csdn高校俱乐部 面试题 逻辑 

CSDN-木水辰

毕业生北京邮电大学

题目:

一楼到十楼的每层电梯门口都放着一颗钻石,钻石大小不一。你乘坐电梯从一楼到十楼,每层楼电梯门都会打开一次,只能拿一次钻石,问怎样才能拿到最
大的一颗?

要求和奖励(奖励活动已结束):

给出你的分析思路,条理清楚叙述明确且符合逻辑者,将获得高校俱乐部送出的 30 积分和 30 C币。

创建
2015-03-16
浏览
216668次
最新回复
2016-05-04
回复
59
4

fushichou

毕业生哈尔滨理工大

先拿下第一楼的钻石,然后在每一楼把手中的钻石与那一楼的钻石相比较,如果那一楼的钻石比手中的钻石大的话那就把手中的钻石换成那一层的钻石。
(PS:因为“只能拿一次”是存在异议的,所以是总共只能拿一次,还是每层只能拿一次?无法知道。但如果这个和“在稻田一直走,不能回头,请你捡出最大的一个稻穗”这样的题目一样的话,那么上面的就是正确答案!)

2015年03月19日 09:21:08

龚冬冬

毕业生东北林业大学

这道题根本不可能百分之百的拿到最大的那个钻石,而且能拿到的钻石是最大的那颗的概率还是很低的,接近1/10也就是和你随机抽取一个出来是最大钻石的概率相似,但是我们可以通过分析取最优解,也就是拿尽量大的钻石,比如说我前5层不拿钻石,仅仅观察,通过观察判断后面钻石的大小,如果遇到比前5层最大的钻石还大的钻石就取出,否则取最后一枚钻石,这样在钻石随机分布的情况下就会有很大概率拿到的钻石接近最大的那颗,甚至就是拿到的最大钻石。

2015年03月17日 13:12:53

Lyz1052

毕业生上海大学

题目意思是取到最大的一颗,而不是尽量取到最大的一颗。。。。

这么看,我觉得,带个切割机上电梯,直接拿第一层的那一个,然后把每层的钻石都切成比第一层的小,第一层的当然就是最大的一颗

2015年03月18日 18:45:06

纵横车

毕业生湖北大学知行

显然不可能一定拿能到最大的,除非用一些旁门左道的方法,比如把前9层看到的钻石全部销毁,然后拿最后一层的等。

逻辑上可以找一个较大的,

比如每到一层就记录这一层的钻石的大小,

然后计算已知的钻石的大小的平均值认为是整体的平均值,

计算相邻大小两颗钻石的大小差距的平均值,再由数据个数与总体个数推算出整体的大小相邻的钻石的差值,(每层楼都记录并计算一次所以这些预测值会越来越接近实际值)

由此可推测最大的钻石的大小(平均值+4.5*平均差值)。为了降低风险,看到的钻石>=预测值-1*平均差值时就认为它是最大的。

这里是认为钻石的大小成等差数列分布,自然情况下钻石的大小应该是成类似正态分布的情况,但是我想既然这是人为的测试应该会选一些差距比较明显分布比较均匀的钻石,我认为这样就更接近等差数列的分布情况,当然也可以由前面取到的数据来分析更接近什么分布模型,但是这题数据量比较小,这样也不太准确。

2015年03月18日 18:51:34

AudienL

毕业生广州中医药大

原理:取前n层的钻石的平均值avg,从第n+1层开始,如果遇到大于avg的钻石,则取之。(参考前面的回复的)

测试结果:

当n为 1 的时候,找到最大值的比例为: 126873/1000000
当n为 2 的时候,找到最大值的比例为: 126945/1000000
当n为 3 的时候,找到最大值的比例为: 126687/1000000
当n为 4 的时候,找到最大值的比例为: 127257/1000000
当n为 5 的时候,找到最大值的比例为: 256684/1000000
当n为 6 的时候,找到最大值的比例为: 126895/1000000
当n为 7 的时候,找到最大值的比例为: 126946/1000000
当n为 8 的时候,找到最大值的比例为: 126702/1000000
当n为 9 的时候,找到最大值的比例为: 126923/1000000

所以,取得前面5层作为平均值的时候,找到最大那颗钻石的概率最大,大约是0.25

实现代码:

package test;

import java.util.Arrays;
import java.util.Random;

/**
 * 原理:取前n层的钻石的平均值avg,从第n+1层开始,如果遇到大于avg的钻石,则取之。
 */
public class Demo {
    private static int before;// 取前多少层的平均值
    private static int[] diamonds = new int[10];// 十颗钻石

    public static void main(String[] args) {
        // 分别计算当n为1~9层的时候对应取得最大值的概率
        for (int x = 1; x < 10; x++) {
            before = x;

            int count = 1000000;// 测试次数
            int countMax = 0;// 找到最大值的次数

            // 测试count次,计算取得的钻石为最大值的出现比例
            for (int i = 0; i < count; i++) {

                // 初始化十颗钻石
                resetDiamonds();

                // 开始,获取钻石
                int diamond = getDiamond();
                if (isMax(diamond, diamonds)) {
                    countMax++;
                }
            }

            // 计算出现最大值的比例
            System.out.println("当n为 " + before + " 的时候,找到最大值的比例为: " + countMax
                    + "/" + count);
        }
    }

    /**
     * 计算是否获得了最大值
     */
    private static boolean isMax(int diamond, int[] diamonds) {
        Arrays.sort(diamonds);
        if (diamond == diamonds[diamonds.length - 1]) {
            return true;
        }
        return false;
    }

    /**
     * 还是上楼,获取钻石
     */
    private static int getDiamond() {
        int diamond = 0;

        // 计算前n层钻石的平均值avg
        int avg = getAvg();

        // 遍历后面的楼层的钻石
        for (int i = before; i < diamonds.length; i++) {
            if (diamonds[i] > avg) {
                diamond = diamonds[i];
                break;
            }
        }

        // 如果没有遇到大于avg的,则取最后一颗
        if (diamond == 0) {
            diamond = diamonds[diamonds.length - 1];
        }
        return diamond;
    }

    /**
     * 初始化/重置钻石,值为80~100
     */
    private static void resetDiamonds() {
        Random r = new Random();
        for (int i = 0; i < diamonds.length; i++) {
            diamonds[i] = r.nextInt(20) + 80;
        }
    }

    /**
     * 取得前n层楼的平均值
     */
    private static int getAvg() {
        int sum = 0;
        for (int i = 0; i < before; i++) {
            sum += diamonds[i];
        }
        return sum / 5;
    }

}

2015年03月19日 17:43:42

weixiaokang

毕业生南京邮电大学

可以,将每层楼的钻石都做一个印模。出去后,用类似玻璃的材料,再做一个钻石呗。

2015年03月22日 21:19:05

yxyyg

毕业生电子科技大学

同样,首先去前5个样本。并分别判断他们之间的联系。如:1和2之间的关系,0、1.和2之间的关系,等等。直到找出联系,或者到5了还是没有发现联系,就直接取第6个。

如:通过样本取得他们的联系后,若是从下往上,是从大到小排序的话。在发现这个规律时,直接取出当前砖石。

2015年03月24日 22:30:55

Anno_ying

毕业生陕西电子信息

先拿一楼钻石和二楼比较,取最大,有最大和三楼比较,取最大。。。依次,到十楼就是最大的一颗!

2015年07月14日 14:04:11

CSDN-木水辰

毕业生北京邮电大学

恭喜你,获得高校俱乐部送出的 30 积分和 30 C币。

2015年03月17日 16:03:06

最爱麦丽素

毕业生盐城工学院

前3层统计数据,判断大小分布,估计钻石大小范围,中间3三层评估自己的统计,计算均值和方差,若观察到x>=μ+σ的钻石,直接取,取得为大钻石的概率为=15.85%大于10%,是一种更保守的做法。

2015年03月17日 16:40:34

最爱麦丽素

毕业生盐城工学院

前3层统计数据,判断大小分布,估计钻石大小范围,中间3三层评估自己的统计,计算均值和方差,若观察到x>=μ+σ的钻石,直接取,取得为大钻石的概率为=15.85%大于10%,是一种更保守的做法。

2015年03月17日 16:40:38

single_cha

学生哈尔滨工业大

第一种方法:直接拿走第一层的(万一最大的那颗就是第一层的呢)

第二种方法:写十张纸,来抓阄决定在哪层拿钻石(碰运气,风险大)

第三种方法:(若最大的那颗比其他明显都大)前两层都不拿,看第三层,若第三层的钻石明显比前两层的大,可以考虑将这颗拿走,如果大小差异不大则继续观察,直到出现一颗明显比之前楼层钻石大的钻石。(风险较第一种低)

第四种方法:(如果所有钻石大小差异不大):一层一层来,说不定到哪层突然想拿了。(通过观察每层钻石大小凭直觉来拿)

总的来说,需要靠运气来拿。。

 

2015年03月17日 21:51:55

天命王子

毕业生广东工业大学

一般面试题都喜欢没有标准答案的shades_smile,这道题也是一样。

我的答案是:先看前面n层楼,之后再逐层看有哪一层的钻石是大过前面n层中最大的那一颗,要是有一颗大过最大那颗,马上拿走,否则拿最后一颗。

当然要是现实的话,我会选择第七层,因为我的幸运数字是7,还有就是现实中如果有的话,这是一笔意外之财,就算没有拿到最大那颗钻石,自己也是赚了。regular_smile

2015年03月17日 22:28:21

小小的CODEING

毕业生安徽理工大学

先每层看看哪个最大啊!然后从十楼下来拿那个最大的不就行吗?

2015年03月18日 00:02:44

雨过天空

毕业生青岛理工大学

为什么我感觉不论怎么拿其实概率都是十分之一呢

2015年03月18日 14:12:54

sleepandeat

毕业生常熟理工学院

要拿到最大的,我想不出最优解,只能金可能拿大的,在全部样本数量为10的情况下,抽取前M层为抽样样本,因为钻石的随机性,我们可以大致的认为这M个钻石的平均大小代表着这10颗钻石的平均水平,然后从M+1层开始,取大于平均值的那颗钻石。

但是会出现前M颗是最大的情况,再来优化这个模型,不妨把M层后每次看到的钻石也算进抽样样本里,也就是说,直到拿走的那颗钻石之前的钻石全部是抽样样本。

但如果钻石按照从大到小依次排列在一到十楼,那么按照上述算法就没钻石可拿,所以规定,最后一层时候,若没拿钻石,则就取最后一层的钻石。

2015年03月18日 16:52:09

summer92727

学生吉林大学

怎摸都拿不到最大的一颗,统计前五层钻石的大小,后五层中出现比前五层大的就拿。

2015年03月19日 07:35:31

CSDN-木水辰

毕业生北京邮电大学

恭喜你,获得高校俱乐部送出的 30 积分和 30 C币。

2015年03月19日 09:56:27

CSDN-木水辰

毕业生北京邮电大学

相信自己的幸运数字一定会为你带来幸运的~

恭喜你,获得高校俱乐部送出的 30 积分和 30 C币。

 

2015年03月19日 10:15:33

CSDN-木水辰

毕业生北京邮电大学

题目说这个楼除了电梯之外还有楼梯了么。。。

2015年03月19日 10:17:22
Top_arrow