Имеется два одинаковых стеклянных шарика, а также стоэтажное здание. На каждом этаже есть балкон, с которого шарик можно сбросить. Если один шарик разбивается, то можно использовать второй. Как определить с помощью минимального количества бросков самый низкий этаж, при падении с которого шарик точно разбивается? Минимальное количество бросков нужно определить и предложить алгоритм действий.
Ответ
И ещё - головоломка про радиоактивность.
update
Первый - svarog_777.Ответ
Первый шарик бросаем последовательно с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 и 100 этажей. Если на каком-то из этих этажей шарик разбивается, то второй шарик начинаем бросать с этажа, который на один выше, чем был на предыдущем шаге. Если второй шарик не разбивается, то поднимаемся вверх на один этаж. И так далее пока второй шарик не разобьётся. Этаж на котором разобьётся второй шарик и будет искомым. Например, бросаем первый шарик с 14-го этажа - не разбивается, бросаем его же с 27-го этажа - разбивается, тогда второй шарик начинаем бросать с 15-го (14+1) этажа, с 16-го, с 17-го и т.д. пока не разобьётся. Максимальное количество попыток при таком подходе 14.
И ещё - головоломка про радиоактивность.
два, один с первого второй с последнего?
ОтветитьУдалитьДопустим первый шарик остался целым, второй разбился. Как мы определим самый низкий этаж, с которого шарик начинает разбиваться?
Удалитьну тогда кидаем с 1-ого не разбился, поднимаемся на 3-ий кидаем, если разбился кидаем с 2-го, если не разбился поднимаемся на 5-ый и так далее.
УдалитьНо только это всё относительно, так как раз на раз не приходится.
Для этого алгоритма худший случай когда шарик разбивается на 99 этаже. Потребуется 50 попыток. Есть более оптимальные варианты.
УдалитьПонимание динамического программирования и одного состояния (хранить в линейном массиве).
ОтветитьУдалитьМне нравится вариация (http://neerc.ifmo.ru/school/archive/2005-2006.html#team-rus задача H.), Количество шариков лежит в интервале от 1 до 6. Не разбившиеся объекты можно поднять с земли. Нужно минимизировать количество подъемов вверх по этажам (спуски вниз за неразбившимися шариками не учитываются, подниматься вверх - тяжело).
Собственно, тоже динамическое программирование. Но состояние будет 5-ти-мерным.
Тут учитывается только количество попыток. Подъёмы и спуски не берём в расчёт. Так какой же ответ?
Удалитьчестно не вычислял, но логика примерно така если с 50-го кидать
ОтветитьУдалитьто можно залететь на 50+1 попытку = 51
с 20-го, то 5+19 = 24 и т.д.
вобщем с 10 -го если кидать
получается где то 10+8 попыток = 18раз. То есть кинули с 10 го разбился. Еще 8 попыток, начиная со 2-го этажа и если разобьется на 9-ом этаже. Если на 10-м не раблися то с 20-го кидаем и в случае разрушения, кидаем 2-ой с 12-го. Если, гад, бьется на 99-ом, то 18 попыток.
Есть вариант с ещё меньшим количеством попыток.
Удалитьтааак...
ОтветитьУдалитькидаем с 15(можем попасть на 13+1 попыток в случае разбиения)
кидаем с 30(15 попыток)
кидаем с 45(16 попыток можем получить)
кидаем с 55(на 9+3 попыток)
кидаем с 65(13 попыток)
кидаем с 75(14)
кидаем с 85(15)
кидаем с 95(16)
кидаем с 100(4+7 = 11 попыток)
итого максимально могли получить 16 попыток при таком способе
Ошибочка на 95 этаже 17 попыток. Вобщем 17 конечный ответ.
ОтветитьУдалитьМожно сделать ещё меньше.
Удалитьесли с 14-го, то чтобы не увеличить количество попыток в дальнейшем будем уменьшать каждый раз шаг!
ОтветитьУдалить1 бросок с 14 го этажа, если разбили то 13+1 попытка
потом с 27 этажа, если разбили то 2 + 12 попытка
39 то 3+11 попыток
50 этаж
60
69
77
84
90
95
99 - если вдруг разбивается с 99-го то 11 попыток вообще
если 100 - то 12.
При таком раскладе за 14 можно уложиться.
возможно такое линейное увеличение не оптимально, может надо как то шаг оптимизировать...
или просто какой то подвох!
физика задействована типа gt^2/2 ?
У меня такой же ответ - 14 попыток!
Удалитькак не крути - но попыток только 13
ОтветитьУдалить