0

我有一个问题，我完全不知道如何设置重复。

手表制造商希望找出防水的整数值是否在 0 到 n 的范围内。手表漏水防水为0，在n米深度手表不漏水。耐水性定义为n。

为了测试深度 k 的防水性，水肺潜水员在 k 米处潜水，并在该深度的水下停留一小时。如果手表泄漏，则将其丢弃。如果没有泄漏，可以在另一个实验中重复使用。

在最坏的情况下有多少手表会漏水？（这里最坏的情况是指损坏手表的最大数量）？

给出的内容：描述最坏的情况，然后给出损坏手表数量的递归关系。假设通过以下公式为从下到上的子问题选择中点：mid = floor[(lower+upper)/2] where lower = 1, and upper = n 对于第一个子问题。

所以我从中得到的是mid = floor[(1+n)/2] ，但我不确定如何提出适用于任何 n 值的递归。

有人可以指导我做什么/如何开始吗？我将不胜感激任何人的帮助。

多谢你们。

4

1 回答 1

1

如果你想尽量减少泄露的手表总数，那就是一只。您可以按顺序测试 k = 0、k = 1 等，直到手表泄漏。在这种情况下，测试次数的复杂度为 O(m)，其中 m 是手表的防水性。

如果你想最小化测试的总数，那么 IMO 就是一个二分搜索问题。您正在寻找手表泄漏的最小 k。

从中间点开始。

如果手表漏水，则其阻力小于中点。

Hence new mid-point = (lower + mid-point)/2.

如果不泄漏，则其阻力大于中点。

Hence new mid-point = (mid-point + upper)/2.

在最坏的情况下，所有经过测试的手表都会泄漏。这就是算法的复杂度O(logn)。

如果您对可以泄漏的最大手表数量或可以进行的最大试验次数有限制，那么您应该按照@Dukeling 显示的链接获取合适的动态编程公式。

于 2013-11-12T07:48:02.817 回答