Egg dropping puzzle

Love The Way You Lie 2022-08-04 05:17 183阅读 0赞

问题：

有一个100层高的楼，如果一个鸡蛋从n层掉下来或者n层以上，鸡蛋就会碎掉。已知，现在有两个鸡蛋，找到满足条件的n，使在最坏情况下，丢鸡蛋的次数最少。原题链接可以转到wiki：[点击打开链接][Link 1]

很明显，不管egg1怎么丢，egg2肯定得线性得丢。

我们假设egg1每次丢10层，即按10f, 20f, 30f, 40f, 50f, 60f, 70f, 80f, 90f, 100f。

则，如果egg1在10f碎了，我们就不得不用egg2从1f按线性试了，此时最坏的情况是n=9，则总共丢了10次。

如果egg1在100f碎了，我们就不得不用egg2从90f按线性试了，此时最坏的情况是n=99，则总共丢了19次。

但是题目的要求是在最坏情况下丢的鸡蛋次数最少。也就是我们需要在最坏和最好做一下load balance。从上面的举例我们可以发现，越靠后试的次数越多，这是我们对每次丢的层数做了一个等价划分，每次多的都是egg1丢的次数，此时我们只能减少egg2丢的次数，已达到丢的总次数是相同的，很显然，每当egg1多丢一次的时候，egg2就少丢一次。

比如，假设第一次从x层丢下，如果此时n=x-1，显然我们需要试1+(x-1) = x次。

我们现有要分析第二次从那一层丢下，因为egg1比第一次多丢了一次，所以egg2在最坏情况下应该少丢一次，则第二次丢的楼层数是x-1

以此递推则，x + (x-1) + (x-2) + ...+ 1 >= 100，解之得x = 14;

则此时的顺序为：

14f, 27f, 39f, 50f, 60f, 69f, 77f, 84f, 90f, 95f, 99f, 100f

可以显式的试一下，最坏情况是不会超过14的，或者基本都是14次。

把问题再次扩展，如果是n个鸡蛋，k层楼？wiki中有关于这个解答，用动态规划。[Wiki Egg Dropping Puzzle][Link 1]，其状态转移方程为：

W(n,k) = 1 + min\{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k \} 并且初始化条件W(n,1)=1, W(1,k)=k

解释下这个状态转移方程，当我们在x层做实验的时候，我们有两种可能：

1）鸡蛋碎了，则我们就需要递归的处理：x-1 层，n-1个鸡蛋，也就是W(n-1, x-1)

2) 鸡蛋没碎，则我们局需要递归额处理：k-x 层，n个鸡蛋，也就是W(n, k-x)

因为题目要求是在最坏的情况下，所以求上面两个的max。但是要求最坏情况下的最小值，所以需要求x在1到k直接的最小值。

接下来，动态规划的代码就比较容易写了，如下是我自己写的一个：

public int eggDrop(int n, int m) {//n eggs, m floors.
    		int[][] dp = new int[n+1][m+1];
    		
    		for (int i = 0; i < dp.length; i++) {
    			dp[i][1] = 1;
    		}
    		
    		for (int i = 0; i < dp[0].length; i++) {
    			dp[1][i] = i;
    		}
    		
    		for (int i = 2; i < dp.length; i++) {
    			for (int j = 2; j < dp[i].length; j++) {
    				dp[i][j] = Integer.MAX_VALUE;
    				for (int k = 1; k <= j; k++) {
    					int ret = 1 + Math.max(dp[i-1][k-1], dp[i][j-k]);
    					if (ret < dp[i][j]) {
    						dp[i][j] = ret;
    					}
    				}
    			}
    		}
    		return dp[n][m];
    	}

用计算机解法问题的好处就是我们可以试，我们可以把很多情况罗列出来，然后取最优解！

[Link 1]: https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

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

相关阅读

相关 UVA 227 Puzzle

1. \include<cstdio> 2. \include<string.h> 3. char ch\[6\]\[6\]; 4. char common\[1010

古城微笑少年丶/ 2024年02月17日 18:44/ 0 赞/ 83 阅读

相关 puzzling(puzzling和puzzled的区别)

puzzlingB)difficultC)terrifyingD? puzzling 使为难的; 费解的; 令人迷惑的, 莫名其妙的 difficult 难的, 困难的

灰太狼/ 2023年09月26日 14:42/ 0 赞/ 141 阅读

相关 puzzles(puzzles in geography课件)

搜狗问问-搜狗旗下最大互动问答社区 ![puzzles][] 搜狗问问-搜狗旗下最大互动问答社区 [puzzles]: https://img2.baidu.c

深藏阁楼爱情的钟/ 2023年09月26日 14:42/ 0 赞/ 65 阅读

相关 puzzle拼图(puzzle拼图9级答案)

3dpuzzle拼图怎么拼装坦克每一个小模块上有编号，字很小，注意看，把中轴立起，从1开始挨个往中间拼，得一半后，把中轴取出来，弄另一半，然后又取中轴，两个合拢后插入中

本是古典何须时尚/ 2023年09月26日 14:42/ 0 赞/ 181 阅读

相关 egg(三):egg中部署前端项目，egg+vue/egg+react

前言：来继续探究egg的知识，这里来分析下，egg来作为一个服务端来使用，跟nginx一样，egg里面也是支持部署前端的代码的。目录：实现效果：egg服

蔚落/ 2022年09月13日 15:20/ 0 赞/ 751 阅读

相关 Egg dropping puzzle

问题：有一个100层高的楼，如果一个鸡蛋从n层掉下来或者n层以上，鸡蛋就会碎掉。已知，现在有两个鸡蛋，找到满足条件的n，使在最坏情况下，丢鸡蛋的次数最少。原题链接可以转到w

Love The Way You Lie/ 2022年08月04日 05:17/ 0 赞/ 184 阅读

相关 The puzzle of eggs and floors

The puzzle of eggs and floors 俩崩溃的鸡蛋…… 题目：有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破，在第N层以下的楼

灰太狼/ 2022年07月26日 06:20/ 0 赞/ 161 阅读

相关 Puzzle UVA - 227

Puzzle UVA - 227 题目传送： [https://uva.onlinejudge.org/index.php?option=com\_onlinejud

快来打我*/ 2022年06月10日 10:51/ 0 赞/ 190 阅读

相关动态规划法（六）鸡蛋掉落问题（一）（egg dropping problem）

继续讲故事~~ 这天，丁丁正走在路上，欣赏着路边迷人的城市风景，突然发现前面的大楼前围了一波吃瓜群众。他好奇地凑上前去，想一探究竟，看看到底发生了什么事情。

﹏ヽ暗。殇╰゛Y/ 2022年05月23日 08:11/ 0 赞/ 222 阅读

相关 [java puzzles]puzzle:Oddity

The following method purports to determine whether its sole argument is an odd number.Do

绝地灬酷狼/ 2022年04月16日 01:10/ 0 赞/ 147 阅读