腾讯BT的面试题

请腾讯HR出来答题…………

因为方形井盖的对角线长度是比变长长的，就是等边三角形的斜边长度，你要是这样放肯定会掉下去啊

另外我觉的圆形的井盖也好运输一点吧，滚着就过去了，方形的还要搬过去，哈哈~~

真无聊，不仅是不会解答，连问题和解答都不能理解。

题目的意思是要选择一种策略，使你得到最大钻石的概率最大，注意：是最大化拿到最大钻石的概率，这很重要，而不是提高拿到的钻石重量的数学期望（由于没有钻石的具体重量，肯定无法为这个目标制定策略）,也不是提高拿到的钻石大小排名的数学期望（这也是一种目标，但是策略会复杂些，未仔细分析）。理解了这一点，就可以得到所有的策略，分为2大类：
1.不管任何情况，在第i（i在1到10之间）个门出去。
2.前m个门不出去（m在1到9之间），见到比前m个门中最大的还大就立即出去。
所有的可能策略必然属于这其中之一，自己可以详细分析。

其中第1类策略拿到最大钻石概率显然为1/10。
第2类策略拿到最大钻石概率为：i=m到9 求和m*P(m-1,i-1)/10-i ，再除以P(m,10)。P是排列算符。

以m=1解释下：
解释钻石从小到大为d1,d2,...d10
第一个门不出去，如果第一个门为d1,可以拿到最大的概率为（相当于在d2到d10之间随机拿）1/9，
如果第一个门为d2，可以拿到最大的概率为(相当于在d3到d10之间随机拿)1/8，依次类推，
如果第一个门为d9，可以拿到最大的概率为1，如果第一门为d10，可以拿到最大的概率为0，
所以总概率为(1/9+1/8+...1)/10 ，约为0.282



根据公式可以计算如下：
m=1，p=0.282
m=2，p=0.366
m=3，p=0.398
m=4，p=0.398
m=5，没算了，显然该函数在m=3，4达到极值，然后开始下降
...
m=9，p=0.1（这个很容易理解）

最终策略是前3（或4）个门不出去，见到比前3个门（或4）中最大的还大就立即出去。

楼上的思路估计是对的。
如果并排放10个门，只能从一个出去那么概率是1/10。

不过楼上的算法可能还不够准确：
“第一个门不出去，如果第一个门为d1,可以拿到最大的概率为（相当于在d2到d10之间随机拿）1/9， ”
后面的概率应该不是1/9

你为什么会指望hr也这么想？

因为题目说得很清楚，怎样拿到最大的钻石

这位兄弟很强嘛
感觉很有道理 学数学的？
呵呵 你如果去面试就中了

那为什么漏雨水的盖子不做成圆的而是长方的呢

我以为是方的有可能掉进去。。圆的不会。。好像看过这题

Lxh的思路应该是对的，不过概率可能有点问题，m层之后各层出去的概率应该不是相同的。
我写了下代码模拟了一下

import java.util.Random;

public class JustForTest
{
	// 随机数的最大值
	private static int MAX_RANDOM_VALUE = 5 * 7 * 8 * 9;
	// 钻石的个数
	private static int DIAMOND_COUNT = 10;

	private static Random RANDOM = new Random();

	public static void main(String[] args)
	{
		// 循环的次数
		int count = 1000000;
		// i表示到第几层后才去取
		for (int i = -1; i < DIAMOND_COUNT - 1; i++)
		{
			// 得到最大的次数
			int trueGet = 0;
			for (int j = 0; j < count; j++)
			{
				int[] randomDiamonds = generateRandomNumbers();
				int index = getMaxNumber(randomDiamonds, i);
				// 如果是最大的，则取到了
				if (randomDiamonds[index] == DIAMOND_COUNT - 1)
				{
					trueGet++;
				}
			}
			// 计算得到最大的比例
			float percent = (float) trueGet / count;
			System.out.println("m=" + (i + 1) + ", p=" + percent);
		}
	}

	// 生成0到9的随机字符窜数组
	private static int[] generateRandomNumbers()
	{
		boolean[] hasUsed = new boolean[DIAMOND_COUNT];
		int[] randomNumbers = new int[DIAMOND_COUNT];
		for (int i = 0; i < DIAMOND_COUNT; i++)
		{
			// 得到随机钻石的大小
			int size = RANDOM.nextInt(MAX_RANDOM_VALUE) % DIAMOND_COUNT;
			while (hasUsed[size])
			{
				size = (size + 1) % DIAMOND_COUNT;
			}
			randomNumbers[i] = size;
			hasUsed[size] = true;
		}
		return randomNumbers;
	}

	private static int getMaxNumber(int[] numbers, int m)
	{
		int maxSize = -1;
		// 取m层中最大的
		for (int i = 0; i <= m; i++)
		{
			if (numbers[i] > maxSize)
			{
				maxSize = numbers[i];
			}
		}
		// 从m+1层开始取比maxSize还大的
		for (int i = m + 1; i < numbers.length; i++)
		{
			// 如果比maxSize还大，则出电梯
			if (numbers[i] > maxSize)
			{
				return i;
			}
		}
		// 如果没有取到，则取最后一个
		return numbers.length - 1;
	}
}

最后输出的结果是:
m=0, p=0.100024(这个相当于直接从1楼出来)
m=1, p=0.234854
m=2, p=0.289502
m=3, p=0.307835
m=4, p=0.302407
m=5, p=0.282525
m=6, p=0.249452
m=7, p=0.206941
m=8, p=0.156819
m=9, p=0.100326(这个相当于直接从10楼出来)

有个疑问，这个策略是怎么想到的啊？
（我是想不出来的）