Игры с Чипом

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

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

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

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

ОТ РЕДАКЦИИ.

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

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

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

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

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

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

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

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

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

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

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

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

— А ты понял, как именно проходить каждую из трех площадок? Ведь у каждой площадки есть по две диагонали, и мы их выбираем так, чтобы вместе получился зигзаг ADCB. Иначе пришлось бы делать лишнюю работу — перекатывать шар впустую из угла в угол.

— Ну, а если будет 9 ворот, тогда я, кажется, тоже понимаю, — подхватил Сережа. — Делю всю площадку на три по трое ворот и поочередно прохожу каждую своим маленьким зигзагом. А вместе получается большой зигзаг. Вот смотри, я его нарисовал. Ага, вот почему ты указываешь два угла: начальный и конечный — чтобы проходить площадку зигзагом, друг за другом: от A к D, от D к C, от C к B. А что ты будешь делать, если число ворот не делится на три?

— Тогда можно оставить в двух площадках поровну ворот, а в третьей — на одно или на два меньше Конечно, в конце концов мы дойдем до пустых площадок, но их, я полагаю, сможет пройти любой крокетист и без моих подсказок, пусть только идет по нужной диагонали. Но вообще-то ты прав — это упущение в программе, надо было написать про пустые площадки. Пусть ребята это условие впишут в нашу стихотворную программу.

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

Чип и Сережа ждут, что вы пришлете свои программы и на конверте поставите девиз «Крокет».

ОТ РЕДАКЦИИ:

На время Чип расстается с нами, ребята. Он едет в США работать над советско-американским проектом «Фобос». Обещал Сереже писать письма. Когда Сережа получит эти письма, мы их напечатаем.

В ожидании Чипа

Об электронных переводчиках и лучших портных Кливленда

Сколько бы теперь ни набирал Сережа на калькуляторе 1234 + 5678, Чип больше не появлялся. Далеко был Сережин дружок, в Америке, в городе Сан-Диего. Он улетел в США работать над советско-американским космическим проектом «Фобос». Сережа уж весь атлас исползал, а нашел Сан-Диего. Оказывается, он в штате Калифорния, почти на самой границе с Мексикой и в то же время на берегу Тихого океана.

«Ах, Чип, Чип. Что же ты не пишешь? А ведь обещал. Я так привык к тебе», — думал Сережа.

Забросив атлас, Сережа пошел в папин кабинет посмотреть, нет ли чего почитать про Чипову жизнь и жизнь его братии. Вообще-то шарить на папином столе Сереже не разрешалось. Но сегодня он нарушил запрет и, аккуратно приподняв бумаги, исписанные быстрым папиным почерком, вытянул несколько номеров журнала «В мире персональных компьютеров».

Усевшись в кресло, Сережа погрузился в чтение. Текст был научный, сложный, но кое-что интересное Сережа все-таки вычитал.

Оказывается, в Англии разрабатывается устройство автоматического перевода речи с одного языка на другой. Установлено оно будет на телефонных линиях. Англичанин сможет понять японца, хотя каждый из них будет говорить на родном языке. Как работает устройство? К телефону подключается персональная ЭВМ, на экране дисплея появляется текст произносимой фразы. «Переводчик» знает 1000 слов на английском, французском, испанском, японском языках.

Две японские фирмы изобрели щетки, которые моют самолет всего лишь за час. Управляют щетками компьютеры, а обслуживают эту установку, размещенную в одном из аэропортов Токио, всего пять человек.