— Знаешь, Чип, ребята жалуются, что в последнее время наши игры стали скучнее. То ли дело, говорят, поющие поросята или 512 невест — было и смешно, и интересно. Что нам делать?
— А что тут поделаешь! Наверное, ребята правы: любая игра рано или поздно наскучит. Вот я скоро поеду путешествовать — тут уж будет о чем рассказать.
— Ну давай все-таки поиграем, ну хоть в крокет. Кстати вот уж где алгоритма не надо: гоняй себе шар по площадке, пока все ворота не пройдешь, только знай не промахнись.
Конечно, Сережа нарочно дразнил Чипа — ему очень нравилось, когда тот входил в азарт. И Чип попался на удочку.
— Это говорит программист?! Да ты что, не знаешь, что вся наша жизнь состоит из алгоритмов, не только твой дурацкий крокет? А что касается крокета, это частный случай знаменитой проблемы коммивояжера: как выбрать кратчайший маршрут через заданные точки. Для коммивояжера (бродячего торговца) это города на карте, для крокетиста — ворота на площадке.
— Ну и как выбрать этот маршрут?
— Самый короткий маршрут очень сложно выбирать, если я начну объяснять, мы с тобой последних читателей растеряем. Есть простой алгоритм выбора достаточно короткого маршрута без повторений и самопересечений. Уж так вышло, что этот алгоритм в стихах. Слушай:
— Ну как? — спросил Чип, как всегда, гордясь своим литературным упражнением.
— Да не очень... То есть стихи мне понравились, — спохватился Сережа, — только непонятно, что делать, когда будет много ворот. Вот когда одни ворота, тут все ясно: пройди их и катись в противоположный угол. Ну, когда трое ворот, тоже просто — дели площадку на три и по очереди проходи каждую...
— А ты понял, как именно проходить каждую из трех площадок? Ведь у каждой площадки есть по две диагонали, и мы их выбираем так, чтобы вместе получился зигзаг ADCB. Иначе пришлось бы делать лишнюю работу — перекатывать шар впустую из угла в угол.
— Ну, а если будет 9 ворот, тогда я, кажется, тоже понимаю, — подхватил Сережа. — Делю всю площадку на три по трое ворот и поочередно прохожу каждую своим маленьким зигзагом. А вместе получается большой зигзаг. Вот смотри, я его нарисовал. Ага, вот почему ты указываешь два угла: начальный и конечный — чтобы проходить площадку зигзагом, друг за другом: от A к D, от D к C, от C к B. А что ты будешь делать, если число ворот не делится на три?
— Тогда можно оставить в двух площадках поровну ворот, а в третьей — на одно или на два меньше Конечно, в конце концов мы дойдем до пустых площадок, но их, я полагаю, сможет пройти любой крокетист и без моих подсказок, пусть только идет по нужной диагонали. Но вообще-то ты прав — это упущение в программе, надо было написать про пустые площадки. Пусть ребята это условие впишут в нашу стихотворную программу.
Сереже очень понравился алгоритм рекурсивного крокета, и он его в своем кружке запрограммировал для настоящего компьютера. Посмотрите, как нарисовал компьютер крокетный маршрут через пятьдесят ворот. А какую программу напишете вы?
Чип и Сережа ждут, что вы пришлете свои программы и на конверте поставите девиз «Крокет».
ОТ РЕДАКЦИИ:
На время Чип расстается с нами, ребята. Он едет в США работать над советско-американским проектом «Фобос». Обещал Сереже писать письма. Когда Сережа получит эти письма, мы их напечатаем.