| Вопрос: Задача о Мише и Маше | Добавлено: 31.10.06 19:17 |
Автор вопроса:  appolinari
|
| Ответы | Всего ответов: 37 |
|
Номер ответа: 31 Автор ответа:  SyavX Вопросов: 25 Ответов: 149 |
Профиль | | #31 | Добавлено: 03.11.06 18:56 |
|
Млиииин, бегло условие прочитал...
Тогда, конечно, соглашусь с Морфом 
|
||
|
Номер ответа: 32 Автор ответа: Morpheus Вопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #32 | Добавлено: 04.11.06 04:57 |
|
Так что Морфеус ближе
что значит "ближе"? ^o|
к истине... |
||
|
Номер ответа: 33 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #33 | Добавлено: 04.11.06 05:18 |
|
Про люки боян.
Года полтора назад бродила в блогах инфа что в Microsoft на каждом собеседовании задавали вопрос "крышки люков делают круглыми". Но потом перестали. Потом что на собеседования начали приходить в футболках с надмисями "Чтоб они не падали в колодцы" Про шары - я насчитал 17. Кто меньше? |
||
|
Номер ответа: 34 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #34 | Добавлено: 04.11.06 05:46 |
| Можно еще меньше - 16 | ||
|
Номер ответа: 35 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #35 | Добавлено: 04.11.06 06:30 |
| Виноват, 16 падений доказать не могу, минимальное кол-во падений которое я могу доказать - 17, но уверен что возможно и 16. | ||
|
Номер ответа: 36 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #36 | Добавлено: 04.11.06 06:44 |
|
Ход решения у меня такой.
Разбиваем задачу на две части. В первом случае этаж буде находиться между 1 и 70 включительно, во втором - 71 и 100 включительно. Начинаем бросать шар со следующих этажей, пока он не разобьется: 10 20 30 40 50 60 70 Если на каком-то этаже шар разбивается, допустим, на метке 40, то логично, что этаж находится междя 31 и 40. Бросаем второй шар с этажей 31 по 40 по порядку: 31 32 33 34 35 36 37 38 39 Если на каком-то шагу шар разбивается, то логично, что мы нашли искомый этаж. Если он не разбился на 39 этаже, значит искомый этаж - 40. Логично, что больше всего бросков нужно сделать в том случае если наш этаж - 70 - т.е. 7 + 10=17 Если этаж ниже чем 70, то бросков нужно будет сделать меньше. Artyom says: Итак, вторая часть... Мы бросили шар с 70-го этажа (это 7-й бросок) и он не разбился. Можно продолжить бросать такой же методикой, как и первые 70, и в таком случае мы ограничимся 20-ю бросками, но нас это решение не устраивает. Поэтому мы начинаем бросать шар с таких этажей: 76 82 88 94 100 То есть, через каждые 6 этажей начиная с 71-го. В определенный момент шар разобьется, допустим, это будет 100-й этаж. Логично, что искомый этаж лежит между 95 и 100. Artyom says: Делаем еще 5 бросков: 95 96 97 98 99 В определенный момент шар разобьется - мы нашли наш этаж. Если на разобьется, значит наш этаж - 100. Т.е. в худшем случае нам нужно сделать еще 10 бросков для второго варианта, если их сложить с первыми 7, то получим 17. В обоих вариантах - по 17 бросков. Возможно, если разбить задачу на большее количество частей, можно найти и более оптимальное решение. |
||
|
Номер ответа: 37 Автор ответа: ПавелАдминистратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | | #37 | Добавлено: 04.11.06 07:02 |
Я пока нашел, как 14-ю можно ограничиться. Думаю, это самое оптимальное решение 
Первый кидаем с таких этажей пока он не разобьётся: 14 27 39 50 60 69 77 84 90 95 99 Т.е. каждый раз уменьшаем интервал на 1 (чтобы меньше раз бросать второй шар - и сумма киданий первого и второго шара была максимум равна 14). Далее дело техники... Скажем, остановились на 77-ом (первый шар на нем разбился) - второй шар кидаем с 70-го, 71-го, 72-го, 73-го, 74-го, 75-го, 76-го. После разбивания (и N-го броска) первого шара для нахождения точного этажа остается максимум 14-N бросаний второго шара. Улучшать, думаю, уже некуда. |
||