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

csdn高校俱乐部 面试题 逻辑 

CSDN-木水辰

毕业生北京邮电大学

题目:

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

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

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

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

fushichou

毕业生哈尔滨理工大

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

2015年03月19日 09:21:08

yongheng5871

学生大连理工大学

我认为其实这道题就考得是如何从不同的侧面去分析问题,只要找到一个不同于其他人的方向去分析都是正解!

2015年03月19日 10:24:06

海南小石

毕业生海南大学

每层楼电梯门都会打开一次,只能拿一次钻石。这个题目为什么感觉有语病歧义呢?限制是只拿一次,没有限制放下钻石,1楼拿走,往上走看到大的就拿一次,把小的放回,这样类似冒泡排序一层一层来,肯定100%拿到钻石嘛。。。。

2015年03月19日 10:29:05

gting96

毕业生中国科学技术

补充一下1楼的想法:即前n楼不拿钻石,若在后面遇到比前面n楼中最大的钻石还要大的,那么就选择该钻石。

记10个钻石按大小编号为 1,2,3,4,5,6,7,8,9,10

假设其排列是完全随机的。那么总共有全排列P(10,10)=3628800种。

在使用上面的策略下,满足以下两个条件的排列是能够成功的拿到最大的钻石的(也就是编号10)。

  1. 最大钻石不在第1楼到第n楼(否则根据上述策略,将会错过最大的钻石)
  2. 从第n+1楼到最大钻石的楼层都比前面n楼中最大的钻石来得小。

根据以上两点,就可以很容易求出满足该条件的排列。因为数字较小,直接遍历所有全排列求解。

关键的判断函数如下:

bool judge(int list[],int n)
{
    int i, maxnum;
    maxnum = list[0];
    for (i = 0; i < n; i++) //前n个的最大值
    {
        if (maxnum < list[i])maxnum = list[i];
    }
    if (maxnum == 10)return false; //如果最大的那个钻石在前n个中,那么这个排列是失败的
    for (i = n; i < 10; i++)
    {
        if (list[i] == 10) return true; //如果找到了最大的钻石 那么这个排列是成功的
        if (list[i]>maxnum) return false; //如果找到的不是最大的钻石,那么这个排列是失败的
    }
    return false;
}

 

经过测试,得到如下的结果:

  • n=1时,总共有1026576个排列满足条件,概率约为0.2829
  • n=2时,总共有1327392个排列满足条件,概率约为0.3658
  • n=3时,总共有1446768个排列满足条件,概率约为0.3987
  • n=4时,总共有1445184个排列满足条件,概率约为0.3983
  • n=5时,总共有1352880个排列满足条件,概率约为0.3728
  • n=6时,总共有1188000个排列满足条件,概率约为0.3274
  • n=7时,总共有962640个排列满足条件,概率约为0.2653
  • n=8时,总共有685440个排列满足条件,概率约为0.1889
  • n=9时,总共有362880个排列满足条件,概率约为0.1000

因此可以有一个合理的策略是前三层不取钻石,然后在接下去的楼层遇到比前三层中最大的钻石还大的,就选取它。

2015年03月22日 15:41:41

龚冬冬

毕业生东北林业大学

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

2015年03月17日 13:12:53

最爱麦丽素

毕业生盐城工学院

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

2015年03月17日 16:40:34

天命王子

毕业生广东工业大学

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

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

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

2015年03月17日 22:28:21

小小的CODEING

毕业生安徽理工大学

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

2015年03月18日 00:02:44

sleepandeat

毕业生常熟理工学院

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

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

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

2015年03月18日 16:52:09

Lyz1052

毕业生上海大学

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

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

2015年03月18日 18:45:06

纵横车

毕业生湖北大学知行

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

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

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

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

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

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

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

2015年03月18日 18:51:34

summer92727

学生吉林大学

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

2015年03月19日 07:35:31

yongheng5871

学生大连理工大学

 

乘坐电梯到最顶层知道哪一层的钻石最大后,出电梯走楼梯到指定楼层去拿就好了。 他又没有说不可以出去

 

2015年03月19日 10:21:43

CSDN-木水辰

毕业生北京邮电大学

这怎么听起来有掩耳盗铃的味道在里面呢。。。

2015年03月19日 10:22:40

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

大块木

毕业生邵阳学院

 10层楼,10颗钻,按从钻石的大小编号为(0-9),在10层楼放置10颗钻其总共的放置方法为10的全排列,即10的阶乘:3628800种。

常规情况下,从10层楼中任取一个钻编号为9(最大)的概率为0.1,做3628800次实验,每次都选中编号为9的钻的概率为1/36288000。

此类事件存在随机性,采用随机抽样的实验方法,先设离散型随机变量X的所有可能xk(k=1,2,3....),实验得出其对应的概率为Pk(k=1,2,3....),从是选取Pk最大的值的排列,其排列9所在的层数,这样拿到最大的钻的可能性最高。

2015年03月20日 19:43:07

CSDN-木水辰

毕业生北京邮电大学

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

2015年03月17日 16:03:06

最爱麦丽素

毕业生盐城工学院

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

2015年03月17日 16:40:38

single_cha

学生哈尔滨工业大

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

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

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

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

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

 

2015年03月17日 21:51:55

雨过天空

毕业生青岛理工大学

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

2015年03月18日 14:12:54
Top_arrow