Автор: klem4 5.02.2010 13:50
Дано:
- два абсолютно одинаковых шарика по размерам и свойствам
- дом в 100 этажей.
- 20 попыток
Бросаем шарик с этажа X - это минус одна попытка (при этом шарик может разбиться).
Одновременно можно сбросить только один шарик.
Задача: определить минимальный этаж, сбросив с которого шарик, тот разобьется.
Автор: Client 5.02.2010 18:50
Спойлер (Показать/Скрыть)
по-моему, нужно использовать метод "быстрого поиска", т.е. делить на 2, так максимально быстро найдется нужный этаж
Автор: klem4 6.02.2010 0:04
Client,
Спойлер (Показать/Скрыть)
шариков всего 2, попыток всего 20, а этажей 100. И ответы в спойлер пожалуйста ;)
Автор: Client 6.02.2010 1:17
Спойлер (Показать/Скрыть)
а, т.е. если разбился, то разбился?
ну тогда первым шариком определим номер десятка этажа (от 1 до 10, уменьшаем на 1) и вторым ищем номер единиц, т.е. уже конкретный этаж в десятке, также от 1 до 10. Вроде как раз 20 должно быть
Автор: Lapp 6.02.2010 4:23
Вчера ложился спать с определенным намерением решить эту задачу. Вот только не помню, решил или нет..
Автор: volvo 6.02.2010 5:16
Для klem4 (Показать/Скрыть)
Цитата
- 20 попыток
Это, а неиспользованные (как минимум 5, если я ничего не путаю) - куда девать?
Автор: Lapp 6.02.2010 13:00
Тоже неплохая задачка )). На ней хорошо объяснять суть позиционных систем счисления, наверное.
решение (Показать/Скрыть)
Сначала пройтись по этажам 10*i, i=1,2,..,10, а потом по 10*(iгде разбился-1)+j, j=1,2,...,10.
Автор: klem4 6.02.2010 16:35
to volvo
Спойлер (Показать/Скрыть)
Второй вопрос в задаче был как раз в нахождении минимального числа нужных попыток, но я его опустил
20 - избыточно
Автор: Unconnected 6.02.2010 19:42
15 (Показать/Скрыть)
Придумал метод, в котором максимум будет задействовано 15 попыток. Первым шариком определяем нужный десяток, сначала кидаем с 10го, потом с 20го... Выявив десяток, начинаем сбрасывать шарик с первого этажа этого десятка, потом с 3го, 5го... Т.е. прибавляем по 2. Искомый этаж будет "тот, с которого шарик разбился"-1 .
Автор: TarasBer 6.02.2010 20:23
Спойлер (Показать/Скрыть)
Ну понятно, первым шариком идём по этажам с неким диапазоном, а вторым уже с каждого этажа, только в пределах одного диапазона.
Например, кидать 1й шарик с 20, 39, 57, 74, 90, 100 этажей (диапазон каждый раз уменьшаем на 1, чтоб выравнять число попыток).
На самом деле, и 14 попыток хватит, если кидать 1й шарик с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105 этажей.
Автор: Unconnected 7.02.2010 1:18
15 (Показать/Скрыть)
Ага, верно подмечено:) Если номер этажа кратен десяти, или равен одному, то отнимать ничего не надо
Автор: Archon 7.02.2010 2:03
Спойлер (Показать/Скрыть)
Первый шарик бросаем с этажей номер F(i) = i*n - 1/2*i*(i-1), где i - номер попытки, а n - число попыток, которые мы намереваемся использовать. Когда на j-ом шаге шарик разобьется, то начинаем сбрасывать второй с позиции F(j-1) + 1 и шагом 1. На каком этаже разобьется, тот нам и нужен. При этом максимальный этаж, который мы можем проверить равен Fmax(n) = 1/2*n*(n+1). Отсюда находим минимально необходимое кол-во попыток для 100 этажей - 14.
Автор: Archon 7.02.2010 2:33
2 volvo (Показать/Скрыть)
Цитата
Это, а неиспользованные (как минимум 5, если я ничего не путаю) - куда девать?
А это чтобы делить людей на тех, кто решил за 19 попыток и тех, кто решил за 14 =).
Автор: Lapp 7.02.2010 3:14
Фи, Archon
Цитата(Archon @ 6.02.2010 22:33)
2 volvo (Показать/Скрыть)
А это чтобы делить людей на тех, кто решил за 19 попыток и тех, кто решил за 14 =).
Займемся расчлененкой?..
Какой вопрос - такой ответ. Задача поставлена, и ее решение есть решение.
Я сначала решил за 20, и был очень рад. Запиши меня в свой списочек людей второго (или n+1, n на твой выбор) разряда..
Автор: Archon 7.02.2010 10:43
Ну вот, сейчас я и сам заметил, что фразу сформулировал неудачно. Никого не хотел обидеть, правда. Просто часто сталкивался с тем, что "задачи для собеседований" (а это, похоже, одна из таких) имеет некую подоплеку. То есть работодателю важно не только решил ли соискатель задачу, но и как он ее решил. Свое отношение к этому вопросу я не высказывал, так что "Фи" считаю незаслуженным =).
Автор: Lapp 7.02.2010 17:20
Цитата(Archon @ 7.02.2010 6:43)
Ну вот, сейчас я и сам заметил, что фразу сформулировал неудачно. Никого не хотел обидеть, правда.
Хорошо, спишем на недоразумение..
;)
Автор: Client 7.02.2010 17:52
Archon, я так и не понял как ты сделал. Объясни, пожалуйста
Автор: Archon 7.02.2010 21:39
Цитата
Archon, я так и не понял как ты сделал. Объясни, пожалуйста
Так же, как
TarasBer.
Спойлер (Показать/Скрыть)
Сбрасываем первый шарик через некоторые промежутки пока не разобьется. Вторым шариком последовательно проверяем все этажи в последнем промежутке. Причем промежутки каждый раз надо выбирать не больше оставшегося числа попыток.
Например, если число попыток 20, то максимальный этаж, с которого можно сбросить шарик на первой попытке - 20. Тогда оставшихся 19 попыток как раз хватит на проверку этажей с 1 по 19. Если шарик на первой попытке не разбился, то далее его можно скинуть максимум с 39 этажа. Тогда оставшихся 18 попыток хватит на проверку этажей с 21 по 38. И так далее. Получается, что первый шарик сбрасывается с этажей 20, 39, 57, 74,...
В обобщенном виде номер этажа вычисляется по формуле:
F(i) = i*n - 1/2*i*(i-1), где i - номер попытки, а n - число попыток, которые мы намереваемся использовать.
При этом максимальный этаж, который мы можем проверить равен:
Fmax(n) = 1/2*n*(n+1)
Подставив высоту здания (100 этажей) в последнюю формулу, найдем минимальное число попыток.
Автор: Client 7.02.2010 21:46
Archon
Спойлер (Показать/Скрыть)
Понял.
Спасибо