查找算法从一组N个比萨饼

-3

我有这样的功课问题找到类似的比萨饼：查找算法从一组N个比萨饼

您将得到同样大小的ň比萨饼盒，每个包含1个比萨饼堆栈。箱子里的比萨饼按直径增加分类;直径都是至多40厘米。

1a上。证明有必须存在两种比萨饼在堆栈，其直径由至多40 /（Ñ -1）厘米不同。
1b。给出一个发现这样一对的算法。你的算法可以学习比萨饼的直径的唯一方法是打开盒子并测量它。我们将调用该操作尺寸（i），其中i是正在打开的盒子的编号。你的算法应该尽可能少的披萨盒。对于完整的信用，它应该打开Ø（日志 ñ）盒在最坏的情况下。

对于1a，我不知道如何在数学上证明。对于1b，我知道我将不得不使用二分搜索，但我不知道如何实现它。

我如何去了解这个问题呢？我会欣赏任何提示，或任何建议如何处理它。

来源

2017-01-21 stupid_kid

是否已经阅读了讲义？（或参加他们） –

是的，我参加了讲座。没有讨论过这个问题。教授已经讨论了时间复杂度和排序算法，但没有教会我们如何解决这类问题。 –

当我去大学时，我参加了讲座。然后我花了2/3小时阅读各个主题。现在是否有所不同 - 你无法访问图书馆（我没有互联网的奢侈品）。 –

对于1a中可以使用感应：

基本上：假设n = 2的（至少两个比萨饼，否则没有区别）和最大化差。让其中一个比萨饼的直径为40，另一个比例为x然后我们有40-x < 40 /（2-1）这是真的。

感应步骤N => N + 1 ，你可以从那里试试...

来源

2017-01-21 23:13:34

我同意你的意见。但考虑另一种情况。假设n = 5，并且我有直径1,2,5,5,40的比萨饼。所以从我所了解的情况来看，在这种情况下差异可能最大。但显然1和40之间的差异是39.那么公式如何成立。感谢您的回复 –

您并未寻求最大的差异。你正在寻找至少两个满足条件。 –

这非常有帮助！谢谢！！！ –

查找算法从一组N个比萨饼

回答

相关问题