［百度面试题］100层楼，球可能会在某一层楼摔坏，问用2个球，最坏情况下几次测试可以找出该楼层

╰+攻爆jí腚メ 2021-11-23 03:12 239阅读 0赞

该题还可以扩展，比如说给更多的球，如3个球，多少次[测试][Link 1]可以找出楼层。

分析如下：

用动态规划解这个问题

设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。

程序如下

**\[cpp\]** [view plain][] [copy][view plain]

1.  /\* 
2.   \* a balls, n floors, want to find the minimum number of floor 
3.   \* where a ball drops will be broken. output the minimum number 
4.   \* of drops 
5.   \* METHOD: dynamic programming 
6.   \* assum the answer is b, that is the number of drops 
7.   \* f(a, b): the maximum number of floors, when a balls and b drops 
8.   \* f(a, b) = 1 + f(a, b - 1) + f(a - 1, b - 1) 
9.   \* obviously, f(a, 1) = 1; f(1, b) = b 
10.  \*/  
11. \#include <stdio.h>  
12. \#include <stdlib.h>  
13. \#include <assert.h>  
14. \#include <string.h>  
15. \#define DEBUG  
16. \#define MAX\_B 64  
17. \#define MAX\_A 16  
18. \#define f(a, b) ff\[a - 1\]\[b - 1\]  
19. static unsigned int a, n;  
20. static unsigned long long ff\[MAX\_A\]\[MAX\_B\];  
21. static void init()  
22. \{  
23.     int i;  
24.     memset(ff, 0, sizeof(ff));  
25.     /\*f(a, 1) = 1\*/  
26.     for (i = 1; i <= MAX\_A; i++)\{  
27.         f(i, 1) = 1;  
28.     \}  
29.     /\*f(1, b) = b + 1\*/  
30.     for (i = 1; i <= MAX\_B; i++)\{  
31.         f(1, i) = i;  
32.     \}  
33. \}  
34. static unsigned long long do\_find\_min\_drops(int i, int j)  
35. \{  
36.     if (f(i, j))  
37.         return f(i, j);  
38.     f(i, j) = do\_find\_min\_drops(i - 1, j - 1) +   
39.         do\_find\_min\_drops(i, j - 1) + 1;  
40.     return f(i, j);  
41. \}  
42. static void do\_print\_drops(int i, int j, unsigned long long min,   
43.         unsigned long long max)  
44. \{  
45.     if (min > max)  
46.         return;  
47.     if (1 == i)\{  
48.         assert(j == max - min + 1);  
49.         for (i = min; i <= max; i++)\{  
50.             printf("%5d", i);  
51.         \}  
52.         printf("/n");  
53.         printf("\*\*\*\*\*\*\*\*\*\*\*\*\*/n");  
54.         return;  
55.     \}  
56.     if (1 == j)\{  
57.         assert(min == max);  
58.         printf("%5lld/n", max);  
59.         printf("\*\*\*\*\*\*\*\*\*\*\*\*\*/n");  
60.         return;  
61.     \}  
62.     printf("%5lld", min + f(i - 1, j - 1));  
63.     do\_print\_drops(i - 1, j - 1, min, min + f(i - 1, j - 1) - 1);  
64.     do\_print\_drops(i, j - 1, min + f(i - 1, j - 1) + 1, max);  
65. \}  
66. static void print\_drops(int ans)  
67. \{  
68.     do\_print\_drops(a, ans, 2, n);/\*\[2..n\]\*/   
69. \}  
70. static void find\_min\_drops()  
71. \{  
72.     /\*NOTE: number of floors are \[1, n\]\*/  
73.     int i, j, m;          
74.     int ans;  
75. \#if 0//def DEBUG  
76.     for (i = 2; i <= MAX\_A; i++)\{  
77.         for (j = 2; j <= MAX\_B; j++)\{  
78.             printf("f(%d, %d) = %lld/n", i, j, do\_find\_min\_drops(i, j));  
79.         \}  
80.         printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/n");  
81.     \}  
82. \#endif  
83.     i = 1;   
84.     j = MAX\_B;  
85.     while (i <= j)\{  
86.         m = (i + j) / 2;  
87.         if (do\_find\_min\_drops(a, m) + 1 < n)  
88.         /\* 
89.          \* why +1? because the 1st floor need not to test 
90.          \*/  
91.             i = m + 1;  
92.         else  
93.             j = m - 1;  
94.     \}  
95.     ans = i;  
96.     if (ans > MAX\_B)\{  
97.         printf("the number of the maximum drops(MAX\_B = %d) is too small/n", MAX\_B);  
98.         printf("maximum floors "   
99.                 "can be tested is f(%d, %d) + 1 = %lld + 1. STOP/n", a, MAX\_B, f(a, MAX\_B));  
100.         exit(0);  
101.     \}  
102.     printf("the minimum drops: %d/n", ans);  
103.     print\_drops(ans);  
104. \#ifdef DEBUG  
105.     for (i = 1; i <= a; i++)\{  
106.         for (j = 1; j <= ans; j++)\{  
107.             printf("f(%d, %d) = %lld/n", i, j, f(i, j));  
108.         \}  
109.         printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/n");  
110.     \}  
111. \#endif  
112. \}  
113. int main(int argc, char \*\*argv)  
114. \{  
115.     if (3 != argc)\{  
116.         fprintf(stderr, "usage: %s a n/n", argv\[0\]);  
117.         exit(-1);  
118.     \}  
119.       
120.     a = atoi(argv\[1\]);  
121.     n = atoi(argv\[2\]);  
122.     printf("a = %d/tn = %d/n", a, n);  
123.     assert(a > 0 && a < MAX\_A && n > 0);  
124.     init();  
125.     find\_min\_drops(); /\*drops: 1\*/  
126.     return 0;  
127. \}

这里，我采用递归的方法打出了测试过程，解释如下：

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

\*\*\*\*\*\*\*\*\*\*\*\*\*

104

\*\*\*\*\*\*\*\*\*\*\*\*\*

3）对于更多球的情况，输出的测试方法分析起来有些麻烦，但是上面的动态规划法求出的结果就容易理解了，且是保证正确的。

[Link 1]: http://lib.csdn.net/base/softwaretest
[view plain]: http://blog.csdn.net/lzshlzsh/article/details/5951447#

［百度面试题］100层楼，球可能会在某一层楼摔坏，问用2个球，最坏情况下几次测试可以找出该楼层

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关什么情况下不能使用最坏情况评估算法的复杂度？

相关使用天平找出12球中的问题球

相关（找最值问题）一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼

相关情景题：0~100层楼，有两个球。一个任意的x，在0~x之间球扔下不会碎，在x~100之间求扔下会碎。找出这个x

相关实验楼 - Python Numpy 100题实验（一）

相关 100层楼扔鸡蛋，最快速度找出，哪层是鸡蛋碎的临界点

相关几种排序在最坏和最好情况下的时间复杂度

相关找球号(一）

相关［百度面试题］100层楼，球可能会在某一层楼摔坏，问用2个球，最坏情况下几次测试可以找出该楼层

相关最坏情况比较次数