Игры с Чипом

— Так это что, не настоящий Штирлиц?! — возмутился Сережа. — А я-то уши развесил.

— Почему не настоящий, самый настоящий, только он уже на пенсии. Разве не может бывший разведчик поиграть после школы с внуком?

— Ну, допустим, а что за частотная таблица — я ничего не понял.

— Частотная таблица — один из самых важных  инструментов шифровальщика. Возьми любую книгу и посчитай, сколько раз на какой-нибудь странице встречается буква «а», потом на другой странице, на третьей. Ты получишь примерно одинаковые числа. То же самое надо проделать с другими буквами алфавита. Можно посчитать, что любой русский текст состоит на 9,4% из букв «о», на 9% из «а» и так далее. Теперь возьми секретное послание. Мы предполагаем, что оно написано по-русски, перетасованным алфавитом. Посчитаем, какие буквы в нем встречаются и с какой частотой, сравним таблички и....

— Понял! — обрадовался Сережа.

— Только не думай, что все так просто, это ведь статистика, так можно угадать только самые часто встречающиеся буквы, так что тебе придется попотеть. А если остались еще какие-то неясности с частотной таблицей, посмотри рассказ Эдгара По «Золотой жук».

ОТ РЕДАКЦИИ.

Эту задачу мы предложили в письмах семи финалистам конкурса Чипа. Лучше всех справились Саша БАУРОВ и Карапет ОВИВЯН, они и получают калькуляторы фирм «Кассио» и «Электроника» на солнечных батарейках. Победитель шуточного конкурса Олеся МАТВЕЕВА — годовую подписку на «Пионер» 1989 года. А остальные пять претендентов на призовые места — грамоты журнала «Пионер».

Рекурсивный крокет

— Знаешь, Чип, ребята жалуются, что в последнее время наши игры стали скучнее. То ли дело, говорят, поющие поросята или 512 невест — было и смешно, и интересно. Что нам делать?

— А что тут поделаешь! Наверное, ребята правы: любая игра рано или поздно наскучит. Вот я скоро поеду путешествовать — тут уж будет о чем рассказать.

— Ну давай все-таки поиграем, ну хоть в крокет. Кстати вот уж где алгоритма не надо: гоняй себе шар по площадке, пока все ворота не пройдешь, только знай не промахнись.

Конечно, Сережа нарочно дразнил Чипа — ему очень нравилось, когда тот входил в азарт. И Чип попался на удочку.

— Это говорит программист?! Да ты что, не знаешь, что вся наша жизнь состоит из алгоритмов, не только твой дурацкий крокет? А что касается крокета, это частный случай знаменитой проблемы коммивояжера: как выбрать кратчайший маршрут через заданные точки. Для коммивояжера (бродячего торговца) это города на карте, для крокетиста — ворота на площадке.

— Ну и как выбрать этот маршрут?

— Самый короткий маршрут очень сложно выбирать, если я начну объяснять, мы с тобой последних читателей растеряем. Есть простой алгоритм выбора достаточно короткого маршрута без повторений и самопересечений. Уж так вышло, что этот алгоритм в стихах. Слушай:

Пройди по крокетной площадке AB
По правилам этим простым:
Одни лишь ворота попались тебе?
От «A» ты отправишься к ним.
«B »— угол напротив, туда ты спешишь,
Ворота пройдя без помех,
И катится шарик проворный, как мышь.
И близок желанный успех.
А ЕСЛИпопалось побольше ворот,
ТОвсе ж головы не теряй,
Не стой, удивленно разинувши рот,
Площадку на три разделяй.
По длинной, конечно, дели стороне,
Пусть поровну будет ворот,
И тот, кто рекурсию знает вполне,
Зигзагом три части пройдет.
Сначала пройди по площадке AD,
Потом по площадке DC.
CB ты пройди, не запнувшись нигде,
И колышек стукни в конце.
Площадку прошел — ты доволен и рад,
В конце подпрограммы поставишь
ВОЗВРАТ. 

— Ну как? — спросил Чип, как всегда, гордясь своим литературным упражнением.

— Да не очень... То есть стихи мне понравились, — спохватился Сережа, — только непонятно, что делать, когда будет много ворот. Вот когда одни ворота, тут все ясно: пройди их и катись в противоположный угол. Ну, когда трое ворот, тоже просто — дели площадку на три и по очереди проходи каждую...