Xirax
дневник • Профиль
01:45 21-04-2006 Математическое
На интервью задали задачку... такую... эдакую

Есть дом, в нем n этажей
Есть два кокоса
Нужно вычислить прочность кокоса в этажах (т.е. с какого наименьшего этажа надо бросить кокос чтоб он разбился).
Если кокос разбился, его больше юзать нельзя.

Минимальное число бросков?
Комментарии:
Darksoul
дневник • Профиль
02:11 21-04-2006
Два?
Xirax
дневник • Профиль
02:16 21-04-2006
Два.

Если один кокос - то в среднем n/2 бросков (начинаем снизу, добавляем по одному этажу пока не разобьется)
Если бесконечно кокосов - то log2(n) бросков (бинарный поиск)
Darksoul
дневник • Профиль
02:28 21-04-2006
хм...
Начинаем с n/2. Если бьется - то идем снизу попорядку. Если нет, то в 3/4. и т.п.
Мне кажется.
Xirax
дневник • Профиль
04:24 21-04-2006
Неа
Anafay
Профиль
06:49 21-04-2006
Поскольку кокосов 2, то начинать надо не с n/2, а с n/3.
Разбился - вторым кокосом проходим с 1 до n/3.
Не разбился - пробуем n*2/3. Если разбился - вторым кокосом проходим интервал n/3 - n*2/3, если целый - то проверяем n*2/3 - n.

Грубо говоря, второй кокос - сокращение числа попыток втрое по сравнению с одним кокосом. Может, что-то еще придумать можно...
Xirax
дневник • Профиль
09:55 21-04-2006
Anafay
Похоже на правду. Я ответа не знаю. Интервьюер сказал что для 100 этажей он добился 9-10 бросков в среднем.

Это учитывая равномерное распределение вероятности разбивания: т.е. P(минимальный этаж = 1) = P(минимальный этаж = k) = P(минимальный этаж = n)
Anafay
Профиль
10:01 21-04-2006
Xirax
Так надо какую оценку - минимальное среднее количество бросков или минимальное в наихудшем случае?
Xirax
дневник • Профиль
10:22 21-04-2006
Anafay
Среднее
Xirax
дневник • Профиль
07:51 22-04-2006
получил (n+1-2*sqrt(n))/(n-1)