［百度面试题］100层楼，球可能会在某一层楼摔坏，问用2个球，最坏情况下几次测试可以找出该楼层 - CSDN博客
［百度面试题］100层楼，球可能会在某一层楼摔坏，问用2个球，最坏情况下几次测试可以找出该楼层
该题还可以扩展，比如说给更多的球，如3个球，多少次测试可以找出楼层。
分析如下：
用动态规划解这个问题
设f(a, b)为a个球做b次测试可以测试到的楼层数，可以确定的楼层数即为f(a, b) + 1，因为第1层不需测试，需要测试的楼层号仅仅为[2, f(a, b) + 1]共f(a, b)层，也就是a个球b次测试可以测试到的楼层数。考虑第1次测试，测试的楼层记为x：
1）如果球破了，就需要测试x下面的楼层，还剩下a-1个球b-1次测试，测试的楼层数为f(a - 1, b - 1)。
2）如果球没有破，那么需要测试x上面的楼层，还剩下a个球b-1次测试，测试的楼层数为f(a, b - 1)。
a个球b次测试为1）2）测试的楼层数及第1次测试了的1层，所以：
f(a, b) = f(a - 1, b - 1) + f(a, b - 1) + 1 & & & & & & & & & & & & & & & & & & & & & & &（1）
考虑初始条件，显然f(a, 1) = 1（a &= 1，1次测试可以测试到的楼层数当然为1，不论多少个球），f(1, b) = b（b &= 1，1个球做了b次测试当然测试到了b层楼）。
强调一下：注意f(a, b)为测试到的楼层数，f(a, b)加上不需测试的楼层才是可以确定的楼层（f(a, b) + 1）。
动态规划解（1）式即可。
一般来说，a &= 2（1个球意义不大），可以计算出f(2, 64) =&2080，f(3, 64) = 43744，f(4, 64) = 679120。
* a balls, n floors, want to find the minimum number of floor
* where a ball drops will be broken. output the minimum number
* of drops
* METHOD: dynamic programming
* assum the answer is b, that is the number of drops
* f(a, b): the maximum number of floors, when a balls and b drops
* f(a, b) = 1 + f(a, b - 1) + f(a - 1, b - 1)
* obviously, f(a, 1) = 1; f(1, b) = b
#include &stdio.h&
#include &stdlib.h&
#include &assert.h&
#include &string.h&
#define DEBUG
#define MAX_B 64
#define MAX_A 16
#define f(a, b) ff[a - 1][b - 1]
static unsigned int a,
static unsigned long long ff[MAX_A][MAX_B];
static void init()
memset(ff, 0, sizeof(ff));
/*f(a, 1) = 1*/
for (i = 1; i &= MAX_A; i++){
f(i, 1) = 1;
/*f(1, b) = b + 1*/
for (i = 1; i &= MAX_B; i++){
static unsigned long long do_find_min_drops(int i, int j)
if (f(i, j))
return f(i, j);
f(i, j) = do_find_min_drops(i - 1, j - 1) +
do_find_min_drops(i, j - 1) + 1;
return f(i, j);
static void do_print_drops(int i, int j, unsigned long long min,
unsigned long long max)
if (min & max)
if (1 == i){
assert(j == max - min + 1);
for (i = i &= i++){
printf("%5d", i);
printf("/n");
printf("*************/n");
if (1 == j){
assert(min == max);
printf("%5lld/n", max);
printf("*************/n");
printf("%5lld", min + f(i - 1, j - 1));
do_print_drops(i - 1, j - 1, min, min + f(i - 1, j - 1) - 1);
do_print_drops(i, j - 1, min + f(i - 1, j - 1) + 1, max);
static void print_drops(int ans)
do_print_drops(a, ans, 2, n);/*[2..n]*/
static void find_min_drops()
/*NOTE: number of floors are [1, n]*/
#if 0//def DEBUG
for (i = 2; i &= MAX_A; i++){
for (j = 2; j &= MAX_B; j++){
printf("f(%d, %d) = %lld/n", i, j, do_find_min_drops(i, j));
printf("****************/n");
j = MAX_B;
while (i &= j){
m = (i + j) / 2;
if (do_find_min_drops(a, m) + 1 & n)
* why +1? because the 1st floor need not to test
i = m + 1;
j = m - 1;
if (ans & MAX_B){
printf("the number of the maximum drops(MAX_B = %d) is too small/n", MAX_B);
printf("maximum floors "
"can be tested is f(%d, %d) + 1 = %lld + 1. STOP/n", a, MAX_B, f(a, MAX_B));
printf("the minimum drops: %d/n", ans);
print_drops(ans);
#ifdef DEBUG
for (i = 1; i &= i++){
for (j = 1; j &= j++){
printf("f(%d, %d) = %lld/n", i, j, f(i, j));
printf("****************/n");
int main(int argc, char **argv)
if (3 != argc){
fprintf(stderr, "usage: %s a n/n", argv[0]);
a = atoi(argv[1]);
n = atoi(argv[2]);
printf("a = %d/tn = %d/n", a, n);
assert(a & 0 && a & MAX_A && n & 0);
find_min_drops(); /*drops: 1*/
这里，我采用递归的方法打出了测试过程，解释如下：
1）2个球，100层楼时，可以计算出
f(2, 13) = 91
f(2, 14) = 105
因此需要的测试次数为14，测试过程为
&& 15 & &2 & &3 & &4 & &5 & &6 & &7 & &8 & &9 & 10 & 11 & 12 & 13 & 14
*************
&& 28 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27
*************
&& 40 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39
*************
&& 51 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50
*************
&& 61 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60
*************
&& 70 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69
*************
&& 78 & 71 & 72 & 73 & 74 & 75 & 76 & 77
*************
&& 85 & 79 & 80 & 81 & 82 & 83 & 84
*************
&& 91 & 86 & 87 & 88 & 89 & 90
*************
&& 96 & 92 & 93 & 94 & 95
*************
&&100 & 97 & 98 & 99
*************
第1次测试为15层，如果球破了，则剩下的一个球测试[2, 14]，总共的测试次数最多为1+13=14
如果球没破，则测试28层，如果破了，剩下的一个球测试[16, 27]，总共的测试次数最多为1+1+12 = 14
如果球没破，测试100层，如果破了，剩下的一个球测试[97, 99]，总共的测试次数最多为1{11} + 3 = 14
如果球没破，则不存在楼层使得球可以摔破。
2）3个球，100层楼，可以计算出
f(3, 8) = 92
f(3, 9) = 129
因此测试测试最多为9次。测试过程：
&& 38 & &9 & &2 & &3 & &4 & &5 & &6 & &7 & &8
第1个球测试38层，如果破了，第2个球测试9层，如果还破了，剩下的一个球测试[2, 8]层，总共的测试次数2 + 7 = 9
*************
&& 16 & 10 & 11 & 12 & 13 & 14 & 15
如果第2个球没破，则测试16层，如果破了，第3个球测试[10, 15]，总共的测试测试3 + 6 = 9
*************
&& 22 & 17 & 18 & 19 & 20 & 21
如果第2个球没破，则测试22层，如果破了，第3个球测试[17, 21]，总共的测试测试4 + 5 = 9
*************
&& 27 & 23 & 24 & 25 & 26
如果第2个球没破，则测试27层，如果破了，第3个球测试[23, 26]，总共的测试测试5 + 4 = 9
*************
&& 31 & 28 & 29 & 30
如果第2个球没破，则测试31层，如果破了，第3个球测试[28, 30]，总共的测试测试6 + 3 = 9
*************
&& 34 & 32 & 33
*************
&& 36 & 35
*************
*************
&& 67 & 45 & 39 & 40 & 41 & 42 & 43 & 44
如果第1个球没破，则测试67层，如果破了，第2个球测试45层，如果破了，第3个球测试[39, 44]，总共的测试次数3 + 6 = 9。以下类似，不再重复。
*************
&& 51 & 46 & 47 & 48 & 49 & 50
*************
&& 56 & 52 & 53 & 54 & 55
*************
&& 60 & 57 & 58 & 59
*************
&& 63 & 61 & 62
*************
&& 65 & 64
*************
*************
&& 89 & 73 & 68 & 69 & 70 & 71 & 72
*************
&& 78 & 74 & 75 & 76 & 77
*************
&& 82 & 79 & 80 & 81
*************
&& 85 & 83 & 84
*************
&& 87 & 86
*************
*************
&&105 & 94 & 90 & 91 & 92 & 93
*************
&& 98 & 95 & 96 & 97
*************
&&101 & 99 &100
*************
&&103 &102
*************
*************
3）对于更多球的情况，输出的测试方法分析起来有些麻烦，但是上面的动态规划法求出的结果就容易理解了，且是保证正确的。
本文已收录于以下专栏：
相关文章推荐
有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？？？
2012年腾讯实习生笔试的时候，有一...
题目：有一栋100层高楼,从某一层开始扔下的玻璃球刚好摔坏,现有两个玻璃球,试用最简便的方法确定这个恰好摔坏玻璃球的那层. 这是一道著名的面试题目，仅写出我的思路和解法． 首先从题目得出基本思路１．第...
最近做的一道腾讯笔试题。
该题还可以扩展，比如说给更多的球，如3个球，多少次测试可以找出楼层。
分析如下：
用动态规划解这个问题
设f(a, b)为a个球做b次测试可以测试到的楼层数，可以确定的楼层数即为f(a, b) ...
这道题是说，100层楼，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法，因为只想记录一下思路和讨论过程，写得很简略。现在，我...
等价类划分
边界值分析
题三等价类划分把全部输入数据合理地划分为若干等价类，在每一个等价类中取一个数据作为测试的输入条件，就可以用少量代表性的测试数据取得较好的测试结果。有效等价类：指对于...
有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破， 在第N层以下的楼层落下不会摔破。给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下， 最小化鸡蛋下落的次数。(假设每次摔落时，如果没有摔...
确定鸡蛋最高摔坏楼层的面试题
问题描述：给两个鸡蛋，确定鸡蛋从楼上摔下会摔坏的最高楼层，并且使试摔次数最少。最高100层。最低可摔楼层为2楼，若100层没破，则最高楼层为99。
方法一：二分法
他的最新文章
讲师：王禹华
讲师：宋宝华
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)