黑马程序员技术交流社区

标题: 扔鸡蛋面试问题 [打印本页]

作者: 永远的EOF 时间: 2015-8-17 00:08
标题: 扔鸡蛋面试问题

[size=14.3999996185303px]现在只有两个鸡蛋，而算法必须在各种合法输入下都是可行的，就是说要能找出这一层来，你得假设你的运气最差，这就意味着，我求解的是[size=14.3999996185303px]在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值，而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋，这就意味着，我只能从第一层开始老老实实地一层一层往上试，不能越层；而我的运气非常非常差，于是我这样试验的结果就是一直试验到最高一层鸡蛋依然没破，试验的次数就等于楼层数N。

[size=14.3999996185303px][size=14.3999996185303px]动态规划法求解

[size=14.3999996185303px]现在，我有两枚鸡蛋，第一枚鸡蛋从哪一层楼开始扔就显得至关重要了。如果第一枚鸡蛋碎了，那就回到刚说的只有一枚鸡蛋的问题了。我相信很多人立即映射到脑子里的词是“二分法”，也就是说，第一枚鸡蛋从N/2开始扔，如果碎了，扔的楼层数就是N/2（注意取整）；如果没碎，剩下N/2楼层里继续用二分法。可以预计，如果没碎的情况，扔鸡蛋的总次数要小于N/2。也就意味着，还有潜力可挖，如果不用二分法，让扔第一枚鸡蛋的楼层数为x，它小于N/2；同时如果第一枚鸡蛋没碎，接下去的策略，在运气最差的情况下仍然让扔的次数等于x，就最经济了。

[size=14.3999996185303px]最常规的解法是动态规划。可以用动态规划法求解的问题必须满足这样的条件，分割成的子问题是最优解的时候，原问题也是最优解。显然这个问题满足这一点：假设扔的总次数为f(x)，在第一次扔碎了的情况下，接下去只能一层一层试验，最多从第1层到第x-1层需要试验x-1次，加上扔第一个鸡蛋那一次，总的次数就是(x-1)+1=x；在第一次没碎的情况下，就相当于一个新的相似子问题：在N-x层中寻找新的扔鸡蛋次数f(N-x)，因此总次数就是f(N-x)+1。那么：

f(x)=max(x, f(N-x)+1)

[size=14.3999996185303px]同时，递归求解的出口是：当x=1，f(x)=1。所以，算法大致如下：

[size=14.3999996185303px][size=1em]

[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em]29

[size=1em]30

[size=1em]31

[size=1em]32

[size=1em]33

[size=1em][size=1em]// times表示N取值为i的时候，需要扔多少次
[size=1em]private static int[] times;

[size=1em]public static int dropEgg(int N) {
[size=1em] // 初始化数组
[size=1em] times = new int[N + 1];
[size=1em] return dp(N);
[size=1em]}

[size=1em]private static int dp(int N) {
[size=1em] // 两层楼或一层楼就没有计算的必要了
[size=1em] if (1 == N)
[size=1em]       return 1;
[size=1em] else if (2 == N)
[size=1em]       return 2;

[size=1em] for (int x = 2; x < N; x++) {
[size=1em]       int max = maxTimes(N, x);
[size=1em]       if (0 == times[N] || times[N] > max)
[size=1em]          times[N] = max;
[size=1em] }

[size=1em] return times[N];
[size=1em]}

[size=1em]// 碎和不碎的次数最大值
[size=1em]private static int maxTimes(int N, int x) {
[size=1em] int sum = dp(N - x) + 1;
[size=1em] if (x < sum)
[size=1em]       return sum;
[size=1em] else
[size=1em]       return x;
[size=1em]}

[size=14.3999996185303px][size=14.3999996185303px]“两个鸡蛋”到“m个鸡蛋”

[size=14.3999996185303px]现在把问题扩展一下，由两个鸡蛋扩展到m个鸡蛋，times数组第一维表示最多可以扔几次，第二维表示扔第几次：

[size=14.3999996185303px][size=1em]

[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em][size=1em]public static int dropEgg(int N, int m) {
[size=1em] // 初始化数组
[size=1em] times = new int[m + 1][N + 1];
[size=1em] return dp(N, m);
[size=1em]}

[size=1em]private static int dp(int N, int m) {
[size=1em] if (1 == m || 1 == N || 2 == N)
[size=1em]       return N;

[size=1em] for (int time = 2; time <= m; time++)
[size=1em]       for (int x = 2; x < N; x++) {
[size=1em]          int max = maxTimes(N, x, time);
[size=1em]          if (0 == times[time][N] || times[time][N] > max)
[size=1em]             times[time][N] = max;
[size=1em]       }

[size=1em] return times[m][N];
[size=1em]}

[size=1em]// 碎和不碎的次数最大值
[size=1em]private static int maxTimes(int N, int x, int m) {
[size=1em] int sum = dp(N - x, m) + 1;
[size=1em] if (x < sum)
[size=1em]       return sum;
[size=1em] else
[size=1em]       return x;
[size=1em]}

作者: 风华正茂 时间: 2015-8-17 12:45
收藏一下

作者: pengbeilin 时间: 2015-8-17 14:26
- - 完全看不懂不知道楼主在说什么

作者: kevin986745 时间: 2015-8-17 14:45
看不明白想表达什么意思

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2