Вернуться   Финляндия по-русски » Жизнь в Финляндии » Творчество и юмор » Творческие и интеллектуальные развлечения
Логин
Пароль

Ответ
 
Опции темы Поиск в этой теме Оценить тему Опции просмотра
Old 10-07-2007, 12:21   #1
ank
просто зверь
 
Аватар для ank
 
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
Задачка о прочности шариков

Давненько задачек небыло.
Вот одна забавненькая. Легенда гласит, что несколько лет назад ее давали во время собеседования с потенциальными сотрудниками Microsoft.

Есть 100этажное здание с окнами на каждом этаже. У вас есть шарик, про который известно, что если его выбросить из окна на kом этаже или ниже - он упадет на землю и не разобъется. Если выбростить с k+1го или выше - упадет и разобъется.

Задача - выяснить число k.
Для одного шарика эта эта задача решается элементарно: бросить шарик с первого этажа. Если не разбился - перейти на 2ой, бросить оттуда, и так далее подниматься, пока не разобъется. Таким образом не более чем за 100 бросков найдем число k, если оно есть.

Собственно задача: теперь у вас два шарика. Предложите способ точно определить число k за минимальное число бросков.

Математику:
Возможны обобщения: больше шариков, другая высота здания.
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 12:31   #2
Mike BFD
Done & gone
 
Аватар для Mike BFD
 
Сообщений: 2,208
Проживание: Kerava
Регистрация: 02-12-2006
Status: Offline
"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...

Это тест при приеме в Мелкософт? Да-а-а...

-----------------
"Мы живем в эпоху политкорректности. Даже дерьмо нельзя называть дерьмом, так как это может быть оскорблением национальных чувств какого-нибудь опарыша" (с)
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 13:02   #3
ank
просто зверь
 
Аватар для ank
 
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
Цитата:
Сообщение от Mike BFD
"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...

Это тест при приеме в Мелкософт? Да-а-а...

Не возьмут тебя в Microsoft
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 13:47   #4
Apollon
Dreamer...
 
Аватар для Apollon
 
Сообщений: 4,088
Проживание: Vantaa
Регистрация: 05-03-2006
Status: Offline
Ну если это два одинаковых шарика, и смысл с помощью их найти число "к" за минимальное кол-во бросков, то можно, как мне кажется, выкидывать каждый раз шарик с каждого второго этажа. Если на 20-ом не разбился, а разбился на 22-ом, то выкидываем второй шарик на 21-ом. Если разбился и там, число "к" = 20; если нет, то "к" = 21...

-----------------
«Человека делают счастливым три вещи: любовь, интересная работа и возможность путешествовать.»
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 13:52   #5
ank
просто зверь
 
Аватар для ank
 
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.

"Есть способ лучше".
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 14:08   #6
Apollon
Dreamer...
 
Аватар для Apollon
 
Сообщений: 4,088
Проживание: Vantaa
Регистрация: 05-03-2006
Status: Offline
Цитата:
Сообщение от ank
Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.

"Есть способ лучше".
Мда..., это я поторопилси.

Блин, ну тогда с каждого десятого, а как разобъется, вторым шaриком искать этаж.

PS: И чем это я на работе занимаюсь?! Этажи считаю! Дожили.

-----------------
«Человека делают счастливым три вещи: любовь, интересная работа и возможность путешествовать.»
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 16:23   #7
PearLinShell
Гость
 
Сообщений: n/a
Проживание:
Регистрация:
Status:
Cool

Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......

Последнее редактирование от PearLinShell : 10-07-2007 в 16:25.
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 16:32   #8
Mike BFD
Done & gone
 
Аватар для Mike BFD
 
Сообщений: 2,208
Проживание: Kerava
Регистрация: 02-12-2006
Status: Offline
Unhappy

Цитата:
Сообщение от PearLinShell
Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......

Я уже предлагал то же самое ("вилку"), только в варианте для произвольного количества шариков, так Анк только усмехается...

-----------------
"Мы живем в эпоху политкорректности. Даже дерьмо нельзя называть дерьмом, так как это может быть оскорблением национальных чувств какого-нибудь опарыша" (с)

Последнее редактирование от Mike BFD : 10-07-2007 в 16:35.
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 17:13   #9
Kaktus
зеленый и колючий
 
Аватар для Kaktus
 
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
А давай кидать с nго этажа, потом с 2nго, потом с 3nго, пока не разобьется, опосля чего хватит еще n бросков 2-го шарика, чтобы уточнить этаж.

Наглый вопрос: а "усталость" и прочие микроповреждения шарика с каждым броском не накапливаются?
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 17:18   #10
Kaktus
зеленый и колючий
 
Аватар для Kaktus
 
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
по-моему, 19 бросков хватит, может и меньше можно...
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 17:36   #11
Apollon
Dreamer...
 
Аватар для Apollon
 
Сообщений: 4,088
Проживание: Vantaa
Регистрация: 05-03-2006
Status: Offline
Цитата:
Сообщение от Kaktus
по-моему, 19 бросков хватит, может и меньше можно...

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

-----------------
«Человека делают счастливым три вещи: любовь, интересная работа и возможность путешествовать.»
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 17:57   #12
SannamannA
Cthulhu fhtagn!
 
Аватар для SannamannA
 
Сообщений: 6,166
Проживание:
Регистрация: 13-03-2007
Status: Offline
Цитата:
Сообщение от ank
Для одного шарика эта эта задача решается элементарно: бросить шарик с первого этажа. Если не разбился - перейти на 2ой, бросить оттуда, и так далее подниматься, пока не разобъется. Таким образом не более чем за 100 бросков найдем число k, если оно есть.


Если k>100, то и за 100 бросков нипочем не найдешь.
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 18:27   #13
Kaktus
зеленый и колючий
 
Аватар для Kaktus
 
Сообщений: 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.
 
0
 
0
    Ответить с цитированием
Old 10-07-2007, 18:30   #14
Kaktus
зеленый и колючий
 
Аватар для Kaktus
 
Сообщений: 1,379
Проживание:
Регистрация: 25-06-2003
Status: Offline
Цитата:
Сообщение от Apollon
Ну так в принципе в мной предложенным способе и получится как раз 19 бросков, если предположить, что шарик кокнется с 100-го этажа. Значит мыслим одинакого.


Сорри, прозевал твой пост, но я еще лучше придумал
 
0
 
0
    Ответить с цитированием
Old 11-07-2007, 11:12   #15
ank
просто зверь
 
Аватар для ank
 
Сообщений: 6,244
Проживание:
Регистрация: 28-07-2004
Status: Offline
Я знал, что решит только Kaktus.
Жаль, что не я беру в Microsoft.
 
0
 
0
    Ответить с цитированием
Ответ


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра Оценка этой теме
Оценка этой теме:

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

vB коды Вкл.
[IMG] код Вкл.
HTML код Выкл.



» Объявления на Doska.fi

» Галерея Финляндии

» Реклама на Doska.fi

» Реклама на Russian.fi


Часовой пояс GMT +3, время: 14:42.

Russian.fi - Финляндия по-русски © Suomitech Oy, 2002-2024 При использовании материалов с сайта указание ссылки на russian.fi обязательно