1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

Задачка про стеклянные шары

Тема в разделе "Высшее образование", создана пользователем Cray, 11.10.06.

  1. Cray

    Cray Активный участник

    1.802
    0
    Для любителей нестандартных задачек.

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

    Например, с одним шаром он может бросить его с первого этажа, потом со второго, и т.д., т.е. надо 100 бросаний.
     
  2. Teacher

    Teacher Участник

    408
    0
    вроде (n+2)/2
    т.е. сначала бросаем со 2-го этажа, Возможно 2 варианта:
    1) разбился -> тогда бросаем с первого
    2) не разбился. -> тогда бросаем с 4-го.
    Если с 4-го разбился, то бросаем с 3-го (для контроля)
    Если не разбился - идем на 6-ой и т.д.
    итого получаем что если шар разобется на n ом этаже, то надо сделать (n+2)/2 попытку.

    Оговорюсь: надо рассмотреть верхний предел, но сейчас мозги туго будут сображать
     
  3. Arturvn

    Arturvn Активный участник

    6.269
    68
    14 бросков
     
  4. Teacher

    Teacher Участник

    408
    0
    получается 51
     
  5. AlTk

    AlTk Читатель

    10.699
    0
    Teacher, а можно и так:
    шаг избрать не 2 а Х, тогда получается:
    бросаем с этажа Х*K, где 1 <= K <= (100/X), K - целое. если разбился, то второй шар бросаем поочередно с этажей X*(K-1) + I, 1 <= I < X? пока не разобьется.
    в самом худшем случае надо сделать (X+100/X) бросков.
    теперь берем производную, находим минимум. ответ готов.

    ПС. мог напутать с +-1.
     
  6. Ivan

    Ivan Werewolf

    9.054
    3
    Бросить шар с середины здания, допустим, с 50 этажа. Если разбился, то тогда начинать с первого этажа, и бросать до тех пор, пока не разобъется. Если не разбился, то подняться на 75-ый, и бросить оттуда. Если не разбился, то оставшееся расстояние опять поделить на 2, и вычислить сегмент. Если разбился, то пройти снизу оставшийся сегмент.
     
  7. AlTk

    AlTk Читатель

    10.699
    0
    Ivan, в твоем случае понадобится 50 попытка (если шарик разбивается при броске с 49 этажа).
    в моем решении Х=10, следовательно количество попыток равно 20.
     
  8. Arturvn

    Arturvn Активный участник

    6.269
    68
    Ivan,
    а если кинешь с 50 разобьется и кинешь с 25 тоже разобьется... что дальше делать шаров то 2 всего...

    В случае с двумя шарами 100-этажное здание можно гарантированно промерить за 14 бросков. Делается это так: первый шар сбрасывается с 14-ого этажа, далее, если не разбивается, с этажа номер 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Определенный таким образом промежуток, в котором разбивается шар, последовательно промеряется вторым шаром.
    Иначе говоря, вначале мы зондируем здание первым шаром с шагом, уменьшающимся на единицу, начиная с 14. То есть номер этажа для сбрасывания определяется последовательным суммированием 14 + 13 + 12 + 11 + ... Каждый бросок первым шаром отнимает у нас один ход, потому следует уменьшать на один и количество этажей для промера вторым шаром. В итоге сумма бросков первым и вторым шаром не превысит 14 и мы точно определим искомый этаж.
    За N бросков таким способом можно гарантированно промерить N + (N-1) + ... + 3 + 2 + 1 = N*(N+1)/2 этажей. При N=13 это 91 этаж, а при N=14 уже 105
     
  9. AlTk

    AlTk Читатель

    10.699
    0
    Arturvn, хитро
    "... потому следует уменьшать на один и количество этажей для промера вторым шаром ..."
    об этом я не подумал.
     
  10. Agnus

    Agnus Активный участник

    1.477
    0
    фигасе академики)))
     
  11. Cray

    Cray Активный участник

    1.802
    0
    Arturvn, быстро нашел праильный ответ, даж обидно.