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

csdn高校俱乐部 面试题 逻辑 

CSDN-木水辰

毕业生北京邮电大学

题目:

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

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

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

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

CSDN-木水辰

毕业生北京邮电大学

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

2015年03月19日 10:24:39

CSDN-木水辰

毕业生北京邮电大学

前面有人这样说过了。。。再想想

2015年03月19日 10:25:08

剑侠365

毕业生南京邮电大学

下楼的时候拿啊,而且我女朋友说她全都要zz_5

2015年03月19日 10:28:32

CSDN-木水辰

毕业生北京邮电大学

你的这个“偷梁换柱”的思路倒是很新颖。题目要求只能拿一次,并没有约束不可以置换。

所以嘛,30积分30C币还是送给你了~在实际工作中,有些时候采用“置换”手法未尝不是一个好的办法,但是不是所有的问题都可以采用这样的捷径的,具体问题具体分析吧~angel_smile

2015年03月19日 10:28:36

海南小石

毕业生海南大学

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

2015年03月19日 10:29:05

CSDN-木水辰

毕业生北京邮电大学

题目没说不可以出去,但是题目没说此楼有楼梯。。。

2015年03月19日 10:29:27

CSDN-木水辰

毕业生北京邮电大学

对的。原本就是条条大路通罗马,一个问题通常有很多解决的办法,也许只有一个是最优的,但是我们不鼓励所有人都采用同样的思路,我们鼓励差异化的存在。

2015年03月19日 10:30:13

海南小石

毕业生海南大学

你乘坐电梯从一楼到十楼,每层楼电梯门都会打开一次,只能拿一次钻石。

让我们来看看这个语病吧:

[1]你乘坐电梯从一楼到十楼,只能拿一次钻石。

[2]每层楼电梯门都会打开一次,(每层楼)只能拿一次钻石。

哎呦我草,我勒个肾

2015年03月19日 10:32:19

CSDN-木水辰

毕业生北京邮电大学

你要是早点说出来,就能获得积分和C币了。楼上已经有人说出这个思路了。

2015年03月19日 11:15:43

雨过天空

毕业生青岛理工大学

闭着眼到第十层,然后睁开眼把第十层的拿走,反正你就看到一个,它当然就是最大的

2015年03月19日 15:19:27

雨过天空

毕业生青岛理工大学

把题改改多好,可以自由操纵电梯停下,把混乱的钻石重新排序什么的

2015年03月19日 15:27:52

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

CSDN-木水辰

毕业生北京邮电大学

感谢清晰明确的思路和代码分享。

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

2015年03月20日 09:55:15

道成空

毕业生湖南城市学院

和9个人一起坐电梯上去每层其中一人拿一个,然后由大到小依次次出去交任务。(合作就有共赢)

10 9 8 7 6 5 4 3 2 1

9 8 7 6 5 4 3 2 1 0

8 7 6 5 4 3 2 1 0 0

...

1 0 0 0 0 0 0 0 0 0

2015年03月20日 12:27:13

Wayde_Fang

毕业生安徽师范大学

常规方法上面已经有人分析了,我说个不常规的吧,题目没说不能事先知道钻石的具体大小,那么首先记下最大的钻石是什么样子,电梯开门的时候看一下如果是最大的那颗就立即拿下!钻石到手!

2015年03月20日 16:58:53

大块木

毕业生邵阳学院

 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

miao9551

学生江苏理工学院

题中说了,每层楼钻石的大小不一,也就是说最大的钻石只可能在一层上,我们把楼层按顺序分成4个部分3,3,3,1,然后从以一个部分(也就是前3层中随机选一个,无所谓啦,假设你的第六感很准确的告诉你另外的一个楼层上的一定不是最大钻石,此时你换成另外的一个楼层找到最大钻石的概率是2/3),同里从另外两个有3层的部分中找出来可能是最大的,此时你在前面三个中选出的三个可能最大的钻石中选出一个最小的,第六感告诉你了另外一个,你选择自己选出来的概率会更大些,把它排除掉,现在只剩下3个有可能是最大的钻石,按照第一个部分的选法选出最大,此时你选择的钻石最大的可能性也是最大的2/3;概率存在于被给予的条件下,概率不能寄托在实际的物体上

2015年03月21日 18:47:07

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

weixiaokang

毕业生南京邮电大学

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

2015年03月22日 21:19:05

CSDN-木水辰

毕业生北京邮电大学

能够将概率论所学为所用,恭喜你,获得高校俱乐部送出的 30 积分和 30 C币。

2015年03月23日 11:42:31
Top_arrow