©2016-2024 Matools All rights reserved,
粤ICP备17059708号
扔鸡蛋-思路解析
无意中看到了这个扔鸡蛋的问题，以博主的智商最多想到了分成10层来扔，搜了一下最优答案，感觉回答都不是很清晰，特此整理下思路。希望能给大家一份简明易懂的解题思路
问题：
有一栋楼，共100层。
定义：鸡蛋在第n层楼扔下，不会碎，第n+1层扔下，会碎，那么第n层就叫临界楼层
你手中有两个鸡蛋（默认理想状态：两个鸡蛋完全相同），如何优化尝试策略，使得使用最少次数，测出临界楼层
即，使用此策略，最差也可以在多少次以内测出临界楼层
（ps:假定鸡蛋一定会在某层楼下落后碎掉）
思路：
注意：手中只有俩鸡蛋，必须要保证全碎之前测试出临界楼层
1 为了不让鸡蛋碎掉，我们从一楼开始测试，这样只需要一个鸡蛋，当到达临界楼层的上一层n+1时，我们可以得出，n层是临界楼层，这是最原始的方法，遍历。
这种策略最糟糕的情况会是测试到100楼鸡蛋才会碎，测试次数是100次，临界楼层是99楼。最好的情况是测试到2楼鸡蛋就碎了，测试次数是2次，临界楼层是1层。
写博不易，给个赞鼓励一下吧
2 我们手中有俩鸡蛋，为了充分利用条件，我们可以利用第一个鸡蛋来缩小范围。
我们可以先跑到50楼去扔，没碎的话，我们再去75楼去扔···直到第一个鸡蛋碎掉。
如果我们从50楼扔，没碎，说明50楼以下是安全的，50楼以上还有50楼，那我们再去上面的50楼的一半——75楼去扔，在75楼碎了，说明临界楼层在50层~74层之间，我们就利用第二个鸡蛋，遍历51层到74层。这是运用
二分法。
这种策略最糟糕的情况会是50层鸡蛋就碎了，49层是临界楼层，测试次数是1+49次，临界楼层是99楼。最好的情况是1楼是临界楼层，测试次数是1+2次。
3
还有没有更好的办法呢？我们手中有两个鸡蛋，尝试使每个鸡蛋的测试任务大致相当，即给100开个平方根，第一个鸡蛋只测试整十楼层，第二个鸡蛋测试两个整十楼层之间的楼层。我们可以先测10楼，20楼，30楼···，直到第一个鸡蛋碎掉。
如果我们测到30楼，第一个鸡蛋碎了，那我们就用第二个鸡蛋遍历测试21~29楼。
这种策略最糟糕的情况会是99层是临界楼层，测试次数是10+9次。最好的情况是1楼是临界楼层，测试次数是1+2次。
点关注不迷路
4 这个时候我们产生了疑问，第三种方法是最好的策略吗？我们怎么验证呢？
验证这种事情，我们肯定要借助数学工具了。
首先，我们我们假定存在一种最优策略，最多n次测试就能找到临界楼层
那么，最糟糕的状况会是哪一种呢？
从上面的分析可以看出，测试次数分为两部分
第一颗鸡蛋的测试次数x，用来缩小范围
第二颗鸡蛋用来在小范围内查找临界楼层y
即X+y=n
那么当测试次数固定为n时，每当x增加1，y则减少1
即，每当第一颗鸡蛋测试一次，那么所留给第二颗鸡蛋探查的范围就应该减少1
{此处内容用于帮助各位i理解：如果n=10,那么第一次探查了20楼，使用了一次机会，如果碎了，确定的范围是1~19，那么，第二颗鸡蛋需要使用10-1次机会去探查19层，在最糟糕的情形下显然无法完成。
显然当n=10时，第一次探查为10楼显然更合适，确定下来的范围是1~9，第二颗鸡蛋使用10-1次探查9层楼，最糟糕的情形下也能满足。
如果探查10楼后鸡蛋没碎，而在第二次探查时碎了呢？我们第二次探查应该把范围再缩小1，如果第一个鸡蛋多探查一次，那么留给第二颗鸡蛋的探查机会就少一次，我们要保证在最糟糕的情形下也能探查到，所以留给第二颗鸡蛋的探查范围应该与其探查机会相等。即第一颗鸡蛋的第二次机会应该探查第19层，确定下来的范围需要探查的范围是11~18，第二颗鸡蛋的剩余探查次数刚好为10-2，匹配成功
·····
根据以上分析，我们可以发现，每一次的探查范围都减一，即n-1,n-2,n-3,....2,1,0
最后我们的探查范围会缩小到0
那么我们把这些探查范围加起来，再加上n就是我们的探查总范围}
即n+(n-1)+(n-2)+······+3+2+1+0=100
解的n刚好为正整数14，即使用此策略最多探查14次即可在100楼中找到临界楼层
另外，当探查总范围发生改变时，解的n可能为小数，显然，探查次数只能为整数且n越小探查总范围越小，
即n应向上取整
热门工具 换一换