Скопируйте готовый код используя комбинацию клавиш Ctrl+C.
Есть два одинаковых стеклянных шара и один 100 этажный дом. Известно, что шары начинают разбиваться при ударе о землю, падая с определенного этажа. Как определить минимальное количество сбрасываний этих шаров с различных этажей, за которые можно гарантированно найти этот самый этаж?
Источник: Творческое объединение «Полет мысли» (г. Челябинск)
Подписка на рассылку
ответ 19 проходим дом с шагом 10, потом проходим подблоки обоснование минимальности на основе того, что А*(Б+1)=100 (тут +1 из-за того, что при проходе через Н этажей в блоке остается Н-1 этажей)и А+Б=min. имеет решение при А=10, Б=9
семь (применим дихотомический поиск: сначала середина здания (этаж 50), если шар разбился, спускаемся ниже, на 25-й, если не разбился - поднимаемся на 75-й, и т.д.).
Дихотомия сработает, если шаров семь или больше. Пусть они разбиваются, если их сбросить с третьего. Первый разобьётся на 50ом, второй - на 25ом. Больше шаров нет, а ответ три - не получен. Ответ будет 18, если точно известно, что есть этаж, при сбросе с которого шар разобьётся. Тогда нет смысла бросать с сотого этажа, и потребуется 9 сбросов с шагом 10, и 9 сбросов после.
Меньше 35 сбрасываний ,кажется не получается. 1.Вначале сбросим с 33 этажа,если шар разобьется, то второй следует сбрасывать последовательно ,начиная с первого.Он может не разбиться и с 32 этажа. 2.С 33 этажа не разбился,сбросим с 66 этажа.Если разбился , то сбрасываем последовательно, как и в первом случае ,но начиная с 34 этажа.Всего33+1= 34 сбрасывния. 3.С 66 не разбился , сбросим с 99 этажа.Если разбился , то в худшем случае необходимо еще 32 сбрасывания.Всего33+2= 35 сбрасываний. 4.С 99 не разбился.Сбросим с 100-го.Всего 4 сбрасывания.Минимально необходимиое число-35 раз.