再谈大楼扔鸡蛋的问题
source link: https://www.raychase.net/1374
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
这道题是说，100 层楼，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法，因为只想记录一下思路和讨论过程，写得很简略。现在，我想重新整理一下这个问题，再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述，把这个问题的前后说清楚。
现在只有两个鸡蛋，而算法必须在各种合法输入下都是可行的，就是说要能找出这一层来，你得假设你的运气最差，这就意味着，我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值，而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋，这就意味着，我只能从第一层开始老老实实地一层一层往上试，不能越层；而我的运气非常非常差，于是我这样试验的结果就是一直试验到最高一层鸡蛋依然没破，试验的次数就等于楼层数 N。
动态规划法求解
现在，我有两枚鸡蛋，第一枚鸡蛋从哪一层楼开始扔就显得至关重要了。如果第一枚鸡蛋碎了，那就回到刚说的只有一枚鸡蛋的问题了。我相信很多人立即映射到脑子里的词是 “二分法”，也就是说，第一枚鸡蛋从 N/2 开始扔，如果碎了，扔的楼层数就是 N/2（注意取整）；如果没碎，剩下 N/2 楼层里继续用二分法。可以预计，如果没碎的情况，扔鸡蛋的总次数要小于 N/2。也就意味着，还有潜力可挖，如果不用二分法，让扔第一枚鸡蛋的楼层数为 x，它小于 N/2；同时如果第一枚鸡蛋没碎，接下去的策略，在运气最差的情况下仍然让扔的次数等于 x，就最经济了。
最常规的解法是动态规划。可以用动态规划法求解的问题必须满足这样的条件，分割成的子问题是最优解的时候，原问题也是最优解。显然这个问题满足这一点：假设扔的总次数为 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)
同时，递归求解的出口是：当 x=1，f(x)=1。所以，算法大致如下：
// times[i] 表示 N 取值为 i 的时候，需要扔多少次private static int[] times;public static int dropEgg(int N) {// 初始化数组times = new int[N + 1];return dp(N);}private static int dp(int N) {// 两层楼或一层楼就没有计算的必要了if (1 == N)return 1;else if (2 == N)return 2;for (int x = 2; x < N; x++) {int max = maxTimes(N, x);if (0 == times[N] || times[N] > max)times[N] = max;}return times[N];}// 碎和不碎的次数最大值private static int maxTimes(int N, int x) {int sum = dp(N - x) + 1;if (x < sum)return sum;elsereturn x;}“两个鸡蛋” 到 “m 个鸡蛋”
现在把问题扩展一下，由两个鸡蛋扩展到 m 个鸡蛋，times 数组第一维表示最多可以扔几次，第二维表示扔第几次：
public static int dropEgg(int N, int m) {// 初始化数组times = new int[m + 1][N + 1];return dp(N, m);}private static int dp(int N, int m) {if (1 == m || 1 == N || 2 == N)return N;for (int time = 2; time <= m; time++)for (int x = 2; x < N; x++) {int max = maxTimes(N, x, time);if (0 == times[time][N] || times[time][N] > max)times[time][N] = max;}return times[m][N];}// 碎和不碎的次数最大值private static int maxTimes(int N, int x, int m) {int sum = dp(N - x, m) + 1;if (x < sum)return sum;elsereturn x;}寻找规律
还是回到两个鸡蛋，随着 N 的值改变，可以发现 x 呈现这样的变化：
N=1, x=1
N=2, x=2
N=3, x=2
N=4, x=3
N=5, x=3
N=6, x=3
N=7, x=4
N=8, x=4
N=9, x=4
N=10, x=4
N=11, x=5
N=12, x=5
N=13, x=5
N=14, x=5
N=15, x=5
N=16, x=6
N=17, x=6
N=18, x=6
N=19, x=6
N=20, x=6
N=21, x=6
……
换言之，x=1 的有 1 项，x=2 的有 2 项，x=3 的有 3 项……网上最多的问法是当 N=100 的时候，x 是多少，根据这个规律：
(1+x)*x/2>=100
得知 x 的最小值是 14。
下面来证明一下这个猜想：
因为当扔鸡蛋的最小次数为 x 的时候，第一次从 x 层开始扔，如果碎了，那么接下去就要扔 x-1 次；如果没碎，接下去就变成了扔鸡蛋最小次数为 x-1 的子问题了，此时再扔的楼层数变成了 x+(x-1)，在这种情况下碎和不碎两种情况下需要再扔的次数是相等的，已经是最经济的扔法了，继续之，可以得到，扔鸡蛋最小次数的时候，最高可以检测到的楼层数为：
x+(x-1)+(x-2)+……+1
正好是一个等差数列求和的公式。
如果你还没有理解，我们可以换一个有趣的解释。现在把思路从 “给定 N 层楼，问最少需要扔多少次” 变化到 “给定 x 次最多扔鸡蛋的次数，最多可以在几层的楼上确定鸡蛋破碎的临界层”。
第一次我们从 x 层开始扔，如果碎了，那只能老老实实一层一层试验剩下的 1~(x-1) 层，那么这种情况下可以检测 x 层高的楼；假如说没碎，那么剩下 x-1 次可以试验，变成了一个接着要从 (x-1) 层开始扔的子问题了，这个时候可以检测 (x-1) 层高的楼……依此类推，也得到了最终累计可以检测的楼高，正是这个等差数列求和公式：
x+(x-1)+(x-2)+……+1
这也是为什么，我们可以从网上找到的扔鸡蛋问题，好多都是 N 等于 15、21、28、36 这样的数，这正好等于这个等差数列和。
现在把问题稍稍转变一下，把鸡蛋数量的限制去掉，再把求爬楼梯的限制加上，不妨再来求解：
如果鸡蛋数量无限，但是假如说扔一次鸡蛋需要耗费力气 a，每爬一层楼（无论向上还是向下）需要耗费力气 b，现在用怎样的扔鸡蛋策略，可以让耗费的总力气量最小？
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK