|
10-07-2007, 12:21
|
#1
|
просто зверь
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
|
Задачка о прочности шариков
Давненько задачек небыло.
Вот одна забавненькая. Легенда гласит, что несколько лет назад ее давали во время собеседования с потенциальными сотрудниками Microsoft.
Есть 100этажное здание с окнами на каждом этаже. У вас есть шарик, про который известно, что если его выбросить из окна на kом этаже или ниже - он упадет на землю и не разобъется. Если выбростить с k+1го или выше - упадет и разобъется.
Задача - выяснить число k.
Для одного шарика эта эта задача решается элементарно: бросить шарик с первого этажа. Если не разбился - перейти на 2ой, бросить оттуда, и так далее подниматься, пока не разобъется. Таким образом не более чем за 100 бросков найдем число k, если оно есть.
Собственно задача: теперь у вас два шарика. Предложите способ точно определить число k за минимальное число бросков.
Математику:
Возможны обобщения: больше шариков, другая высота здания.
|
|
|
10-07-2007, 12:31
|
#2
|
Done & gone
Сообщений: 2,208
Проживание: Kerava
Регистрация: 02-12-2006
Status: Offline
|
"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...
Это тест при приеме в Мелкософт? Да-а-а...
-----------------
"Мы живем в эпоху политкорректности. Даже дерьмо нельзя называть дерьмом, так как это может быть оскорблением национальных чувств какого-нибудь опарыша" (с)
|
|
|
10-07-2007, 13:02
|
#3
|
просто зверь
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
|
Цитата:
Сообщение от Mike BFD
"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...
Это тест при приеме в Мелкософт? Да-а-а...
|
Не возьмут тебя в Microsoft
|
|
|
10-07-2007, 13:47
|
#4
|
Dreamer...
Сообщений: 4,088
Проживание: Vantaa
Регистрация: 05-03-2006
Status: Offline
|
Ну если это два одинаковых шарика, и смысл с помощью их найти число "к" за минимальное кол-во бросков, то можно, как мне кажется, выкидывать каждый раз шарик с каждого второго этажа. Если на 20-ом не разбился, а разбился на 22-ом, то выкидываем второй шарик на 21-ом. Если разбился и там, число "к" = 20; если нет, то "к" = 21...
-----------------
«Человека делают счастливым три вещи: любовь, интересная работа и возможность путешествовать.»
|
|
|
10-07-2007, 13:52
|
#5
|
просто зверь
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
|
Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.
"Есть способ лучше".
|
|
|
10-07-2007, 14:08
|
#6
|
Dreamer...
Сообщений: 4,088
Проживание: Vantaa
Регистрация: 05-03-2006
Status: Offline
|
Цитата:
Сообщение от ank
Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.
"Есть способ лучше".
|
Мда..., это я поторопилси.
Блин, ну тогда с каждого десятого, а как разобъется, вторым шaриком искать этаж.
PS: И чем это я на работе занимаюсь?! Этажи считаю! Дожили.
-----------------
«Человека делают счастливым три вещи: любовь, интересная работа и возможность путешествовать.»
|
|
|
10-07-2007, 16:23
|
#7
|
Гость
Сообщений: n/a
Проживание:
Регистрация:
Status:
|
Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......
Последнее редактирование от PearLinShell : 10-07-2007 в 16:25.
|
|
|
10-07-2007, 16:32
|
#8
|
Done & gone
Сообщений: 2,208
Проживание: Kerava
Регистрация: 02-12-2006
Status: Offline
|
Цитата:
Сообщение от PearLinShell
Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......
|
Я уже предлагал то же самое ("вилку"), только в варианте для произвольного количества шариков, так Анк только усмехается...
-----------------
"Мы живем в эпоху политкорректности. Даже дерьмо нельзя называть дерьмом, так как это может быть оскорблением национальных чувств какого-нибудь опарыша" (с)
Последнее редактирование от Mike BFD : 10-07-2007 в 16:35.
|
|
|
10-07-2007, 17:13
|
#9
|
зеленый и колючий
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
|
А давай кидать с nго этажа, потом с 2nго, потом с 3nго, пока не разобьется, опосля чего хватит еще n бросков 2-го шарика, чтобы уточнить этаж.
Наглый вопрос: а "усталость" и прочие микроповреждения шарика с каждым броском не накапливаются?
|
|
|
10-07-2007, 17:18
|
#10
|
зеленый и колючий
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
|
по-моему, 19 бросков хватит, может и меньше можно...
|
|
|
10-07-2007, 17:36
|
#11
|
Dreamer...
Сообщений: 4,088
Проживание: Vantaa
Регистрация: 05-03-2006
Status: Offline
|
Цитата:
Сообщение от Kaktus
по-моему, 19 бросков хватит, может и меньше можно...
|
Ну так в принципе в мной предложенным способе и получится как раз 19 бросков, если предположить, что шарик кокнется с 100-го этажа. Значит мыслим одинакого.
-----------------
«Человека делают счастливым три вещи: любовь, интересная работа и возможность путешествовать.»
|
|
|
10-07-2007, 17:57
|
#12
|
Cthulhu fhtagn!
Сообщений: 6,166
Проживание:
Регистрация: 13-03-2007
Status: Offline
|
Цитата:
Сообщение от ank
Для одного шарика эта эта задача решается элементарно: бросить шарик с первого этажа. Если не разбился - перейти на 2ой, бросить оттуда, и так далее подниматься, пока не разобъется. Таким образом не более чем за 100 бросков найдем число k, если оно есть.
|
Если k>100, то и за 100 бросков нипочем не найдешь.
|
|
|
10-07-2007, 18:27
|
#13
|
зеленый и колючий
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
|
А если так: проверяем этажи
14, 27(+13), 39(+12), 50(+11), 60(+10), 69, .... 99.
Итого хватит 14 попыток. Что характерно, если 100го этажа шарику мало, это определяется.
Возьмете меня в "мокрохвост"? Что дадут, то и раздолб... оптимизирую нафик
Последнее редактирование от Kaktus : 10-07-2007 в 19:00.
|
|
|
10-07-2007, 18:30
|
#14
|
зеленый и колючий
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
|
Цитата:
Сообщение от Apollon
Ну так в принципе в мной предложенным способе и получится как раз 19 бросков, если предположить, что шарик кокнется с 100-го этажа. Значит мыслим одинакого.
|
Сорри, прозевал твой пост, но я еще лучше придумал
|
|
|
11-07-2007, 11:12
|
#15
|
просто зверь
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
|
Я знал, что решит только Kaktus.
Жаль, что не я беру в Microsoft.
|
|
|
Опции темы |
Поиск в этой теме |
|
|
Опции просмотра |
Оценка этой теме |
Линейный вид
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
|
|
|