Задачиcегодня задач в базе - 1448

Задача 435. "Стеклянные шары" все задачи

Код для вставки в блог


Код вставки в блог | Результат

Скопируйте готовый код используя комбинацию клавиш Ctrl+C.

Есть два одинаковых стеклянных шара и один 100 этажный дом. Известно, что шары начинают разбиваться при ударе о землю, падая с определенного этажа. Как определить минимальное количество сбрасываний этих шаров с различных этажей, за которые можно гарантированно найти этот самый этаж?
Читать полностью
02.02.2013

Автор текста: 

Есть два одинаковых стеклянных шара и один 100 этажный дом. Известно, что шары начинают разбиваться при ударе о землю, падая с определенного этажа. Как определить минимальное количество сбрасываний этих шаров с различных этажей, за которые можно гарантированно найти этот самый этаж?

 

Источник: Творческое объединение «Полет мысли» (г. Челябинск)

(Голосов: 0, Рейтинг: 0)
   


Добавить решение/комментарий:

Решения и комментарии:
  • Сергей В|03.02.2013|

    ответ 19 проходим дом с шагом 10, потом проходим подблоки обоснование минимальности на основе того, что А*(Б+1)=100 (тут +1 из-за того, что при проходе через Н этажей в блоке остается Н-1 этажей)и А+Б=min. имеет решение при А=10, Б=9

  • семь (применим дихотомический поиск: сначала середина здания (этаж 50), если шар разбился, спускаемся ниже, на 25-й, если не разбился - поднимаемся на 75-й, и т.д.).

  • TyxTyx|06.02.2013|

    Дихотомия сработает, если шаров семь или больше. Пусть они разбиваются, если их сбросить с третьего. Первый разобьётся на 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 раз.