Вопросы на собеседовании

И правда, нет смысла кидать с шагом фиксированным, ибо тогда на первых шагах остается дофига неиспользованных попыток :)

Каждый следующий шаг можно уменьшать на 1.

Итого имеем:

Пусть гарантированный минимум это X.

Первый бросок с шагом X с этажа X, второй с шагом X-1 с этажа 2X-1, третий с шагом X-2 c этажа 3X-3 и так далее в общем случае k-й бросок (начинаем с k=0) будет с шагом X-k с этажа (k+1)*X-k*(k+1)/2, при этом шаг X=k уже не имеет смысла.

Надо найти такое минимальное X, чтобы (X+1)*X-X*(X+1)/2=X*(X+1)/2 всё еще было не менее 100. Считаем X*(X+1)/2=100 => X*X+X-200=0, один из корней - X=13.6 округлим до целого и итого имеем X=14.

Первый шар бросаем на 14 этаж, потом на 14+13=27 этаж, потом на 27+12=39 этаж, потом на 39+11=60 этаж, потом на 60+9=69 этаж, потом на 69+8=77 этаж, потом на 77+7=84 этаж, потом на 84+6=90 этаж, потом на 90+5=95 этаж, потом на 99 этаж.

Если бы начинали бросать с 13 этажа, до 100 этажа бы не дошли.

Это сообщение отредактировал xeax - 7.02.2015 - 13:13

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

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

19

Первый раз бросаем с десятого.. Если бьется, то оставшийся шарик кидаем с первого по десятый, пока не найдем искомый..
итого вариантов кидания первого шарика: , 10, 20 и т.д. т.е 10 попыток.
если разбился на 10-й, то кидаем 91, 92 и тд пока не разобьется.

Это сообщение отредактировал RusikR2D2 - 7.02.2015 - 12:51

Минимум 1 попытка.
Начать с первого этажа. Шар может сразу разбиться.

А далее, если не разбился, то как предлагают уважаемые коллеги - по нечетным этажам. Так получится минимизировать количество последующих попыток.

Это сообщение отредактировал vedernikoff - 7.02.2015 - 12:51

такой алгоритм:
первый бросок на середине дома - 50 этаж.
Разбился-начинаем с первого и выше, пока не разобьется.
Не разбился-начинаем с 51 и вверх.
Гарантированно за 49 попыток.

Херовый алгоритм, неправ.

Это сообщение отредактировал Xerxes - 7.02.2015 - 12:57

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

И никакая это задаче не математическая, а чистая логика.

Это сообщение отредактировал Алексей750 - 7.02.2015 - 12:51

О! Человек понял суть задачи!

Кто еще лучший алгоритм придумает?

Если ещё точнее - 18. Первый шарик с первого можно и не бросать))

А зачем бегать? на лифте ж можно)) 100 этажей без него никто не строит.

Это сообщение отредактировал hotaby4 - 7.02.2015 - 12:52

то о чем я и написал

Не обязательно по нечетным. Нужно идти через 2 этажа. То есть 3 - 5 - 8. Так как шарика 2, то второй промежуток проверяется 1 броском в случае если 1-ый разбился. А если не разбился, то и проверять не нужно - идти вверх.

Ой, ошиблась в предыдущем сообщении, не 100% гарантия там вычисления этажа.
Кидать по четным этажам начиная со второго, как разобьется, оставшийся кинуть с этажа ниже, это самый оптимальный получится метод выяснить высоту разбивания шарика, со 100% гарантией.

бляяяяя, 29 лет, а что такое ускорение свободного падения не знает оно ровно 9,780 м/с² , для справки
минимальное количество 2 попытки, максимально 100, минимальное максимальных 49

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

Кстати, в условиях не сказано, что нужно узнать МИНИМАЛЬНЫЙ этаж, с которого шарики разбиваются (в этом случае задача становиться математической и двумя шариками не обойтись), а всего лишь надо гарантированно узнать этаж, с которого шарики гарантированно разбиваются.

Итак:

1) бросаем с 100 этажа
шарик не разбивается - задача не имеет решения, т.к. больше этажей у нас нет
шарик разбивается - как минимум имеем ответ "100 этаж", но надо уточнить

2) бросаем с 1 этажа
шарик не разбивается - ответ "100 этаж" см. пункт 1
шарик разбивается - ответ "1 этаж"

Ответ: 2 попытки - и мы гарантированно знаем на каком этаже (100 или 1) разбивается ли шарик

---
Примерно так. По поводу первого этаже не уверен. Может, надо 99 проверять

Это сообщение отредактировал Viktar83 - 7.02.2015 - 12:54

Кстати, чтобы не бегать по лестнице - нужно использовать лифт!

С яйцами тут лучше не появляться. Тут же срач бы начался "а каким концом упало яйцо"?, "А от одной или разных куриц яйца" и т.д.
С шариками - на ЯПе проще

Начинаем с 14.
Повторяем итерации до тех пор, пока не разобьется, уменьшая шаг (14, 27, 39, 50, 69, 77, 84, 90, 95, 99)
Как разбился, начинаем кидать второй, с этажа+1, с которого не разбился разбился первый шар в предыдущем примере.
14 попыток в самом худшем случае.
Предположим, что на 14-м не разбился, а на 27 разбился.
Начинаем второй кидать с 15, 16 и т.д.

Это сообщение отредактировал WhiskIn - 7.02.2015 - 13:10

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

Это сообщение отредактировал tserg - 7.02.2015 - 12:55

14 попыток.
Не моё, честно нашел

51 попытка - 1,3,5,7,9......,99 (50 попыток). Если не разбился 100 этаж, если разбился на 99 проверяется 98.

ответ то совсем простой - "при падении с этажа, с которого шарики начинают разбиваться, шарики начинают разбиваться". Одна попытка.

Тут уже алгоритм представили что за 14 бросков гарантировано можно узнать номер этажа

Если первый шар кидать с каждого 11-го этажа, то за 19 попыток можно узнать.
А что бы меньше бегать по этажам, видимо только по-порядку с, начиная с первого, ну или пользоваться лифтом.

Я не уловил. Это ржака какая-то или что? Ну то есть при определённом раскладе шарики разобьются падая уже с первого этажа.

Обезьяна хочет определить, из окна какого самого низкого этажа 15-этажного дома нужно бросить кокосовый орех, чтобы он разбился. Сколько бросков потребуется обезьяне, чтобы гарантированно удовлетворить свое любопытство, если у нее есть два ореха (орехи одинаковые по своим ударопрочным характеристикам)?

Возможно, предлагаемое решение покажется вам чересчур подробным, но в нем нарочно сделана попытка показать, как вообще нужно строить рассуждения и какие нужно пытаться ставить вопросы, решая нестандартные задачи. Такие «слишком подробные» места выделены мелким шрифтом и их можно пропускать, если вы торопитесь узнать ответ.

Сначала решим задачу, предполагая, что в распоряжении обезьяны есть только 1 кокосовый орех. Ее действия в этом случае предопределены: сначала она должна бросить орех с 1-го этажа, затем, если он не разбился, — со 2-го этажа, если он снова не разбился — с 3-го этажа и так далее. Тот этаж, при броске с которого кокосовый орех разобьется, и будет искомым.

Спросим себя, может ли обезьяна действовать иначе? Допустим, первый бросок она совершила не с 1-го этажа, а с 3-го. Если кокосовый орех не разбился, то это означает, что он не разбился бы и при бросках с 1-го и 2-го этажей; для более высоких этажей результат неизвестен, и обезьяне нужно продолжить свои изыскания. Но что означает, что орех разбился? Ясно, что тогда он разбился бы и при броске с 4-го, 5-го, ..., 15-го этажей. Но разбился бы орех, если бы обезьяна скинула его с 1-го или со 2-го этажа? Это остается невыясненным, а проверить возможности не представляется, поскольку единственный кокосовый орех уже расколот, а больше орехов у обезьяны нет.

Точно так же, совершив первый бросок с 1-го этажа, второй бросок — в том случае, если орех не разбился — обезьяна должна сделать со 2-го этажа. Потому что если вместо этого она скинет орех с любого другого (более высокого) этажа, и орех расколется, останется невыясненным, разбился бы он при броске со 2-го этажа или нет. А проверить это опытным путем возможности больше не будет.

Таким образом, если в распоряжении обезьяны всего 1 кокосовый орех, она должна бросать его последовательно с 1-го этажа, 2-го этажа, 3-го этажа и так далее до тех пор, пока орех не разобьется (или пока этажи не закончатся). Ясно, что в самом худшем случае — если орех попался достаточно твердый — обезьяне потребуется совершить 15 бросков.

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

Итак, чтобы гарантированно удовлетворить свое любопытство, обезьяне понадобится столько же бросков, сколько в доме этажей. Для удобства сформулируем этот результат в виде леммы.

Лемма 1. Если в доме n этажей, а у обезьяны 1 орех, то нужно n бросков.

Вернемся к исходной задаче. Зададимся таким вопросом: что будет, если первым броском свой первый кокосовый орех обезьяна скинет, скажем, с 10-го этажа? Имеется два возможных исхода. Либо орех расколется, и тогда у обезьяны останется только один кокосовый орех и естественное любопытство, с какого самого низкого из первых девяти этажей его нужно бросить, чтобы он разбился. Как мы уже знаем из леммы 1, для этого надо совершить 9 бросков. Либо орех останется целым, а значит, у обезьяны в наличии по-прежнему будет 2 ореха, но проверке теперь будут подлежать лишь последние 5 этажей.

Следовательно, бросок ореха с 10-го этажа сводит исходную задачу к двум другим: «1 орех, 9 этажей» и «2 ореха, 5 этажей». Вычислив количество необходимых бросков в каждой из этих задач, нам нужно будет взять максимум из этих двух чисел, а затем прибавить к нему единицу. Так мы получим ответ для исходной задачи при условии, что первый бросок был совершен с 10-го этажа. Точно так же, если первой попыткой обезьяна скидывает свой орех с 5-го этажа, это приводит ее либо к ситуации «1 орех, 4 этажа» (если орех разбился), либо к ситуации «2 ореха, 10 этажей» (если орех остался целым). И вообще, бросок с k-ого этажа естественным образом дробится на два случая: «1 орех, (k − 1) этаж» и «2 ореха, (15 − k) этажей».

Все вышесказанное приводит нас к необходимости последовательно найти решение для ситуаций «2 ореха, 1 этаж», «2 ореха, 2 этажа», «2 ореха, 3 этажа», ..., «2 ореха, 14 этажей». Исследуем их подробнее.

Ясно, что если в доме лишь 1 этаж, то достаточно всего одного броска. Если в доме 2 этажа, то необходимо совершить 2 броска. В самом деле, если обезьяна скинет орех с 1-го этажа, а он не разобьется, то второй попыткой ей придется сбрасывать его со 2-го этажа. Если же обезьяна скинет орех со 2-го этажа, а он не разобьется, то останется невыясненным, раскололся бы орех при броске с 1-го этажа или нет. Для ответа на этот вопрос нужно скинуть с 1-го этажа второй орех.

Интереснее ситуация, когда в доме 3 этажа. Ясно, что в этом случае одним броском обезьяне не обойтись. Однако оказывается, что двух попыток вполне достаточно. Именно, первый бросок надо совершить со 2-го этажа. Далее, если орех не разбился, его нужно скинуть с 3-го этажа. А если разбился, то надо взять второй орех и скинуть его с 1-го этажа.

Как теперь быть, если в доме 4 этажа? Сколько попыток обезьяне понадобится? С одной стороны, очевидно, что не меньше, чем в том случае, когда этажей было 3, то есть как минимум 2 попытки. С другой стороны, если первый бросок обезьяна совершит с 1-го этажа, то в удачном случае (орех разбился) делать больше ничего не придется, а в неудачном (орех не разбился) задача сведется к уже известной «2 ореха, 3 этажа», которая решалась в 2 броска. Таким образом, 3 бросков обезьяне заведомо достаточно. Весь вопрос теперь заключается в том, всегда ли в неудачном случае обезьяне понадобится 3 броска или же можно гарантированно обойтись двумя. Оказывается, двух попыток, вообще говоря, недостаточно. Ведь если первый бросок обезьяна совершит с 1-го или 2-го этажа, а орех не расколется, то останутся непроверенными как минимум 2 верхних этажа, что требует еще 2 попытки. Если же после первого броска, совершенного с 3-го или 4-го этажа, орех разобьется, то опять же останется как минимум два непроверенных этажа (на этот раз нижние), снова требующие хотя бы 2 попытки. То есть ответ в задаче «2 ореха, 4 этажа» — 3 броска.

Как мы видим, увеличение на 1 количества этажей в доме изменяет число необходимых бросков не более чем на 1. Однако иногда количество попыток увеличивается, а иногда остается прежним. Таким образом, нам нужно понять закономерность: в каких случаях при увеличении этажности ответ будет меняться, а в каких — нет. Чтобы определить эту закономерность, разберем случаи, когда у обезьяны два кокосовых ореха, а этажей в доме 5, 6 и 7.

Итак, если в доме 5 этажей, то скидывание первого ореха с 1-го этажа, как мы уже понимаем, приводит к ситуации «2 ореха, 4 этажа» с известным результатом — 3 броска, то есть всего понадобится 4 попытки. А вот если обезьяна скинет орех уже со 2-го этажа, то задача сведется к двум таким: «1 орех, 1 этаж» и «2 ореха, 3 этажа». Они решаются за 1 и 2 попытки соответственно, максимум из этих двух чисел равен 2, а значит, всего обезьяне понадобится 3 броска. То есть задачи «2 ореха, 4 этажа» и «2 ореха, 5 этажей» имеют одинаковый ответ: 3 броска.

Аналогичная ситуация обнаруживается при разборе задачи «2 ореха, 6 этажей». Если первое скидывание проводится с 1-го этажа, то задача сводится к ситуации «2 ореха, 5 этажей» с результатом 3 броска и общим ответом 4 броска. Если первое скидывание обезьяна производит со 2-го этажа, то задача сводится к случаям «1 орех, 1 этаж» и «2 ореха, 4 этажа». Для их разрешения необходимо совершить 1 и 3 броска соответственно, максимум этих чисел — 3, а значит, общим результатом будут 4 броска. Если же первое скидывание произошло с 3-го этажа, то задача разделяется на «1 орех, 2 этажа» и «2 ореха, 3 этажа». В каждой из полученных подзадач получается 2 броска, поэтому всего нужно сделать 3 броска.

Наконец, если в доме 7 этажей, а у обезьяны 2 кокосовых ореха, то первый бросок, произведенный с 1-го этажа, приводит к ситуации «2 ореха, 6 этажей» и общему результату 4 броска. Первый бросок, произведенный со 2-го этажа, сводит задачу к случаям «1 орех, 1 этаж» и «2 ореха, 5 этажей» с общим ответом 4 броска. Первый бросок, произведенный с 3-го этажа, приводит к случаям «1 орех, 2 этажа» и «2 ореха, 4 этажа»; общим ответом снова оказывается «4 броска». Дальнейшее увеличение номера этажа, с которого обезьяна совершает первое скидывание, бессмысленно. И правда, по лемме 1 задача «1 орех, k этажей» решается за k бросков, а значит, при k > 3 нам понадобится слишком много попыток. Итого, для решения задачи «2 ореха, 7 этажей» обезьяне понадобится 4 броска.

Последнее соображение наводит на важную мысль: поскольку задача «2 ореха, 6 этажей» решалась за 3 попытки, для решения задачи «2 ореха, 7 этажей» осмысленно рассматривать возможность совершения первого броска сразу с 3 этажа. Действительно, чем выше этаж, с которого обезьяна делает первый бросок, тем меньше надо будет бросков в том случае, если орех после этого броска не расколется. Однако совершать бросок с 4 этажа уже невыгодно, поскольку если орех разобьется, то для удовлетворения любопытства всего обезьяне потребуется, вообще говоря, не меньше 4 бросков.

Пусть теперь мы знаем, что задача «2 ореха, (n − 1) этаж» решается за m попыток. Тогда при решении задачи «2 ореха, n этажей» первый бросок надо совершить с m этажа. В том случае, если орех расколется, задачу «1 орех, (m − 1) этаж» мы решим за (m − 1) бросок, а значит, все сведется к случаю, когда орех останется целым, то есть к задаче «2 ореха, (n − m) этажей». Делать первый бросок с более высокого этажа неразумно, поскольку если орех разобьется, то согласно лемме 1 мы заведомо не узнаем ответ на интересующий нас вопрос быстрее, чем за (m + 1) попытку. А кидать первой попыткой орех с более низкого этажа невыгодно, так как тогда нам надо будет решать более сложную задачу в том случае, если он не расколется.

Итог этих рассуждений подведем в лемме.

Лемма 2. Пусть для решения задачи «2 ореха, (n − 1) этаж» нужно m бросков. Тогда для решения задачи «2 ореха, n этажей» также нужно m бросков тогда и только тогда, когда задача «2 ореха, (n − m) этажей» решается не более чем за (m − 1) бросок.

Проиллюстрируем работу леммы 2 на примерах. Как мы выяснили выше, задача «2 ореха, 7 этажей» решается за 4 броска. Значит, для решения задачи «2 ореха, 8 этажей» также нужно 4 попытки. В самом деле, это следует из леммы 2, так как 8 − 4 = 4, а задача «2 ореха, 4 этажа» решается за 3 броска. Аналогично, трех попыток достаточно для 5 и 6 этажей, откуда следует, что за 4 броска обезьяна удовлетворит свое любопытство в задачах «2 ореха, 9 этажей» и «2 ореха, 10 этажей». А вот для 7 этажей нужно уже 4 попытки, а значит, в задаче «2 ореха, 11 этажей» потребуется 5 бросков.

Проводя такие рассуждения, легко убедиться, что 5 бросков хватит, если в доме 12, 13, 14 или 15 этажей.

Таким образом, ответ на основную задачу легко найти, последовательно применив лемму 2 к домам все более высокой этажности. Если в доме 1 этаж, то обезьяне нужен 1 бросок. Когда дом двухэтажный или трехэтажный, достаточно 2 бросков. Если этажей 4, 5 или 6, то нужно 3 броска. Если в доме от 7 до 10 этажей, то требуется уже 4 броска. Наконец, для домов с 11–15 этажами (как в нашем случае) необходимо 5 бросков. При этом последовательность бросков для 15-этажного дома однозначно определена схемой, представленной ниже. На схеме в белых квадратах указаны этажи, с которых обезьяна должна в очередной раз скинуть кокосовый орех, красная стрелочка соответствует случаю, когда орех раскололся, а синяя — случаю, когда орех остался цел. Первый бросок следует сделать с 5 этажа, дальнейшие броски нужно совершать согласно схеме. Тогда число в желтом квадрате, к которому в итоге обезьяна придет, и будет ответом на ее вопрос.

Итак, ответ: 5 бросков.

Естественным образом возникающий после решения задачи вопрос заключается в том, как изменится результат, если обезьяне удастся раздобыть не 2, а, скажем, 3, 5 или 10 кокосовых орехов, а бросает она их не из 15-этажного дома, а из 100-этажной или даже 1000-этажной башни. Иными словами, вопрос заключается в том, каким будет ответ в общем случае, пусть даже нам удастся вывести его лишь приблизительно.

Итак, допустим, в распоряжении обезьяны имеется k одинаковых кокосовых орехов. Сколькими попытками она может гарантированно обойтись, чтобы определить, с какого самого низкого этажа n-этажного дома нужно бросить кокосовый орех, чтобы он разбился?

Ясно, что при n = 1 достаточно одного броска, сколько бы орехов у обезьяны ни было. При увеличении значения n на 1, как мы могли видеть ранее, число необходимых бросков либо также увеличивается на 1, либо остается неизменным. Например, при переходе от n = 1 к n = 2 (и от n = 3 к n = 4) оно увеличивается, а при переходе от n = 2 к n = 3 — нет (если только k ≠ 1, конечно). Ключевой момент, таким образом, состоит в определении закономерности, когда это число увеличивается, а когда — нет.

Рассмотрим набор функций gk(m) натурального аргумента m, заданных согласно следующему правилу: gk(m) = n в том случае, если n — это максимальное количество этажей в доме, для которого обезьяне гарантированно хватит m бросков, чтобы удовлетворить любопытство (при условии, что в распоряжении обезьяны имеется ровно k кокосовых орехов). Иными словами, равенство gk(m) = n означает, что задача «k орехов, n этажей» решается за m бросков, а задача «k орехов, (n + 1) этаж» — уже за (m + 1) бросок. Наша ближайшая цель — попытаться найти формулу для gk(m) при всех возможных k.

Как легко видеть, из леммы 1 вытекает, что g1(m) = m. Для других значений k выписать явный вид функции оказывается не так просто, однако удается получить некоторое рекуррентное соотношение. При этом помогает то же самое соображение, что и в доказательстве леммы 2: если задача «(k + 1) орех, n этажей» решалась за (m + 1) бросок, то при решении задачи «(k + 1) орех, (n + 1) этаж» первый бросок стоит совершить с (gk(m) + 1)-го этажа. Действительно, тогда исходная задача распадется на две: «k орехов, gk(m) этажей» (решается за m бросков) и «(k + 1) орех, (n − gk(m)) этаж». Последняя задача решается за m бросков в том случае, когда n − gk(m) ≤ gk+1(m). Следовательно, оптимальным значением будет n = gk+1(m) + gk(m), что в свою очередь означает, что gk+1(m + 1) = n + 1 = gk+1(m) + gk(m) + 1. Учитывая, что gk(1) = 1 для всех k, найденную формулу можно переписать следующим образом:



Ввиду важности полученных результатов, оформим их в виде леммы.

Лемма 3. а) gk+1(m + 1) = gk+1(m) + gk(m) + 1. б) gk+1(m + 1) = (gk(1) + gk(2) + ... + gk(m)) + (m + 1).

Теперь, когда в нашем распоряжении имеются рекуррентные соотношения для gk(m), найти явные формулы для этих функций оказывается посильной задачей. Действительно,

http://elementy.ru/images/problems/monkey_..._problem_f2.jpg

Аналогичным образом, по индукции, можно доказать следующие формулы более общего вида:

http://elementy.ru/images/problems/monkey_..._problem_f3.jpg

При выводе этих формул помогают следующие соображения:

http://elementy.ru/images/problems/monkey_..._problem_f4.jpg

и то же самое в общем случае:

http://elementy.ru/images/problems/monkey_..._problem_f5.jpg

Обладая формулами для gk(m), мы можем дать удовлетворительный ответ на поставленный нами вопрос. В самом деле, нам нужно узнать по числу этажей n количество необходимых бросков m. Функция gk(m) в определенном смысле осуществляет обратную операцию: с ее помощью по заданному числу бросков m мы можем определить промежуток, для любого числа этажей n из которого ответ на задачу «k орехов, n этажей» будет составлять ровно m бросков. Так как при каждом k функция gk(m) представляет собой многочлен степени k, то при больших значениях m она ведет себя примерно как mk/k!. Это означает, что для достаточно большого числа этажей n обезьяна, обладающая k кокосовыми орехами, удовлетворит свое любопытство примерно за http://elementy.ru/images/problems/monkey_...problem_f6a.png бросков.

Напротив, для малых значений n наблюдается совершенно другая картина. Если орехов достаточно много для того, чтобы обезьяна могла не бояться, что они кончатся в самый неподходящий момент, то можно спокойно воспользоваться идеей двоичного поиска. В этом случае обезьяне оказывается достаточно ([log2 n] + 1) бросков.

http://elementy.ru/problems/843

Это сообщение отредактировал barsik - 7.02.2015 - 13:12