Пионер 1988-09, страница 40

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

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

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

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

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

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

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

Пройди по крокетной площадке АВ По правилам этим простым: Одни лишь ворота попались тебе? От «А» ты отправишься к ним. «В» — угол напротив, туда ты

слешишь,

Ворота пройдя без помех, И катится шарик проворный,

как мышь,

И близок желанный успех. А ЕСЛИ попалось побольше ворот, ТО все ж головы не теряй, Не стой, удивленно разинувши рот, Площадку на три разделяй. По длинной, конечно, дели стороне, Пусть поровну будет ворот, И тот, кто рекурсию знает вполне, Зигзагом три части пройдет. Сначала пройди по площадке АД, Потом по площадке ДС. СВ ты пройди, не запнувшись нигде, И колышек стукни в конце. Площадку прошел — ты доволен и рад. В конце подпрограммы поставишь

ВОЗВРАТ.