Задача
Три прямолинейных коридора одинаковой длины d образуют фигуру, изображенную на рисунке 1.
Рис. 1.
По коридору перемещаются гангстер и полицейский, причем максимальная скорость полицейского в 2 раза выше максимальной скорости гангстера. К сожалению, коридоры длинные, а полицейский обладает ограниченной дальностью обзора — он сможет увидеть гангстера, только если окажется от него на расстоянии не более 1.
Придумайте алгоритм, позволяющий полицейскому поймать гангстера: а) при d = 3; б) при d = 4,999; в) при любом d < 7.
Три прямолинейных коридора одинаковой длины d образуют фигуру, изображенную на рисунке 1.
Рис. 1.
По коридору перемещаются гангстер и полицейский, причем максимальная скорость полицейского в 2 раза выше максимальной скорости гангстера. К сожалению, коридоры длинные, а полицейский обладает ограниченной дальностью обзора — он сможет увидеть гангстера, только если окажется от него на расстоянии не более 1.
Придумайте алгоритм, позволяющий полицейскому поймать гангстера: а) при d = 3; б) при d = 4,999; в) при любом d < 7.
Данилишина Дарья 8-ХБ
ОтветитьУдалитьа)d=3
Пусть полицейский начинает движение из точки A к центру( O ), затем проходит некоторое расстояние по коридору OB и возвращается обратно в O.
Значит, после того как полицейский попал в коридор OB на глубину 2 и вернулся в O можно утверждать, что гангстер находится именно в OC. Мы понимаем, что его нет в коридоре OB, так как, пройдя в OB расстояние d − 1 = 2, полицейский увидел конец коридора. Гангстер не мог успеть за это время выскочить из коридора OC в коридор OA и оказаться там на таком расстоянии, на котором его из точки O не увидит полицейский, потому что вначале он находился на расстоянии больше 1 в коридоре OC, в конце должен оказаться на расстоянии больше 1 в коридоре OA, а значит, должен пройти больше чем 2. За то время, пока полицейский ходил в коридоре ОB, гангстер мог пройти расстояние не больше чем половина пути полицейского, то есть (2 + 2)/2 = 2.
б) d=4,999
Для решения пункта б) полицейскому нужно продолжать погоню — сначала пройти в коридор OC на расстояние 3, чтобы в момент возвращения точно понимать, что гангстер не успел перебежать из OB в OA так как для этого ему необходимо было пройти расстояние, большее 4, за то время, пока полицейский проходил 2 + 3 + 3 = 8, а это невозможно с его скоростью.
Поскольку полицейский уверен, что в коридоре OC гангстера нет до расстояния 3 + 1 = 4, то должно быть выполнено условие (3 + x + x)/2 < 4 + 1, то есть x < 3,5. Пройдя до x = 3,5 в коридор OB, полицейский уже знает, что в этом коридоре гангстера нет на расстоянии до x + 1 = 4,5, поэтому глубина y следующего погружения в коридор OC может быть такой, чтобы выполнялось неравенство (3,5 + y + y)/2 < 4,5 + 1, то есть y < 3,75.Мы видим, что глубины прохождения полицейского (поочередно в коридоры OB и OC) образуют последовательность 2, 3, 3,5, 3,75.
Мы можем указать ф-лу задающую члены этой послед.. Если на некотором(n) шаге полицейский зашел в один из коридоров на расстояние a(n), то гангстера в этом коридоре нет до расстояния a(n) + 1, а значит, следующее прохождение полицейского в соседний коридор может иметь глубину a(n + 1), чтобы (a(n) + a(n + 1) + a(n + 1))/2 ≤ a(n) + 2. Отcюда выплывает, что a(n + 1) = (a(n) + 4)/2.
Тоесть каждая следующая точка вдвое ближе к 4, чем предыдущая. Но это означает, что расстояние до 4 (которое в начале равнялось 2), в каждом следующем погружении сокращается вдвое, 4 − a(n) = 2/2n, a(n) = 4 − 2/2n. Теперь нам понятно что начиная с некоторого n значение a(n) окажется больше чем 3,999, а значит, этого хватит для того, чтобы поймать гангстера в коридоре длиной d = 4,999.
в)......