Разбивать на блоки - плохо, потому что когда простреливаемый ящик меняется, мы можем захватить ящик из другого блока. Для слышащей на 1 ящик - просто. N-1 выстрела - и готово (даже быстрее, чем для полностью глухой!) А вот при N=2 - где-то в промежутке. Перебор руками тяжелый - вариативность слишком высокая.Versus писал(а):Для глухой крысы, видимо, придётся разбить всё пространство на блоки, ограниченные радиусом слуха крысы. И простреливать их по очереди в определённом порядке. Но тут надо ещё подумать надо оптимизацией процесса.
Ловля крыс
Модераторы: Азарапетыч, Администрация
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Ловля крыс
Re: Ловля крыс
Про блоки это я погорячился. Очень хотелось свести задачу к уже решённой по пути наименьшего сопротивления.
Хочу прояснить пару моментов по терминологии:
"Нечётной" называется движущаяся (то есть, наш следующий выстрел заставит крысу двигаться) крыса, удалённая от точки стрельбы на нечётное число ящиков.
"Чётной" называется движущаяся крыса, удалённая на чётное число ящиков.
При последовательном расстреле ящиков чётность крысы не меняется. Значит, нечётная крыса всегда проскочит под пулей, а чётная будет убита.
Смысл любой тактики двойным выстрелом в один и тот же ящик поменять чётность крысы и пристрелить её. Крыса с радиусом слуха 1 всегда нечётная (либо мёртвая).
Если мы приближаемся последовательно к радиусу слуха крысы, то её чётность будет зависеть от чётности радиуса. При чётном значении радиуса, крыса будет чётной, а при нечётном - нечётной. Соответственно, крысу с чётным радиусом мы всегда убьём за один проход, а нечётная всегда ускользнёт за пределы радиуса, а когда снова попадёт в него, то снова будет нечётной. Поэтому для крысы с нечётным радиусом требуется тактика двойных выстрелов, второй выстрел в дуплете либо убивает крысу, либо меняет её чётность. И стрелять приходится в каждый ящик со второго по предпоследний, так как мы ничего не знаем о первоначальном расположении крысы.
Крысу с чётным радиусом можно было бы убить за один проход, если бы мы точно знали, что она не слышит первого выстрела. Но существует вероятность, что первый выстрел будет внутри радиуса слуха такой крысы. При этом она может сидеть через нечётное число ящиков (и стать нечётной). В таком случае при последовательной стрельбе слева направо крыса либо выйдет за пределы радиуса слуха и автоматически станет чётной позже, либо мы поменяем её чётность, стрельнув дуплетом в предпоследний ящик, и убьём на обратном пути. В любом случае потребуется те же 2*(n-2) выстрелов для гарантированной дератизации ящиков.
Встаёт следующий вопрос. Можно ли уменьшить число выстрелов, если мы изначально не знаем, глухая ли крыса и насколько она глухая.
Что-то меня терзают смутные сомнения насчёт N-1 выстрела. Крыса, как только слышит выстрел в соседнем ящике, либо перебегает в тот ящик, в который мы только что стреляли, либо убегает дальше, загоняя себя в тупик. Значит единственная тактика - это тактика Шшока (дублировать выстрел в каждый ящик), иначе проскочит на уже зачищенную территорию. В результате приходим к тем же 2*(n-2), только с другого боку.Dendr писал(а):Для слышащей на 1 ящик - просто. N-1 выстрела - и готово (даже быстрее, чем для полностью глухой!) А вот при N=2 - где-то в промежутке. Перебор руками тяжелый - вариативность слишком высокая.
Хочу прояснить пару моментов по терминологии:
"Нечётной" называется движущаяся (то есть, наш следующий выстрел заставит крысу двигаться) крыса, удалённая от точки стрельбы на нечётное число ящиков.
"Чётной" называется движущаяся крыса, удалённая на чётное число ящиков.
При последовательном расстреле ящиков чётность крысы не меняется. Значит, нечётная крыса всегда проскочит под пулей, а чётная будет убита.
Смысл любой тактики двойным выстрелом в один и тот же ящик поменять чётность крысы и пристрелить её. Крыса с радиусом слуха 1 всегда нечётная (либо мёртвая).
Если мы приближаемся последовательно к радиусу слуха крысы, то её чётность будет зависеть от чётности радиуса. При чётном значении радиуса, крыса будет чётной, а при нечётном - нечётной. Соответственно, крысу с чётным радиусом мы всегда убьём за один проход, а нечётная всегда ускользнёт за пределы радиуса, а когда снова попадёт в него, то снова будет нечётной. Поэтому для крысы с нечётным радиусом требуется тактика двойных выстрелов, второй выстрел в дуплете либо убивает крысу, либо меняет её чётность. И стрелять приходится в каждый ящик со второго по предпоследний, так как мы ничего не знаем о первоначальном расположении крысы.
Крысу с чётным радиусом можно было бы убить за один проход, если бы мы точно знали, что она не слышит первого выстрела. Но существует вероятность, что первый выстрел будет внутри радиуса слуха такой крысы. При этом она может сидеть через нечётное число ящиков (и стать нечётной). В таком случае при последовательной стрельбе слева направо крыса либо выйдет за пределы радиуса слуха и автоматически станет чётной позже, либо мы поменяем её чётность, стрельнув дуплетом в предпоследний ящик, и убьём на обратном пути. В любом случае потребуется те же 2*(n-2) выстрелов для гарантированной дератизации ящиков.
Встаёт следующий вопрос. Можно ли уменьшить число выстрелов, если мы изначально не знаем, глухая ли крыса и насколько она глухая.
- Slavaa
- Писатель на заборах
- Сообщения: 119
- Зарегистрирован: 29 сен 2008, 18:41
- Пол: Мужской
- Откуда: С-Петербург
Re: Ловля крыс
Стреляем во вторуую - крыса точно не в первой
Еще раз во вторую - она не в первой и не второй
После двух раз по третьей - и не в третьей
таким образом делаем по 2 выстрела по каждой коробке, кроме первой и последней
итого 1996
Еще раз во вторую - она не в первой и не второй
После двух раз по третьей - и не в третьей
таким образом делаем по 2 выстрела по каждой коробке, кроме первой и последней
итого 1996
- maksim82
- Популярный автор
- Сообщения: 1813
- Зарегистрирован: 28 июн 2005, 17:28
- Пол: Мужской
- Откуда: Москва
Re: Ловля крыс
Когда начинаем стрелять по третей, крыса перебегает во 2-ю. После 2-го выстрела по 3-ей она перебегает в 1-ю.Slavaa писал(а):Стреляем во вторуую - крыса точно не в первой
Еще раз во вторую - она не в первой и не второй
После двух раз по третьей - и не в третьей
таким образом делаем по 2 выстрела по каждой коробке, кроме первой и последней
итого 1996
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Ловля крыс
Дважды во вторую:Versus писал(а):Что-то меня терзают смутные сомнения насчёт N-1 выстрела.
с первого выстрела либо убьем крысу из второго ящика, либо заставим крысу из 1-го перебежать во второй, либо из 3-го в 1-й, либо из 3-го в 4-й. Если рыса в 4-м или дальше, она стоит на месте.
со второго - либо стреляем в пустой, либо убиваем крысу
Результат - крысы точно нет в первых трех ящиках
Дважды в 4-й - аналогично, итого - нет в первых пяти.
И так далее.
- Slavaa
- Писатель на заборах
- Сообщения: 119
- Зарегистрирован: 29 сен 2008, 18:41
- Пол: Мужской
- Откуда: С-Петербург
Re: Ловля крыс
Когда начинаем стрелять по третей, крыса перебегает во 2-ю. После 2-го выстрела по 3-ей она перебегает в 1-ю.
А откуда она перебежит во вторую???
Если она точно не в перввой, то только из третьей и мы убъем ее когда выстрелим по третьей
А откуда она перебежит во вторую???
Если она точно не в перввой, то только из третьей и мы убъем ее когда выстрелим по третьей
- maksim82
- Популярный автор
- Сообщения: 1813
- Зарегистрирован: 28 июн 2005, 17:28
- Пол: Мужской
- Откуда: Москва
Re: Ловля крыс
Каждая итерация состоит из двух событий: выстрел и перемещение крысы.Slavaa писал(а):Когда начинаем стрелять по третей, крыса перебегает во 2-ю. После 2-го выстрела по 3-ей она перебегает в 1-ю.
А откуда она перебежит во вторую???
Если она точно не в перввой, то только из третьей и мы убъем ее когда выстрелим по третьей
Итерация 1 (И1). Выстрел во 2 коробку (2К) гарантирует, что в начале И2 К1 будет пуста
Итерация 2. Выстрел снова в К2 нам опять гарантирует пустоту К1, но, поскольку после выстрела следует перемещение крысы, это нам не гарантирует пустоту К2 в начале следующей итерации.
Короче, алгоритм по 2 выстрела подряд в каждую коробку не катит. Думайте дальше.
- ХМАО
- Писатель на заборах
- Сообщения: 154
- Зарегистрирован: 24 апр 2009, 21:15
- Пол: Мужской
- Откуда: ХАНТЫ-МАНСИЙСК
Re: Ловля крыс
Очень внимательно прочитал условия задачи и комментарии к ней.
Вот алгоритм дейсвий стрелка-радиста, при количестве ящиков равного ПЯТИ:
(1,2,3,4,5) 2 (2,3,4,5) 3 (1,3,4,5) 4 (2,4) 4 (1,3) 3 (2) 2.
Но дело в том, что если бы мы убили крысу, то об этом не узнали бы.
Значит необходимо загнать уже мертвую крысу в тот ящик, в котором она(крыса) навернека будет(но об этом мы опять не узнаем.
Вот алгоритм дейсвий стрелка-радиста, при количестве ящиков равного ПЯТИ:
(1,2,3,4,5) 2 (2,3,4,5) 3 (1,3,4,5) 4 (2,4) 4 (1,3) 3 (2) 2.
Но дело в том, что если бы мы убили крысу, то об этом не узнали бы.
Значит необходимо загнать уже мертвую крысу в тот ящик, в котором она(крыса) навернека будет(но об этом мы опять не узнаем.
- ХМАО
- Писатель на заборах
- Сообщения: 154
- Зарегистрирован: 24 апр 2009, 21:15
- Пол: Мужской
- Откуда: ХАНТЫ-МАНСИЙСК
Re: Ловля крыс
Не понял!
А куда делся АВТОР, этой классной головоломки.
А куда делся АВТОР, этой классной головоломки.
Re: Ловля крыс
Может не париться и пальнуть вдоль ряда через все коробки разом?
- maksim82
- Популярный автор
- Сообщения: 1813
- Зарегистрирован: 28 июн 2005, 17:28
- Пол: Мужской
- Откуда: Москва
Re: Ловля крыс
Ну дык все же вроде правильно)) то же самое, когда коробок 1000.ХМАО писал(а):Не понял!
А куда делся АВТОР, этой классной головоломки.
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Ловля крыс
Эк вас.ХМАО писал(а):Не понял!
А куда делся АВТОР, этой классной головоломки.
Насчет автора понятия не имею. Американец какой-нибудь.
Спросите у Генриха Лиговского - я задачку у него на форуме "стырил".
Re: Ловля крыс
Я тут слеганца, извиняюсь, что поднял тему трехлетней давности.
Вдруг кто вспомнит эту задачу. Так вот, тугоухая на 3 ящика крыса все же не прибивается. Никак.
Доказано для количества ящиков от 8 до 15 программно перебором всех вариантов.
Живучая, гадина.
Вдруг кто вспомнит эту задачу. Так вот, тугоухая на 3 ящика крыса все же не прибивается. Никак.
Доказано для количества ящиков от 8 до 15 программно перебором всех вариантов.
Живучая, гадина.
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!