Задача о двух шариках Опции

[klem4]

Дано:
- два абсолютно одинаковых шарика по размерам и свойствам
- дом в 100 этажей.
- 20 попыток

Бросаем шарик с этажа X - это минус одна попытка (при этом шарик может разбиться).
Одновременно можно сбросить только один шарик.

Задача: определить минимальный этаж, сбросив с которого шарик, тот разобьется.

[Client]

Спойлер (Показать/Скрыть)

по-моему, нужно использовать метод "быстрого поиска", т.е. делить на 2, так максимально быстро найдется нужный этаж

Сообщение отредактировано: klem4 - 6.02.2010 0:04

[klem4]

Client,

Спойлер (Показать/Скрыть)

шариков всего 2, попыток всего 20, а этажей 100. И ответы в спойлер пожалуйста ;)

[Client]

Спойлер (Показать/Скрыть)

а, т.е. если разбился, то разбился? ну тогда первым шариком определим номер десятка этажа (от 1 до 10, уменьшаем на 1) и вторым ищем номер единиц, т.е. уже конкретный этаж в десятке, также от 1 до 10. Вроде как раз 20 должно быть

[Lapp]

Вчера ложился спать с определенным намерением решить эту задачу. Вот только не помню, решил или нет..

[volvo]

Для klem4 (Показать/Скрыть)

- 20 попыток

Это, а неиспользованные (как минимум 5, если я ничего не путаю) - куда девать?

[Lapp]

Тоже неплохая задачка )). На ней хорошо объяснять суть позиционных систем счисления, наверное.

решение (Показать/Скрыть)

Сначала пройтись по этажам 10*i, i=1,2,..,10, а потом по 10*(i_{где разбился}-1)+j, j=1,2,...,10.

[klem4]

to volvo

Спойлер (Показать/Скрыть)

Второй вопрос в задаче был как раз в нахождении минимального числа нужных попыток, но я его опустил 20 - избыточно

[Unconnected]

15 (Показать/Скрыть)

Придумал метод, в котором максимум будет задействовано 15 попыток. Первым шариком определяем нужный десяток, сначала кидаем с 10го, потом с 20го... Выявив десяток, начинаем сбрасывать шарик с первого этажа этого десятка, потом с 3го, 5го... Т.е. прибавляем по 2. Искомый этаж будет "тот, с которого шарик разбился"-1 .

Сообщение отредактировано: Unconnected - 6.02.2010 19:43

[TarasBer]

Спойлер (Показать/Скрыть)

Ну понятно, первым шариком идём по этажам с неким диапазоном, а вторым уже с каждого этажа, только в пределах одного диапазона.
Например, кидать 1й шарик с 20, 39, 57, 74, 90, 100 этажей (диапазон каждый раз уменьшаем на 1, чтоб выравнять число попыток).
На самом деле, и 14 попыток хватит, если кидать 1й шарик с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105 этажей.

[Client]

Unconnected

15 (Показать/Скрыть)

Вот насчет "-1" не во всех случаях, сам же знаешь что может быть именно этот минимальный этаж, а не предыдущий

[Unconnected]

15 (Показать/Скрыть)

Ага, верно подмечено:) Если номер этажа кратен десяти, или равен одному, то отнимать ничего не надо

[Archon]

Спойлер (Показать/Скрыть)

Первый шарик бросаем с этажей номер 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]

2 volvo (Показать/Скрыть)

Это, а неиспользованные (как минимум 5, если я ничего не путаю) - куда девать?

А это чтобы делить людей на тех, кто решил за 19 попыток и тех, кто решил за 14 =).

[Lapp]

Фи, Archon

2 volvo (Показать/Скрыть)

А это чтобы делить людей на тех, кто решил за 19 попыток и тех, кто решил за 14 =).

Займемся расчлененкой?..
Какой вопрос - такой ответ. Задача поставлена, и ее решение есть решение.
Я сначала решил за 20, и был очень рад. Запиши меня в свой списочек людей второго (или n+1, n на твой выбор) разряда..

[Archon]

Ну вот, сейчас я и сам заметил, что фразу сформулировал неудачно. Никого не хотел обидеть, правда. Просто часто сталкивался с тем, что "задачи для собеседований" (а это, похоже, одна из таких) имеет некую подоплеку. То есть работодателю важно не только решил ли соискатель задачу, но и как он ее решил. Свое отношение к этому вопросу я не высказывал, так что "Фи" считаю незаслуженным =).

[Lapp]

Ну вот, сейчас я и сам заметил, что фразу сформулировал неудачно. Никого не хотел обидеть, правда.

Хорошо, спишем на недоразумение..

;)

[Client]

Archon, я так и не понял как ты сделал. Объясни, пожалуйста

[Archon]

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]

Archon

Спойлер (Показать/Скрыть)

Понял.
Спасибо

Сообщение отредактировано: Client - 7.02.2010 21:47