Страниц: 1 2 [3]
  Печать  
Автор Тема: 2 шарика  (Прочитано 16743 раз)
0 Пользователей и 1 Гость смотрят эту тему.

у вас есть 2 идентичных деревяных шарика, и 100-этажный дом. Задание узнать с какого самого нижнего этажа шарикт разобьется,за минимальное количество кидков, при падении с более нижнего этажа шарики повреждения не получают.
drobin
Давненько
**
Offline Offline

Сообщений: 40

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 7


Просмотр профиля
Ответ #30 : Март 23, 2009, 04:25:46 �

А Разор и не заметил, как написал доказательство того, что меньше, чем за 14, нельзя,
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #31 : Март 22, 2010, 23:12:48 �

Граждане, можно меньше! Не с той стороны подход к задаче ищите!
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #32 : Март 22, 2010, 23:26:30 �

Граждане, можно меньше! Не с той стороны подход к задаче ищите!
моего решения Вы не видели, а я уже не помню)))) могу конечно вспомнить алгоритм, если нужно, но меньше 14 - не уверен, что можно.
кстати, Сэр, если ты читаешь, у тебя не сохранилось моя личка годовой давности?))))
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #33 : Март 22, 2010, 23:28:02 �

Что за личка годовой давности? Это о чем?
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #34 : Март 22, 2010, 23:31:32 �

Упс. Извиняюсь. Да, нельзя меньше, чем 14.
Вот толковое объяснение решения:

Если бы в наличии было всего одно яйцо, то пришлось бы последовательного сбрасывать его с первого этажа, потом со второго, и далее до сотого, но у нас их два, поэтому используем второе для минимизации количества тестов. Будем делить оставшееся количество этажей пополам, сначала сбросим яйцо с 50-го этажа, если разбилось, значит оставшееся яйцо надо будет последовательно сбрасывать с 1-го по 49й этаж, если не разбилось, то бросаем его снова, с 75-го этажа, и так далее. В худшем случае 50 тестов.
Это первое решение, которое пришло в голову так ищет информацию Rambler, тут коварный HR-менеджер предложит Вам улучшить своё решение, и не спешите спорить с ним на бутылку водки, что это решение и так самое лучшее.

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

Пусть X будет необходимое количество попыток. Таким образом, если одно яйцо разобьется, то оставшееся надо будет бросить X-1 раз. Если яйцо не разбилось, то на следующем этапе (если оно разобьется) на тесты с оставшимся яйцом останется X-2 попыток. Объясню на примере - Мы решили что оптимальное количество попыток всего 16, тогда бросаем одно яйцо с шестнадцатого этажа (уже одна израсходованная попытка), и если оно разбилось, то с помощью оставшегося проверяем 16-1=15 этажей. Если оно не разбилось, то у нас осталось в запасе 15 попыток, значит на следующем этапе нужно будет бросать яйцо (и еще одна попытка будет использована) с 16+15+1=32 этажа, так как если яйцо разобьется на 32м этаже, нам хватит 14 попыток чтобы проверить этажи с 17 по 31й.

Нам нужно найти, какое количество опытов будет оптимальным, это будет такое количество, при котором на заключительном этапе понадобится 0 экспериментов. Запишем это в виде последовательности:
(1+a) + (1+(a-1))+ (1+(a-2)) + ...+ (1+0) >= 100
Где 1+p это и будет то количество опытов, которое мы ищем, обозначим его X. Тогда X(X+1)/2 >=100 в нашем случае, надеюсь, Вы не забыли как решать квадратные уравнения?Wink На случай, если забыли, ответ будет 14, соответственно одним яйцом (если оно не разбивается) будем проверять 14й, 27й, 39й, 50й, 60й, 69й, 77й, 84й, 90й, 95й, 99й, 100й этажи, если на одном из этапов яйцо разобьется, то проверим этажи, от максимального, где яйцо еще не билось, до того где оно разбилось.

Получаем результат - до 14 тестов.

Если бы в здании было 36 этажей, тогда X(X+1)/2>=36, решение было бы X=8, и проверить нужно будет 8, 15, 21, 26, 30, 33, 35, 36 этажи, пока яйцо не разобьется.
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #35 : Март 22, 2010, 23:33:09 �

Что за личка годовой давности? Это о чем?
я как человек ленивый, прежде чем восстанавливать свое решение годовой давности прошу другого форумчанина проверить не сохранилось ли это самое решение у него в личных сообщениях, куда я ему его отправлял по его просьбе! Cheesy
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #36 : Март 22, 2010, 23:34:30 �

ну вот и разобрались  Smiley
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #37 : Март 22, 2010, 23:35:48 �

Что за личка годовой давности? Это о чем?
я как человек ленивый, прежде чем восстанавливать свое решение годовой давности прошу другого форумчанина проверить не сохранилось ли это самое решение у него в личных сообщениях, куда я ему его отправлял по его просьбе! Cheesy
Тут, видать, ошибка, т.к. на форуме я где-то 2-3 месяца. Это нереально, год назад меня тут не  было.Smiley
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #38 : Март 22, 2010, 23:44:46 �

так я не тебе писАл, а ТС-у, т.е. серебряннику (памятнику, Сэру), его ветка же была Wink
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #39 : Март 22, 2010, 23:50:14 �

так я не тебе писАл, а ТС-у, т.е. серебряннику (памятнику, Сэру), его ветка же была Wink

Нет, условия этой задачи я услышал только сегодня.  Smiley
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #40 : Март 22, 2010, 23:55:00 �

да ты то сегодня, я тебе написал, что мы уже обсуждали (в этой самой вот где я сейчас пишу ветке) эту задачу и тогда же год назад дал человеку ответ, который сегодня просил проверить в ЛС.
вобщем, не заморачивайся. все решилось уже само собой))))
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #41 : Март 22, 2010, 23:58:09 �

да ты то сегодня, я тебе написал, что мы уже обсуждали (в этой самой вот где я сейчас пишу ветке) эту задачу и тогда же год назад дал человеку ответ, который сегодня просил проверить в ЛС.
вобщем, не заморачивайся. все решилось уже само собой))))

Без питань!
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Страниц: 1 2 [3]
  Печать  
 
Перейти в: