62,614
社区成员
发帖
与我相关
我的任务
分享Google校园招聘的面试题目
刚在电脑报上看到一道有意思的题说是Google校园招聘的其中一道面试题
“有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。”
大家都是怎么想的都来说说吧...........
“有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。”
大家都是怎么想的都来说说吧...........
...全文
请发表友善的回复…
发表回复
westwin 2007-01-13
- 打赏
- 举报
mark
mogolo 2006-12-12
- 打赏
- 举报
为什么每个人都在说自己怎么想的 而没有看看别人的做法？
绿色夹克衫 2006-12-12
- 打赏
- 举报
前几个纯数学证明，感觉都不太理想，只有阿丹的证明是比较全面充分的，而且很直观。看过之后，我觉得还有一些细小之处可以补充。
对于danjiewu(阿丹)证明的一点补充：
在最优方案中，临界层正好处于方案中的某一层时，会出现只有1个1的编码，例如：第一次在14层扔碎了，在1-13层扔没有碎，此时可以判断，临界层是14，编码为10000000000000。
否则14位编码，只有2个1的话，只能表示91层，再加上临界层正好处于方案中的某一层的情况，即只有1个1的情况，共14种，就能够表示105层了。实际上就是C15，取2的问题。15 = 14（最优情况下的次数） + 2（棋子数） -1
同理可以推出，如果有N个棋子的话，K层楼，最短编码会是多长呢（即最优情况下，需要多少次）？
以4颗棋子，1000层为例，经计算后，应当是11次，因为C14取4 = 1001，14 = 11（最优情况下的次数） + 4（棋子数） - 1。
第一颗棋子应当在286或285层扔，后面具体的扔法，大家可以自己考虑，在这里不细说了，最优方案应当有11种。
对于danjiewu(阿丹)证明的一点补充：
在最优方案中，临界层正好处于方案中的某一层时，会出现只有1个1的编码，例如：第一次在14层扔碎了，在1-13层扔没有碎，此时可以判断，临界层是14，编码为10000000000000。
否则14位编码，只有2个1的话，只能表示91层，再加上临界层正好处于方案中的某一层的情况，即只有1个1的情况，共14种，就能够表示105层了。实际上就是C15，取2的问题。15 = 14（最优情况下的次数） + 2（棋子数） -1
同理可以推出，如果有N个棋子的话，K层楼，最短编码会是多长呢（即最优情况下，需要多少次）？
以4颗棋子，1000层为例，经计算后，应当是11次，因为C14取4 = 1001，14 = 11（最优情况下的次数） + 4（棋子数） - 1。
第一颗棋子应当在286或285层扔，后面具体的扔法，大家可以自己考虑，在这里不细说了，最优方案应当有11种。
绿色夹克衫 2006-12-12
- 打赏
- 举报
不好意思，我误导了大家，正确答案应当是楼上的。
我将C(11,4) + C(11,3) + C(11,2) + C(11,1)简化成了C(14,4)，实际上二者不是一一对映的关系，虽然每个C(14,4)都能对应一个C(11,4) + C(11,3) + C(11,2) + C(11,1)中的元素，但存在C(14,4)中的多个情况对应同一个C(11,4) + C(11,3) + C(11,2) + C(11,1)元素的问题。
4个棋子，1000层楼应当是13次：C(13,4)(碎4个) + C(13,3)(碎3个) + C(13,2)(碎2个) + C(13,1)(碎1个) > 1000
我将C(11,4) + C(11,3) + C(11,2) + C(11,1)简化成了C(14,4)，实际上二者不是一一对映的关系，虽然每个C(14,4)都能对应一个C(11,4) + C(11,3) + C(11,2) + C(11,1)中的元素，但存在C(14,4)中的多个情况对应同一个C(11,4) + C(11,3) + C(11,2) + C(11,1)元素的问题。
4个棋子，1000层楼应当是13次：C(13,4)(碎4个) + C(13,3)(碎3个) + C(13,2)(碎2个) + C(13,1)(碎1个) > 1000
danjiewu 2006-12-12
- 打赏
- 举报
4颗棋子，1000层的话，应该是至少13次。
用C（13，4）+C（13，3）+C（13，2）+C（13，1）与1000比较，而不是用C（13+4-1，4）与1000比较。
前面提出的最优解的判断条件还是有点问题。
假设编码长度至少为i才能确保得到临界层，棋子数为n。
条件为：不存在未被使用的编码；并且对所有的编码，不存在2个编码长度之差大于2，除非较短的那个编码已经包含了n个1。
用C（13，4）+C（13，3）+C（13，2）+C（13，1）与1000比较，而不是用C（13+4-1，4）与1000比较。
前面提出的最优解的判断条件还是有点问题。
假设编码长度至少为i才能确保得到临界层，棋子数为n。
条件为：不存在未被使用的编码；并且对所有的编码，不存在2个编码长度之差大于2，除非较短的那个编码已经包含了n个1。
绿色夹克衫 2006-12-12
- 打赏
- 举报
这么长时间还没有个定论么？
to：楼上的
你的方案，至少我看过了，是有问题的，你的错误在于按照固定的层数来试，却没有考虑到，扔过一次后，这个数值是需要重新计算的，比如第一次在10层扔，如果没有碎，那么这个问题就变成了2颗棋子，90层的楼，怎么扔最优的问题。
阿丹在后面的帖子里，修正了自己的方案，并给出了合理的数学证明，我想这个问题已经有了定论了，最悲观的尝试次数，处于13、14这个区间时，有最优方案。
至于数学证明方式，有很多种，大家有兴趣的话可以多讨论一下。
to：楼上的
你的方案，至少我看过了，是有问题的，你的错误在于按照固定的层数来试，却没有考虑到，扔过一次后，这个数值是需要重新计算的，比如第一次在10层扔，如果没有碎，那么这个问题就变成了2颗棋子，90层的楼，怎么扔最优的问题。
阿丹在后面的帖子里，修正了自己的方案，并给出了合理的数学证明，我想这个问题已经有了定论了，最悲观的尝试次数，处于13、14这个区间时，有最优方案。
至于数学证明方式，有很多种，大家有兴趣的话可以多讨论一下。
shuxuejianzi 2006-12-10
- 打赏
- 举报
如此简单的问题被讨论了这么多竟然~~~简单的数学期望估算~~
首先说临界层是1到100的任意层,概率都相等
先说答案:如果楼层是N,则答案那个从一层开始往上走的步长是根下N
证明:当步长为一的时候:期望为101/2
为2时:51/2 ......
分析:当步长为n时候,最少需要一步完成,最多需要100/n完成(此处这个式子只适合n刚好能被100整除,当不能整除时,此值另说~公式稍微麻烦点,打起来麻烦呵呵)则期望为(1+100/n+n)/2
高中数学知识,当n为根下N时这个数最小,解决~~~
当然如果不能刚好开根下的时候,需要递归了,先是取开根后的整数,然后先解决这个数的平方内的这些楼层,剩下的楼层解决方案为剩下楼层数再开方,相当于一个递归的过程~~~~
解决完毕,望网友们指正~!
首先说临界层是1到100的任意层,概率都相等
先说答案:如果楼层是N,则答案那个从一层开始往上走的步长是根下N
证明:当步长为一的时候:期望为101/2
为2时:51/2 ......
分析:当步长为n时候,最少需要一步完成,最多需要100/n完成(此处这个式子只适合n刚好能被100整除,当不能整除时,此值另说~公式稍微麻烦点,打起来麻烦呵呵)则期望为(1+100/n+n)/2
高中数学知识,当n为根下N时这个数最小,解决~~~
当然如果不能刚好开根下的时候,需要递归了,先是取开根后的整数,然后先解决这个数的平方内的这些楼层,剩下的楼层解决方案为剩下楼层数再开方,相当于一个递归的过程~~~~
解决完毕,望网友们指正~!
frank_c 2006-12-10
- 打赏
- 举报
支持10楼10楼一扔
danjiewu 2006-12-10
- 打赏
- 举报
mogolo(mogolo)的证明和我一开始一样没有注意到分成的多个小的题目不是等同的，想简单了。
不过如果是面试那么短的时间想要答出完全正确的答案恐怕不容易，题目不错。
不过如果是面试那么短的时间想要答出完全正确的答案恐怕不容易，题目不错。
finalcreator 2006-12-10
- 打赏
- 举报
zzmsl(周先生) ( ) 信誉：100 Blog 2006-12-6 17:26:49 得分: 0
这种应该找数学的来解决。解决出来了程序员写代码。
晕
这种应该找数学的来解决。解决出来了程序员写代码。
晕
danjiewu 2006-12-10
- 打赏
- 举报
上次发帖漏了一段，sorry。现在补上。
=========================================
我把题目想简单了，每隔10层扔一次不是最优解，只是还算可以的解。
假设n为棋子数，i为可以扔的次数，F（n，i）表示可以确保能得到临界点的最大楼层数。
显然若n = 1，F（n，i）= i； //这里认为楼层从1层开始
若n >= i，F（n，i）=2^i - 1；
其他情况下F（n，i）=F（n-1，i-1）+ F（n，i-1）+1。
对F（n，i）计算有疑问的可以再另外讨论，F（n，i）的计算公式暂时还没有想出来。
要求n个棋子，楼层为f的情况下的最优解，首先找到i使得F（n，i-1）<f并且F（n，i）>=f。
i即至少需要扔i次才能确保找到临界点。第一次扔的楼层为F（n-1，i-1）+1，以此类推根据第一次扔的结果确定第二次扔的楼层。
对于google的这道题，就是要找到i使得F（2，i-1）<100并且F（2，i）>=100。
F（2，2）= 3
F（2，3）= 3+2+1 =6
F（2，4）= 6+3+1 =10
F（2，5）= 10+4+1 =15
可以发现F（2，n）正好等于1到n的和。
F（2，13）= 91
F（2，14）= 105
得到i = 14，至少需要14次可以确定临界点。
至于要得到所有情况下扔的次数最少的最优解，应该不止一种。
=========================================================
又考虑了一下，google的问题可以看为：
用0和1表示的编码来表示1-100的数，限制条件为：1最多只能出现2次，而且如果出现2次1，则第二个1必须在编码的最后。（实际题目还有个要求，1-100的编码必须是按顺序的，不过对解题没有影响）实际意义就是，1为摔碎，0为未摔碎，在第几位就是表示扔的第几次。
所要求的就是使编码的总长度最小。
要求最短的编码长度，参考Huffman编码、Shanon编码，只不过其中像11，101这样饱含了2个1的编码就不能再拆分，而且1-100是等概率的。简单点说，等概率的情况下，短编码没有用完，是不会用到长编码的。所以如果长度为14的编码已经足够，那么最优解（就是所有情况下扔的总次数之和最少）就不可能出现长度超过14的编码。如果满足下面的条件，那么就可以确定是最优解：
没有使用长度超过14的编码；
所有长度小于14的包含有2个1的编码都对应了一个值；
除了包含2个1的编码，没有使用长度小于13的编码。
至于证明解法满足上面的条件，应该不是很难，自己也可以判断的出来。
=========================================
我把题目想简单了，每隔10层扔一次不是最优解，只是还算可以的解。
假设n为棋子数，i为可以扔的次数，F（n，i）表示可以确保能得到临界点的最大楼层数。
显然若n = 1，F（n，i）= i； //这里认为楼层从1层开始
若n >= i，F（n，i）=2^i - 1；
其他情况下F（n，i）=F（n-1，i-1）+ F（n，i-1）+1。
对F（n，i）计算有疑问的可以再另外讨论，F（n，i）的计算公式暂时还没有想出来。
要求n个棋子，楼层为f的情况下的最优解，首先找到i使得F（n，i-1）<f并且F（n，i）>=f。
i即至少需要扔i次才能确保找到临界点。第一次扔的楼层为F（n-1，i-1）+1，以此类推根据第一次扔的结果确定第二次扔的楼层。
对于google的这道题，就是要找到i使得F（2，i-1）<100并且F（2，i）>=100。
F（2，2）= 3
F（2，3）= 3+2+1 =6
F（2，4）= 6+3+1 =10
F（2，5）= 10+4+1 =15
可以发现F（2，n）正好等于1到n的和。
F（2，13）= 91
F（2，14）= 105
得到i = 14，至少需要14次可以确定临界点。
至于要得到所有情况下扔的次数最少的最优解，应该不止一种。
=========================================================
又考虑了一下，google的问题可以看为：
用0和1表示的编码来表示1-100的数，限制条件为：1最多只能出现2次，而且如果出现2次1，则第二个1必须在编码的最后。（实际题目还有个要求，1-100的编码必须是按顺序的，不过对解题没有影响）实际意义就是，1为摔碎，0为未摔碎，在第几位就是表示扔的第几次。
所要求的就是使编码的总长度最小。
要求最短的编码长度，参考Huffman编码、Shanon编码，只不过其中像11，101这样饱含了2个1的编码就不能再拆分，而且1-100是等概率的。简单点说，等概率的情况下，短编码没有用完，是不会用到长编码的。所以如果长度为14的编码已经足够，那么最优解（就是所有情况下扔的总次数之和最少）就不可能出现长度超过14的编码。如果满足下面的条件，那么就可以确定是最优解：
没有使用长度超过14的编码；
所有长度小于14的包含有2个1的编码都对应了一个值；
除了包含2个1的编码，没有使用长度小于13的编码。
至于证明解法满足上面的条件，应该不是很难，自己也可以判断的出来。
态度决定品质 2006-12-09
- 打赏
- 举报
liaotao(牛牛) , 看了下你的代码，有些不明白。
问下：如五楼破，临界在五楼以下； 现在还有一个棋子，假设临界是3楼，3楼破；程序应该输出2楼，临界是2楼，矛盾；看看我的理解和你的有什么不同
问下：如五楼破，临界在五楼以下； 现在还有一个棋子，假设临界是3楼，3楼破；程序应该输出2楼，临界是2楼，矛盾；看看我的理解和你的有什么不同
zhangfan790913 2006-12-09
- 打赏
- 举报
这个贴子怎么还没结啊?
越看越受不了, 竟然还有这么多人在 找破了两次的临界值????晕啊!!!!
在X楼不碎,在X+2碎了,你知道X+1是临界???他是怎么个临界?是碎还是不碎,好好看看人家的回贴!!!!
越看越受不了, 竟然还有这么多人在 找破了两次的临界值????晕啊!!!!
在X楼不碎,在X+2碎了,你知道X+1是临界???他是怎么个临界?是碎还是不碎,好好看看人家的回贴!!!!
mogolo 2006-12-09
- 打赏
- 举报
*****************************************************************************
希望都看看这个帖子 ！！！！！！！！！！！！！
谢谢大家
*****************************************************************************
这道题使用的方法是 concurrence 的 merge方法
简单说就是把一个大的题目分成几个等份的小的题目
T(n)=aT(n/b) + f(n)
a表示分成的份数 b表示把n分成多少份 f(n)表示分的过程中的代价
这里 a=n/k 的话 b=k f(n)=k+2k+...+(n/k)*k
T(n)=n/kT(n/k) + k(k+n)/2=n/kT(n/k) +O(n)
根据master method（已经证明的方法，可以查找算法导论4.4的证明)
当O(n^logb(a))=f(n)=O(f(n))时 可取到整体最小为n^logb(a）*log2(n)
所以 logb(a)=1
logk(100/k)=1
k=100/k
k=10
证明完毕
******************************************************************************
希望都看看这个帖子 ！！！！！！！！！！！！！
谢谢大家
*****************************************************************************
这道题使用的方法是 concurrence 的 merge方法
简单说就是把一个大的题目分成几个等份的小的题目
T(n)=aT(n/b) + f(n)
a表示分成的份数 b表示把n分成多少份 f(n)表示分的过程中的代价
这里 a=n/k 的话 b=k f(n)=k+2k+...+(n/k)*k
T(n)=n/kT(n/k) + k(k+n)/2=n/kT(n/k) +O(n)
根据master method（已经证明的方法，可以查找算法导论4.4的证明)
当O(n^logb(a))=f(n)=O(f(n))时 可取到整体最小为n^logb(a）*log2(n)
所以 logb(a)=1
logk(100/k)=1
k=100/k
k=10
证明完毕
******************************************************************************
wanna51 2006-12-09
- 打赏
- 举报
这样，最多测试的次数在10-16次，
上面也有提到13次，为什么没有采取这个答案呢？
在61层以下最多次数在10-13次
在61层以上最多次数在13-16次
这种情况，在实际中，应该比每次最多测试次数都在13层要好吧。
具体应该用概率来解释吧，可惜我概率学得不好，讲不出详细的道理 ：（
上面也有提到13次，为什么没有采取这个答案呢？
在61层以下最多次数在10-13次
在61层以上最多次数在13-16次
这种情况，在实际中，应该比每次最多测试次数都在13层要好吧。
具体应该用概率来解释吧，可惜我概率学得不好，讲不出详细的道理 ：（
wanna51 2006-12-09
- 打赏
- 举报
根据公式：f(x) = floor/x+x 算出f(x)最大值为sqr(floor)
第一次：floor = 100 , x = 10楼
如果10楼碎了，那么测试次数为 x -1 + 1 = 10次
如果在x=10楼没有碎
第二次：floor = 100 - x = 90楼，此时x = 10楼，意思为，从20楼开始丢。。。。依此类推
测试楼层 摔坏所在楼层 测试次数
1-100 10 10
11-100 20 11
21-100 29 11
30-100 38 12
39-100 46 12
47-100 54 13
55-100 61 13
62-100 68 14
69-100 74 14
75-100 80 15
81-100 85 15
86-100 89 15
90-100 93 16
94-100 96 16
97-100 98 16
98-100 99 16
class Program
{
static int count = 0;
static void Main(string[] args)
{
int floor = 100;
Trace.WriteLine("Floor Range\tBreak Floor\tCount");
GetN(floor);
Console.Read();
}
static void GetN(int floor)
{
double nn = Math.Sqrt(floor);
int n = (int)Math.Floor(nn);
if (n - nn != 0) n++;
count++;
int start = 100 - floor + 1;
int leftFloor = floor - n;
Trace.WriteLine(start + "-100\t\t" + (start + n - 1) + "\t\t" + (n + count - 1));
switch (leftFloor)
{
case 1:
break;
case 2:
Trace.WriteLine("98-100\t\t99\t\t" + (count + 1));
break;
default:
GetN(floor - n);
break;
}
}
}
第一次：floor = 100 , x = 10楼
如果10楼碎了，那么测试次数为 x -1 + 1 = 10次
如果在x=10楼没有碎
第二次：floor = 100 - x = 90楼，此时x = 10楼，意思为，从20楼开始丢。。。。依此类推
测试楼层 摔坏所在楼层 测试次数
1-100 10 10
11-100 20 11
21-100 29 11
30-100 38 12
39-100 46 12
47-100 54 13
55-100 61 13
62-100 68 14
69-100 74 14
75-100 80 15
81-100 85 15
86-100 89 15
90-100 93 16
94-100 96 16
97-100 98 16
98-100 99 16
class Program
{
static int count = 0;
static void Main(string[] args)
{
int floor = 100;
Trace.WriteLine("Floor Range\tBreak Floor\tCount");
GetN(floor);
Console.Read();
}
static void GetN(int floor)
{
double nn = Math.Sqrt(floor);
int n = (int)Math.Floor(nn);
if (n - nn != 0) n++;
count++;
int start = 100 - floor + 1;
int leftFloor = floor - n;
Trace.WriteLine(start + "-100\t\t" + (start + n - 1) + "\t\t" + (n + count - 1));
switch (leftFloor)
{
case 1:
break;
case 2:
Trace.WriteLine("98-100\t\t99\t\t" + (count + 1));
break;
default:
GetN(floor - n);
break;
}
}
}
aoricanfeng 2006-12-09
- 打赏
- 举报
呵呵，有意思，二分法是很高效的，但对这道题好像不实用哦，毕竟这里的棋子如两次都被摔坏了，这题也没办法继续下去了。
阿丹的方法对这题很实用，其实对于“每隔n层楼试一次”的n值的确定，用高中的知识就行了。
把100楼分n份，每份100/n,求（n＋100/n）的最小值（也是这种方法的最差情况），当n＝10时，可以得该最差情况是20
阿丹的方法对这题很实用，其实对于“每隔n层楼试一次”的n值的确定，用高中的知识就行了。
把100楼分n份，每份100/n,求（n＋100/n）的最小值（也是这种方法的最差情况），当n＝10时，可以得该最差情况是20
zhangfan790913 2006-12-09
- 打赏
- 举报
一、关注1楼站立丢到地面的距离
大家自己看结果
public static void main(String args[]) {
for (int n = 1; n <= 100; n++) {
System.out.println("-------------------");
System.out.print("n=" + n + " ");
if( 0 == 100%n ){
System.out.println("最多" + (n + (100 / n) - 2));
} else {
System.out.println("最多" + (n + (100 / n) - 3));
}
}
}
---------------------------------------------------
二、忽略1楼
大家自己看结果
public static void main(String args[]) {
for (int n = 1; n <= 99; n++) {
System.out.println("-------------------");
System.out.print("n=" + n + " ");
if( 0 == 100%n ){
System.out.println("最多" + (n + (100 / n) - 2));
} else {
System.out.println("最多" + (n + (100 / n) - 3));
}
}
}
大家自己看结果
public static void main(String args[]) {
for (int n = 1; n <= 100; n++) {
System.out.println("-------------------");
System.out.print("n=" + n + " ");
if( 0 == 100%n ){
System.out.println("最多" + (n + (100 / n) - 2));
} else {
System.out.println("最多" + (n + (100 / n) - 3));
}
}
}
---------------------------------------------------
二、忽略1楼
大家自己看结果
public static void main(String args[]) {
for (int n = 1; n <= 99; n++) {
System.out.println("-------------------");
System.out.print("n=" + n + " ");
if( 0 == 100%n ){
System.out.println("最多" + (n + (100 / n) - 2));
} else {
System.out.println("最多" + (n + (100 / n) - 3));
}
}
}
fim 2006-12-08
- 打赏
- 举报
up
Aricc 2006-12-08
- 打赏
- 举报
晕，高手啊
加载更多回复（244）
