Есть два стеклянных шарика и 100–этажный дом.
Шарики никогда не бьются, если их бросать с высоты, меньшей чем k–ый этаж, а выше – бьются. (Физические условия – упрощенные: количество падений не влияет на способность шариков выдерживать падения.) Найти минимальное число «бросаний» b, которых будет всегда достаточно, чтобы опытным путем найти номер «рокового» этажа k. (Шары, можно бросать по одному.)
Решение этой задачи в два счета можно найти в сети.
Теперь, имеем n этажей в небоскребе…
(дальше – внутри)

размер 400x393, 59.91 kb

GD Star Rating
loading...

10 Responses to Найти минимальное число «бросаний»

  1. Elova:

    Решение с n этажами не попалось на глаза, но его можно вывести, исходя из формулы для суммы первых i членов арифметической прогрессии.
    Ответов не пишу, ибо, вдруг кому–то будет интересно её решить.
    (По просьбе вышлю в пост, или это тут называется.)
    А вот теперь — самое интересное: n этажей и m шаров.
    Знает кто решение?

  2. _mj:

    ищи сразу для случая, когда шары выдерживают только f падений с суммарной высотой падений в z этажей, при условии, что в каждый из s небоскребов экспериментатора пустят не более d раз, — чего по сто раз пересчитывать, когда можно решить общую задачу один раз.

  3. Elova:

    не… количество небоскребов вводить бессмысленно… ))) потому и рассмешили…
    что до предельного количества падений, то мы и так стремимся уменьшить его, потому такое ограничение только сделает задачу, либо решаемой, либо нет, но на алгоритм поиска не повлияет. А вот с ростом числа шаров достаточное число испытаний за счет увеличения количества допустимых «промахов» можно сократить.

  4. AkMoon:

    29 бросаний?

  5. AkMoon:

    Я искал к–тый этаж так:
    кидал одновременно 2 шарика. Один с n–ого этажа, другой с (n+*)–этажа.
    Т.е. кидаю шар с х этажа, если разбился то ищу в {1,..,*} этажах, если нет то делаю как написано выше с n=*+1, получается один шарик с *+1, другой с 2х+1. В наихудшем варианте у нас получится
    [(100–х)*2/х + 1] бросаний.
    Теперь на каком–то шаге мы опеределили промежуток этажей, длиной х, в которым нужный нам этаж. Причем остался один шарик. будем последовательно идти вверх, потребуется х бросаний.
    Нужен максимум функции (100–х)*2/х + 1 + х

    пересчитал, получилось 26
    мой ответ : от 26 до 29

  6. Haun:

    На собеседовании как–то спросили. Помню что у меня получилось 13 бросаний вроде с уменьшающимся шагом.
    То есть первое через 13 этажей, если не разбилось то ещё через 12 (на 25–м), далее 36 итд.
    Ход решения щас не воспроизведу.

  7. Elova:

    меньше чем 26

  8. Elova:

    больше чем 13

  9. Haun:

    14, я идиот )

  10. Elova:

    Для 100 этажей 14–ти бросаний хватит в любом случае.

    Для n этажей : Image #703045, 459 Bytes

    Где:
    k(500)=32
    k(1000)=45
    k(10000)=141

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