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