21-04-2006 01:45 Математическое
На интервью задали задачку... такую... эдакую
Есть дом, в нем n этажей
Есть два кокоса
Нужно вычислить прочность кокоса в этажах (т.е. с какого наименьшего этажа надо бросить кокос чтоб он разбился).
Если кокос разбился, его больше юзать нельзя.
Минимальное число бросков?
Есть дом, в нем n этажей
Есть два кокоса
Нужно вычислить прочность кокоса в этажах (т.е. с какого наименьшего этажа надо бросить кокос чтоб он разбился).
Если кокос разбился, его больше юзать нельзя.
Минимальное число бросков?
Комментарии:
Darksoul
21-04-2006 02:11
Дневник • Профиль
Два?
Два.
Если один кокос - то в среднем n/2 бросков (начинаем снизу, добавляем по одному этажу пока не разобьется)
Если бесконечно кокосов - то log2(n) бросков (бинарный поиск)
Если один кокос - то в среднем n/2 бросков (начинаем снизу, добавляем по одному этажу пока не разобьется)
Если бесконечно кокосов - то log2(n) бросков (бинарный поиск)
хм...
Начинаем с n/2. Если бьется - то идем снизу попорядку. Если нет, то в 3/4. и т.п.
Мне кажется.
Начинаем с n/2. Если бьется - то идем снизу попорядку. Если нет, то в 3/4. и т.п.
Мне кажется.
Неа
Камрад
Поскольку кокосов 2, то начинать надо не с n/2, а с n/3.
Разбился - вторым кокосом проходим с 1 до n/3.
Не разбился - пробуем n*2/3. Если разбился - вторым кокосом проходим интервал n/3 - n*2/3, если целый - то проверяем n*2/3 - n.
Грубо говоря, второй кокос - сокращение числа попыток втрое по сравнению с одним кокосом. Может, что-то еще придумать можно...
Разбился - вторым кокосом проходим с 1 до n/3.
Не разбился - пробуем n*2/3. Если разбился - вторым кокосом проходим интервал n/3 - n*2/3, если целый - то проверяем n*2/3 - n.
Грубо говоря, второй кокос - сокращение числа попыток втрое по сравнению с одним кокосом. Может, что-то еще придумать можно...
Anafay
Похоже на правду. Я ответа не знаю. Интервьюер сказал что для 100 этажей он добился 9-10 бросков в среднем.
Это учитывая равномерное распределение вероятности разбивания: т.е. P(минимальный этаж = 1) = P(минимальный этаж = k) = P(минимальный этаж = n)
Похоже на правду. Я ответа не знаю. Интервьюер сказал что для 100 этажей он добился 9-10 бросков в среднем.
Это учитывая равномерное распределение вероятности разбивания: т.е. P(минимальный этаж = 1) = P(минимальный этаж = k) = P(минимальный этаж = n)
Камрад
Xirax
Так надо какую оценку - минимальное среднее количество бросков или минимальное в наихудшем случае?
Так надо какую оценку - минимальное среднее количество бросков или минимальное в наихудшем случае?
Anafay
Среднее
Среднее
получил (n+1-2*sqrt(n))/(n-1)