Игры с Чипом - [32]
— Ну что же, мы с тобой еще не играли в шифры.
— Что, загадывать или отгадывать? — загорелись глаза у Сережи.
— И то, и другое, но только сначала я расскажу тебе одну детективную историю.
«Штирлиц взглянул на часы. Было 12.33, одна минута до условленного времени. Он не отрываясь смотрел в окно вагона, привычно фиксируя отражения. Стрелка солидных швейцарских часов неторопливо прошла еще круг. Он вздохнул, вынул часы из жилетного кармана и переложил в правый карман ватерпруфа. Это был сигнал.
Движение нежной маленькой руки оказалось небрежно, почти незаметно. «Хорошо их учат в этой пресловутой школе», — усмехнулся про себя Штирлиц. Из осторожности он проехал еще одну остановку. Неподалеку от Генерального штаба он присел на скамейку, подождал, пока мимо проковыляла седая дама с ризеншнауцером, и только тогда вынул из кармана записку.
Судя по кириллице и размеру слов, текст был на русском языке, но шифр — новый. «Пожалуй, часа два у меня есть, раньше они не хватятся». Штирлиц любил разгадывать шифры. Частотную таблицу русских букв он помнил наизусть. Оставалось составить такую же таблицу для неизвестного текста и сравнить их. Сообщение получалось довольно странное.
О мядр щзщшпдкф юяфяспд.
— Люп впшпыкю?
— Нфпд.
— Пюлоьз.
— Пю шяыпфеьз.
— Тюп шзм дзьп?
— Чплпфзьз.
— Ьфр лпвп?
— Ьфр нэдз мпявп.
— 3 мдпвп фк ъыкнфзюх?
— Ьз ъоьпш пюзл ърюх
КФК чянюх: Упфхчя ямо дя наянюх: Пд о мядр ябя мзфядхлкг.
Увлекшись, Штирлиц забыл обо всем. В ключе не хватало всего трех букв, когда знакомый голос насмешливо произнес: «Игра окончена, полковник. Разведчик должен уметь проигрывать».
— Дениска, так нечестно! Мы же договорились до трех часов, а сейчас 2.30. Мне же совсем немного осталось!
— Эх, дедушка, как же ты не заметил, что я тебе в метро часы на полчаса назад подвел. А еще бывший разведчик! Ну ладно, ничья, а теперь пошли скорее, я обещал, что мы еще хлеб по дороге купим...».
— Так это что, не настоящий Штирлиц?! — возмутился Сережа. — А я-то уши развесил.
— Почему не настоящий, самый настоящий, только он уже на пенсии. Разве не может бывший разведчик поиграть после школы с внуком?
— Ну, допустим, а что за частотная таблица — я ничего не понял.
— Частотная таблица — один из самых важных инструментов шифровальщика. Возьми любую книгу и посчитай, сколько раз на какой-нибудь странице встречается буква «а», потом на другой странице, на третьей. Ты получишь примерно одинаковые числа. То же самое надо проделать с другими буквами алфавита. Можно посчитать, что любой русский текст состоит на 9,4% из букв «о», на 9% из «а» и так далее. Теперь возьми секретное послание. Мы предполагаем, что оно написано по-русски, перетасованным алфавитом. Посчитаем, какие буквы в нем встречаются и с какой частотой, сравним таблички и....
— Понял! — обрадовался Сережа.
— Только не думай, что все так просто, это ведь статистика, так можно угадать только самые часто встречающиеся буквы, так что тебе придется попотеть. А если остались еще какие-то неясности с частотной таблицей, посмотри рассказ Эдгара По «Золотой жук».
ОТ РЕДАКЦИИ.
Эту задачу мы предложили в письмах семи финалистам конкурса Чипа. Лучше всех справились Саша БАУРОВ и Карапет ОВИВЯН, они и получают калькуляторы фирм «Кассио» и «Электроника» на солнечных батарейках. Победитель шуточного конкурса Олеся МАТВЕЕВА — годовую подписку на «Пионер» 1989 года. А остальные пять претендентов на призовые места — грамоты журнала «Пионер».
Рекурсивный крокет
— Знаешь, Чип, ребята жалуются, что в последнее время наши игры стали скучнее. То ли дело, говорят, поющие поросята или 512 невест — было и смешно, и интересно. Что нам делать?
— А что тут поделаешь! Наверное, ребята правы: любая игра рано или поздно наскучит. Вот я скоро поеду путешествовать — тут уж будет о чем рассказать.
— Ну давай все-таки поиграем, ну хоть в крокет. Кстати вот уж где алгоритма не надо: гоняй себе шар по площадке, пока все ворота не пройдешь, только знай не промахнись.
Конечно, Сережа нарочно дразнил Чипа — ему очень нравилось, когда тот входил в азарт. И Чип попался на удочку.
— Это говорит программист?! Да ты что, не знаешь, что вся наша жизнь состоит из алгоритмов, не только твой дурацкий крокет? А что касается крокета, это частный случай знаменитой проблемы коммивояжера: как выбрать кратчайший маршрут через заданные точки. Для коммивояжера (бродячего торговца) это города на карте, для крокетиста — ворота на площадке.
— Ну и как выбрать этот маршрут?
— Самый короткий маршрут очень сложно выбирать, если я начну объяснять, мы с тобой последних читателей растеряем. Есть простой алгоритм выбора достаточно короткого маршрута без повторений и самопересечений. Уж так вышло, что этот алгоритм в стихах. Слушай:
