Найти алгоритм, чтобы найти похожие пицц из набора N пицц

Question

Я имею эту проблему домашнее задание:

Вам дают пачку п коробок для пиццы одного и того же размера, каждый из которых содержит 1 пиццы. Пицца в коробках сортируется путем увеличения диаметра; диаметры не более 40 см.

1a. Докажите, что в стеке должны быть две пиццы , диаметр которых не может превышать 40/(n -1) см.
1b. Дайте алгоритм для определения такой пары. Единственный способ, которым ваш алгоритм может узнать диаметр пиццы, - это открыть коробку и измерить ее. Мы будем называть эту операцию мера (i), где i - номер открываемого ящика. Ваш алгоритм должен открывать как можно меньше ящиков для пиццы. Для полного кредита он должен открыть O (журнал   n) коробки в наихудшем случае.

Для 1a, я не знаю, как доказать это математически. Для 1b я понимаю, что мне придется использовать двоичный поиск, но я точно не знаю, как это реализовать.

Как мне решить эту проблему? Я был бы признателен за любые намеки или любые предложения по его приближению.

Answer 1

Для 1a можно использовать индукцию:

В основном: Предположим, п = 2 (по крайней мере, две пиццы, в противном случае нет никакой разницы) и максимизировать разницу. Пусть одна из пицц имеет диаметр 40, а другой x . Тогда у нас есть 40-x < 40/(2-1), что верно.

Индукционный шаг п => п + 1 и вы можете попробовать оттуда ...