鸡蛋下降
测试
有关……
鸡蛋下降指一类问题,其中重要的是找到正确的响应,而不超过某些故障状态的(低)数量。在一个玩具的例子中,有一个塔
2鸡蛋,
1 00地板
假设你有两个鸡蛋,你想确定在一栋100层楼的大楼里,你可以从哪一层扔下一个鸡蛋而不破。你需要确定在最坏情况下找到临界下限所需的最小尝试次数,同时使用最佳策略。
- 如果鸡蛋在某一层没有破裂,那么它在下一层也不会破裂。
- 如果鸡蛋在某一层破碎,那么它将在以上任何一层破碎。
- 鸡蛋可能会在一楼破掉。
- 鸡蛋可能不会在最后一层打破。
有人会想用二分搜索来解决这个问题,但实际上这不是最好的策略,你会明白为什么。试着自己解决这个问题,回答这个问题,或者继续读下去,看看这个问题的详细解释。
使用二分搜索,你必须从
但如果鸡蛋在你第一次尝试的时候就破了怎么办,也就是说
记住,问题是确定临界下限
从
- 如果第一个鸡蛋在14层碎了怎么办?
如果第一个鸡蛋在 1 4th一层,然后我们应该检查第一层,然后是第二层,直到1 3.th地板上。这样做,总尝试次数将是14。- 如果它不坏怎么办?
那么你应该检查 2 7th地板上。为什么?因为如果它坏了,你就得检查所有楼层1 5th直到2 6th1层(13层),这使得总尝试次数保持在14次( 第一次尝试1 4th二楼2 7th地板上,还有剩下的十二滴1 5th直到2 6th地板上) . - 如果它不坏怎么办?
如果它没坏,你就得检查一下
使用相同的推理,您应该检查
不知道如果这张桌子上有3个鸡蛋会是什么样子!!
使用其他策略,如二分搜索,在某些情况下需要更少的尝试(就像我们的第一个例子),但在最坏的情况下需要大量的尝试
因此,我们可以得出结论,使用另一种策略,在最坏的情况下,你需要超过14次尝试。
2鸡蛋,
k 地板
现在让我们试着找出有两个鸡蛋和一个建筑的情况下的解
开始这个问题的一个好方法是问“我们能把所有的地板都铺上吗?
假设在最佳策略中,最坏情况下的落子数是 你知道我们在做什么吗?基于滴数总是 我们可以找到这个问题的解析解:
假设在使用最佳策略时,在最坏情况下的最小尝试次数为
x+(x−1)+(x−2)+(x−3.)+⋯+2+1=2x(x+1) 地板。
如果我们能覆盖
2x(x+1)≥k. 因此,
x2+x−2k=0⟹x=2−1+1+8k
. 但
x=⌈2−1+1+8k
⌉. 在第一个例子中,
.在我们的尝试中,我们会把鸡蛋扔在
N鸡蛋,
k 地板
假设你有
递归解:
这种解决方案更直接,可以轻松实现,但也是最慢的解决方案。在编程竞赛中使用这种解决方案是不可取的,因为它的性能很差。 动态规划方案:
此解决方案与前一解决方案类似,但速度更快,可用于解决中等或较小值的问题 k 而且N .结合了二分搜索和递归的解决方案:
这是更快的一种,一旦理解了策略,就很容易实现。
递归解决方案
想象一下下面的情况:你有
如果鸡蛋破了:
问题简化为 n −1鸡蛋和我 −1剩余的地板。如果没有断裂:
问题简化为 n 鸡蛋和h −我剩余的地板。这一点很重要。我们想要测试的地板并不重要;事实上,剩下的楼层数才是最重要的。例如,测试1到20层之间的楼层(包括1和20层)将需要相同数量的下降来测试21到40层,或81到100层。在这三种情况下,我们都测试了20层。
现在我们可以定义一个函数 我们可以把上面的发现整理成下面的递归来确定 鸡蛋掉落谜题的递归:
W[n,h]=1+最小值(马克斯(W(n−1,我−1),W(n,h−我)))
(注意:
基本情况如下:
因为我们需要
因为我们只需要一滴就可以测试一层楼,不管鸡蛋的数量,
因为0层不需要水滴,
文中给出了该算法的伪代码
12 3 4 5 6 7 8 9 10 11 12 13 14 |
|
使用递归解决方案的c++代码:
12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
|
DP的解决方案
之前的解决方案非常慢,同一个函数被调用了不止一次,这是不必要的。然而,由于它的子问题是重叠的,并且由于它的最优子结构性质(我们可以利用子问题的最优解来找到问题的解),我们可以通过动态规划来解决问题。
我们可以避免重新计算相同的子问题<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/subroutines/">记忆一个>这个函数
下面是伪代码:
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
c++代码:
12 34 56 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
|