Текст книги "Игры с Чипом"
Автор книги: Пионер Журнал
Соавторы: Александр Мигдал
сообщить о нарушении
Текущая страница: 7 (всего у книги 9 страниц)
Двоичный поиск и влюбленный принц
– Апчхи! Ну и пылища! – возмутился Чип, как всегда, появляясь из калькулятора. – Ты что, переезжать собрался?
– Нет, у меня генеральная уборка, – вздохнул Сережа. – Ну и скучное же дело! Особенно перебирать шкафы. Я ведь хотел как быстрее: книжки забросил в один, одежду в другой, дверцы прикрыл и пошел гулять. Так бабушка шкафы открыла и заставила перекладывать: чтобы все книги стояли по порядку – по теме, по году издания, по размерам. И с одеждой тоже: сначала маленькая, потом побольше, потом совсем большая – папина... Жуть! И так можно все найти, если постараться: залез, разрыл кучу, нужную вещь вытянул. Пока все книги расставишь, они так надоедят, что больше их читать не захочется.
– Не огорчайся. Даже в такой простой жизненной ситуации можно увидеть интересную задачу и придумать красивый алгоритм. А заодно и понять, почему проще постоянно поддерживать порядок, чем наводить его раз в месяц.
– Какой уж тут алгоритм! Знай рассовывай по шкафам тряпки... Апчхи! Апхчи!
– Замечательный алгоритм быстрой сортировки. Если у тебя есть, например, пятьсот книг, то он ускорит твою работу в тридцать раз. Давай только начнем издалека. Рассмотрим такую задачу: приятель позвал тебя в гости, номер квартиры сказал, а этаж назвать забыл. Предположим, что он живет в очень высоком, скажем, стоэтажном, доме, где на каждом этаже разное число квартир.
– В Эмпайр-Стейт-Билдинг?
– Пусть там. По числу этажей и количеству почтовых ящиков на первом этаже ничего сказать нельзя. Как бы ты стал искать своего друга?
– По запаху! Раз он меня пригласил, значит, у него пахнет чем-то вкусным, – засмеялся Сережа. – А если говорить серьезно, я бы, наверное, доехал на лифте до верхнего этажа и стал бы спускаться вниз, проверяя номера на дверях.
– И сколько переходов с этажа на этаж тебе бы потребовалось?
– Ну, – задумался Сережа,– если в доме сто этажей и квартира может оказаться на любом, то в худшем случае я осмотрю все сто, а в среднем, наверное, этажей пятьдесят.
– А я утверждаю, что квартиру твоего друга можно найти не более чем за семь проверок. Помнишь стишок про степени двойки?
– Ты хочешь сказать, что два в седьмой – 128? Но при чем тут это?
– А как чипы справились с Мегафлопом, ты помнишь? Для того чтобы нескольким чипам быстро сложить много чисел, эти числа разбивались на пары, и каждую пару суммировал свой чип, потом суммы снова разбивались на пары и так далее, пока не оставалась сумма всех чисел. Тогда сто чисел мы бы сложили за семь шагов. Если нарисовать график такого суммирования, то получится что-то вроде дерева. А теперь попробуй перевернуть его головой вниз.
– Постой, постой, я, кажется, понял, – обрадовался Сережа. – Мы так определяли день рождения друга. Я должен поехать на пятидесятый этаж, посмотреть там номер квартиры и, если он больше, чем у моего приятеля, поехать вниз, на 25-й, а если меньше, то на 75-й, там опять посмотреть номер квартиры и так далее. Тогда можно за семь шагов найти друга даже в доме со 128 этажами.
– Молодец! – обрадовался Чип. – Вот ты сам придумал алгоритм двоичного поиска. А теперь попробуй написать программу. Давай воспользуемся командой:
ПОВТОРЯЙ, ПОКА ВЕРНО УСЛОВИЕ ((БЛОК)) [7]7
БЛОК – это любой набор команд, а двойные скобки нужны, чтобы видеть, где он начинается, а где кончается.
[Закрыть].
Сережа поднатужился и начал писать, косясь при этом на дверь: вдруг войдет бабушка и задаст ему нагоняй за то, что он отлынивает от уборки?
Программа:
1. ВЕРХНИЙ ЭТАЖ = 128.
2. НИЖНИЙ ЭТАЖ = 0.
3. Читай из записной книжки номер квартиры друга.
4. Повторяй, пока ВЕРХНИЙ ЭТАЖ выше НИЖНЕГО.
((СРЕДНИЙ ЭТАЖ = (ВЕРХНИЙ + НИЖНИЙ) : 2.
если ДРУГ живет на СРЕДНЕМ этаже, то КОНЕЦ,
если ДРУГ живет выше СРЕДНЕГО, то НИЖНИЙ этаж приравниваем к СРЕДНЕМУ,
иначе ВЕРХНИЙ приравниваем к СРЕДНЕМУ.))
– Ишь ты, ни одной ошибки, – сказал Чип, заглянув в листок, – не зря ты учишься в кружке программистов.
– Только какое это имеет отношение к уборке? – отложив ручку, спросил Сережа.
– Самое прямое! – успокоил его Чип. – Давай разберем еще одну задачку. Ты читал сказку Шарля Перро «Золушка»?
– Спрашиваешь!
– Тогда ты, конечно, помнишь, что принц приказал мерить туфельку всем девушкам королевства. Сначала принцессам, потом герцогиням, потом придворным дамам... А теперь посчитаем. Во Франции порядка миллиона девушек нужного возраста. Если каждая будет мерить туфельку хотя бы в течение минуты, то вся процедура примерки займет около трех лет, и это при условии, что принц будет работать не покладая рук день и ночь. Только сказочная любовь может выдержать подобное испытание. А теперь предположим, что мы с тобой советники короля. Если бы девушек можно было построить, но не по росту, а по размеру ноги, что бы ты предложил принцу?
– Я предложил бы ему объявить по радио, чтобы все девушки измерили свои ноги с точностью до миллиметра и позвонили бы во дворец...
– Это нечестно. Ты же знаешь, что в те сказочные времена не было ни радио, ни телефонов и даже портновский сантиметр был редкостью. Нет, единственный выход – мерить туфельку на ногу.
– Да ведь это та же самая задача! – воскликнул Сережа, немного подумав.
– Я бы...
– Тсс! Пусть лучше ребята пришлют нам программу поиска Золушки. Я думаю, что без нашей помощи принц ее просто не найдет, и сказка кончится плохо!
– Ну, хорошо, а как же построить девушек по размеру туфельки?
– Это могут сделать придворные дамы. Представь, что мы уже построили девушек, и тут пришла еще одна. Тогда нам надо найти двух девушек, стоящих одна за другой, чтобы у одной из них размер ноги был меньше, чем у новенькой, а у другой – больше. Ты понимаешь, как эта задача связана с двумя предыдущими?
– Конечно, нужно только изменить программу. Но ведь придворных дам много. Нельзя ли эту задачу как-нибудь распараллелить?
– Молодец! Не думал я, что ты догадаешься. Но пусть ребята поломают над этой задачей головы сами, а я дам только легкий намек. Предположим, что мы разделили девушек на 2 группы и каждую из них построили. Если ты, используя предыдущие задачи, придумаешь, как соединить эти два строя, ты найдешь самый быстрый метод сортировки, который называется метод «вставок-слияний». А тогда ты не только поможешь королевской женитьбе, но и быстро справишься с генеральной уборкой.
ОТ РЕДАКЦИИ.
Ребята, поможем Сереже решить задачу Чипа? Пришлите нам свои программы, а на конверте напишите: "Где Золушка?» Лучшие программы мы напечатаем.
Бурная жизнь Фатландии
– Чип, давай во что-нибудь поиграем. – предложил Сережа своему другу, – только на этот раз давай играть по-честному)
– А я всегда играю честно! – возмутился Чип. – Жульничать умеет только очень большой компьютер, да и то с помощью программы искусственного интеллекта. А нам, маленьким машинкам, это просто не по силам.
– Ты только не обижайся, пожалуйста, – спохватился Сережа, – я просто имел в виду такую игру, где шансы у противников одинаковые. Помнишь, как мы с тобой играли в спички? Если один из игроков умеет пользоваться числами Фибоначчи, то он всегда выигрывает. И как только секрет разгадан, играть становится неинтересно.
– Понимаю, ты хочешь, чтобы я показал тебе игру без выигрышной стратегии?
– Да. что-нибудь вроде шахмат, шашек или крестиков-ноликов на бесконечном поле, только новенькое.
– Ну, для крестиков-ноликов выигрышная стратегия есть, при правильной игре всегда побеждает крестик. Только алгоритм не такой простой, как в игре со спичками или в игре «орел-решка». Он придуман в Японии, занимает три увесистых тома и состоит в переборе большого числа позиций. Это больше похоже на математическое доказательство, а не на руководство к действию.
– А что за выигрышный алгоритм в игре «орел-решка»?
– Очень простой: не играть вообще.
– Чип, а есть машины, которые умеют играть в крестики-нолики по выигрышному алгоритму?
– Не знаю, но если у какого-нибудь трудолюбивого японца и хватит терпения запихнуть этот многотомный труд в программу, с таким компьютером никто не станет играть. Интересно иметь дело с противником, который играет немного лучше или немного хуже тебя, пускается в авантюры, выдает красивые идеи и вообще думает как-то по-человечески...
– Ну вот, Чип, опять ты сказки рассказываешь! Разве может машина придумать что-нибудь сама? Она знает только то, что есть в программе.
– Не совсем так. Например, для шашек уже существует программа, думающая, «как человек». Ее идея в том, чтобы компьютер все время учился: после каждого хода сравнивал результаты своих прошлых прогнозов с тем, что на самом деле происходит, и в следующий раз делал более точные прогнозы. Такие прогнозы заменяют ему перебор ходов: он посмотрит несколько ходов вперед, а дальнейшие варианты предугадывает. После каждого хода он прогнозирует все лучше и лучше. Ему ничего не стоит хранить в памяти все сыгранные партии и извлекать из них уроки.
– А как он это делает? Ведь алгоритм прогноза надо было написать заранее?
– Что-то, конечно, надо было написать заранее, в этом и состоит искусство программиста, но можно сделать так, чтобы программа сама себя исправляла.
– Ладно, хватит, Чип, я устал от разговоров. Давай все-таки поиграем.
– Хорошо, давай сыграем в машинную игру под названием «Жизнь». Условия игры такие. Колония бактерий живет на бескрайних просторах Фатландии. Предположим, что эта страна разбита на клетки, как листок из тетради. В каждой клетке только одна бактерия. Соседями одной клетки считаются все клетки, расположенные рядом по горизонтали, вертикали и диагонали. Мерой времени у нас служит смена поколений бактерий, и колония будет жить по таким законам:
1. Если у клетки меньше двух соседей, то бактерия в ней гибнет от скуки.
2. Если у клетки больше трех соседей, то бактерия в ней гибнет от тесноты.
3. Если у пустой клетки ровно три соседа, то в ней рождается новая жизнь.
Только не применяй эти правила поочередно к каждой клетке, бактерии рождаются и гибнут по общему сигналу.
– Постой, постой, я не успеваю, – перебил его Сережа, – давай посмотрим историю жизни какой-нибудь одной колонии. Пусть у нас будет колония из трех бактерий
– Применяй наше правило. У самых крайних клеток по одному соседу, значит, они погибнут от скуки. У средней клетки два соседа, она не погибнет. Теперь рассмотрим те клетки, которые выше и ниже средней. У них по три соседа. Значит, в каждой из этих клеток в следующем поколении возникает по бактерии.
– Чип, постой. Я не понимаю. Ведь та клетка, которая была сбоку, умерла, значит, у верхней средней клетки нет трех соседей.
– Я же сказал, они умирают и рождаются только по общему сигналу, в Фатландии жесткий порядок. Ты сначала найди все возможные изменения в своей колонии, а потом уж разом меняй.
– Понял, понял. Тогда в следующем поколении наша колония станет такой:
а потом опять
и так далее.
– Молодец! А колония
вообще никогда не меняется, но в Фатландии случаются и более невероятные приключения. Поиграй, например, с обыкновенным крестиком
если ты хорошо подумаешь, то поймешь, что через четыре хода он превратится в четыре таких же.
– Чип! А давай напишем программу для «жизни»!
– Давай, только пусть это будет не простой подсчет соседей, а программа, которая ищет игровые ситуации. Например, если колония зациклится (повторит прошлое состояние), то пусть программа на это отреагирует.
Сережа подумал и написал программу. И машина выдала по этой программе вот такую серию картинок.
ОТ РЕДАКЦИИ:
Ребята! А вам такое задание: на листе бумаги в клеточку ноликами нарисуйте первую букву своего имени (такую форму будет иметь ваша колония бактерий) и продолжите историю развития этой колонии. Самую интересную историю мы напечатаем. На конверте поставьте девиз: «Жизнь».
Чип и Сережа читают ваши письма
– Чип! Посмотри, как много у нас новых друзей! – обрадовался Сережа, глядя на стол, заваленный письмами. Он взял наугад несколько конвертов: Мурманск, Одесса, Хабаровск, Ленинград, Киев... – Вот бы съездить ко всем этим ребятам в гости!
– На это тебе не хватило бы даже летних каникул, – засмеялся Чип. – Только на конкурс «Турнир »пришло 602 письма. Кстати, вот задача. Наверняка есть ребята, которые прислали нам по нескольку писем – ответы на различные конкурсы. Как нам найти их ответы в этой груде?
– Разве это задача, – сразу ответил Сережа. – надо рассортировать конверты с фамилиями авторов по алфавиту. А алгоритм быстрой сортировки мы уже знаем, помнишь историю про принца и Золушку?
– Помню, а вот какую программу ты бы написал для нашей задачи?
Сережа немного подумал и написал такую программу:
1. Взять мешок, о котором М писем.
2. Рассортировано 0 писем.
3. Повторяй, пока рассортировано меньше, чем М писем.
4. Возьми из мешка письмо.
5. Вставь в список новое письмо.
6. Конец.
Подпрограмма: «Вставь в список »(новое письмо)
1. Верхний = 0
2. Если рассортировано 0 писем, перейди к строке 7.
3. Нижний = длине списка.
4. Средний = (Верхний + Нижний): 2
5. Если фамилия > Среднего, то
Нижний = Среднему,
иначе
Верхний = Среднему.
6. Если Верхний > Нижнего + 1, переходи к 4-й строке.
7. Вставить фамилию после Верхнего.
8. Длина списка увеличилась на единицу.
9. Возврат.
– Все правильно, – сказал Чип, проверив программу, – только ты ведь не знаешь, сколько в мешке писем. Поэтому лучше будет, если ты напишешь третью строчку программы так:
3. Повторяй пока в мешке есть письма:
И еще хорошо бы вставить в блок между четвертой и пятой строчками строку: «Прочитать письмо ». Кстати, именно таким способом я и воспользовался, когда разбирал нашу почту.
Очень много откликов пришло на задание найти алгоритм Евклида. Правильные ответы прислали: Сергей АЛЕКСЕЕНКО из Хабаровска; Дима АПУХТИН, Челябинск; Люда БРЫНЬ, г Мена; Лена ГЕРАСИМОВА, Одесса; Саша ЗАВОРИН, п. Победа; Олеся КОСТЕНКО, Севастополь; Оля МАЗЕПА, Волжский; Лена МАЙОРОВА, Килок; Саша МАРТЫНЕНКО, Киев; Лена МОСТОЛЬСКАЯ, Москва; Наташа МУСИЕНКО, Похвистнев; Света НЕРЫДАЕВА, Ярославль; Туля ПУЗАТОВА, д. Б. Когульбаева; Таня РАМЕНСКАЯ, с. Рогачево; Аня САМАРОВА. Москва; Алена ТАРАСОВА, Ижевск; Оксана ТЮНИКОВА, Омск; Оля УСАЧЕВА, Донецк; Нина ШЕВЧЕНКО, Иркутск; Юра ЮРЬЕВ, Москва.
Гораздо сложнее оказалось помочь электронному мальчику с пальчик выйти из болота. С этой задачей из 90 претендентов лучше всех справились Алеша АЛЕКСЕЕВ, Уфа; Витя РЫЖАКОВ, Томск и Дима СОСУЛЯКИН, Новокузнецк. Программы которые они предложили, очень похожи и выглядят примерно так.
1. Возьми три веревки, привяжи к колышку.
2. Трем братьям отойти в разные стороны.
3. Выбрать верхнего.
4. Всем переместиться к выбранному брату и забить там колышек.
5. Если не вышли из болота – возврат к 1.
Подпрограмма: «Выбрать верхнего».
1. Посмотреть на веревки.
2. Если одна выше остальных – выбрать этого брата.
3. Если все на одном уровне – жди утра.
– По-моему, – сказал Сережа, – все трое допустили небольшую ошибку. Чтобы выйти из трясины, нам надо найти не брата, стоящего выше всех, а место, которое выше, чем то, где забит колышек. Возможно, что одна веревка будет выше других, но все братья будут находиться ниже колышка. Тогда мы не только не выйдем из трясины, но, наоборот, завязнем еще глубже. Программу «Выбери верхнего» я бы написал так:
1. Посмотри на веревки.
2. Если есть хоть одна, идущая вверх, то
выбери самую верхнюю,
иначе
жди утра
3. Возврат.
– Правильно, Сережа, я бы даже усилил твое утверждение и написал: «Если есть хоть одна, идущая не вниз» – зачем ждать утра, если есть возможность испробовать еще один вариант, оставаясь на том же уровне.
– Посмотри, Чип, вот сюжеты электронных игр, целых семьдесят писем.
– С этим заданием лучше всех справились Никита ЛИТВИНЕНКО, Краснокаменск и Ира РЯБЫХ, п. Ларба. Пятиклассник Никита предложил игру «Леопольд, выходи!» и даже нарисовал картинку. Сюжет игры такой: две мыши, которыми управляют с помощью клавиш компьютера, дразнят кота Леопольда и прыгают через кнопки, лежащие на дороге. Если мышка приземлится на кнопку, раздается громко «Ай!» (современные компьютеры уже умеют разговаривать), и игрок получает штрафное очко. Дорога с кнопками может двигаться быстрее или медленнее. Поскольку мышек две и они прыгают независимо друг от друга, управлять ими будет не просто, такая игра потребует хорошей координации движений и быстрой реакции.
– Чип, а помнишь того сердитого читателя из Свалявы? Он писал, что мы даем слишком простые задачи. Ему предложили более трудное задание и попросили написать на конверте: «Чип, это я».
– Конечно, помню. Письма из Свалявы мы, правда, пока не получили, зато вон лежат семь писем из разных уголков страны с надписью «Чип, это я». Не знаю, что хотели сказать их авторы, но, к сожалению, в этих письмах нет ни слова о сложном задании, просто ответы на конкурс «Турнир». Кстати, с этим конкурсом справились многие ребята. Правильные ответы прислали Дима АНТОНОВ, Пермь. Ярослав ВЕРБЕ, Киев; Паша ДАНИЛОВ, Загорск; Юра ДУКАЧ, Экибастуз; Саша ЕЛЕСЕЕВ, Ростов-на-Дону; Алексей ЕРОХИН, Марганец; Дима ЗАЙЦЕВ, Апатиты; Кирилл ИЛЬИН, Ленинград; Саша КОНЕВ, Курчатов; Сергей КОРОВЯКОВСКИЙ, Мурманск; Роман КАЛИНА, Оренбург; Таня КРЕСТОВСКИХ, Ухта; Лена МАТАШКОВА, Витебск; Слава НИКОЛАЕВ, с Новомихайловское; Игорь ПЕРМИНОВ. г. Ступино; Алеша МАЛЬКОВ, г. Шимановск; Ольга Л., с. Вихоревка; С. РАССТРИГИН, Рязань; Юра ПЕТРАШОВ, Тольятти; Женя СЕРГУНОВ, Юрга; Дима СУТОРИН, Пермь; Яна СУХОРУКОВА, Красноярск; Оля СИЛИНА, Юрьев-Польский; Ольга ШЕПТАЛИНА, Балашиха; Эльвина ЮНУСОВА, Уфа.
Много программ на бейсике, программ для микрокалькуляторов прислали наши читатели на задание «Турнир». Больше всех постарался Станислав Расстригин: он прислал программы на трех языках – бейсике, алголе и рапире. Игорь Перминов из Ступина на базе нашего задания придумал сюжет электронной игры «Турнир».
– Чип, а давай предложим тем читателям, кто занимается в кружках программирования, усложнять для себя наши задания. Пусть записывают программы на машинных языках или придумывают на основе этих программ электронные игры.
– Конечно, если наши задания кому-то кажутся слишком простыми, их надо использовать как отправную точку для самостоятельной работы.
В поисках выхода
– Чип, а как поживает электронный Мальчик с пальчик? – спросил Сережа. – Расскажи мне про него еще какую-нибудь историю!
– Ладно, – ответил Чип, – только я буду рассказывать, а ты писать программы. Согласен?
– Согласен. – обрадовался Сережа. – Начинай!
– Итак, как-то ночью, когда все инженеры спали, в электрическую сеть прокрался страшный Скачок Напряжения и напал на чипов. Сам Мальчик с пальчик почти не пострадал, его спасли друзья – предохранители, а вот у его старшего брата сгорела вся оперативная память. Жалко стало Мальчику с пальчик братца – теперь тому прямая дорога в демонтаж. И решил он пойти на поклон к великану Гигабайту: ему что проглотить, что отдать пару килобайт – раз плюнуть.
Мама с папой стали Мальчика с пальчик отговаривать:
– Не ходи – и брату не поможешь, и сам пропадешь. Построил себе Гигабайт из каналов и контролеров страшный лабиринт. Кто в этот лабиринт заходит, того великан съедает, а если и не съест тебя Гигабайт, то все равно заблудишься, закружишься в бесконечном цикле, не найдешь обратной дороги.
– Ничего, – отвечает Мальчик с пальчик, – мы с Гигабайтом старые знакомые, один раз я его уговорил, уговорю и в другой.
Взял он узелок, положил туда пару батареек и отправился в путь. Долго ли, коротко плутал по лабиринту, но наконец нашел Гигабайта. Увидел его великан, разинул пасть...»
– Постой, постой. – перебил Чипа Сережа, – это мне напоминает историю про Тесея и Минотавра, я ее читал в «Легендах и мифах Древней Греции». Только ты забыл про Ариадну, которая дала Тесею моток ниток. Он привязал один конец у входа, а потом, когда убил злого Минотавра, по нитке нашел дорогу назад.
– Молодец, – похвалил Чип Сережу, – как раз в нитке все и дело. Герою Тесею, который хорошо умел только махать мечом, нитка действительно была необходима. А наш электронный Мальчик с пальчик выйдет из лабиринта без всякой нитки. Так что это не совсем та же история.
– Извини, Чип, – спохватился Сережа, – рассказывай дальше.
«– А, это ты, малявка, – загрохотал великан, – зачем пожаловал? Тебя съесть – только аппетит раздразнить.
– Будь добр, дай мне пару килобайт оперативной памяти вылечить братца. Для тебя это мелочь, а ему без них один путь – на свалку.
– Ха-ха-ха, мелюзга, да если я тебе даже дам пару килобайт, все равно из лабиринта не выберешься. Я и сам не знаю, как отсюда выйти.
– А вот и выйду, – засмеялся Мальчик с пальчик. – Я знаю алгоритм выхода из любого конечного плоского лабиринта. Раз я сюда пришел, то хоть один выход из твоего лабиринта есть, так что можешь обо мне не беспокоиться, дорогу я найду.
– Ну-ка, расскажи свой алгоритм, – заинтересовался Гигабайт, – а потом прогуляемся вместе наружу. Если выберемся – подарю тебе не два килобайта, а целых десять.
– Алгоритм очень прост, называется «Правило правой руки». Смотри: я кладу мой узелок и иду вперед вдоль правой стены. Как только встречаю развилку, поворачиваю направо. При таком алгоритме я не могу зациклиться – начать ходить по кругу, потому что, если бы я начал ходить по кругу, это бы говорило о том, что я выбирал все время не самый правый коридор. – И Мальчик с пальчик начертил на песке такой рисунок (рис. 1). – Поэтому правильный обход дал бы следующий результат (рис. 2)».
– Постой, – опять не выдержал Сережа, – а если сразу справа от тебя вот такой замкнутый коридор (рис. 3), то ты зациклишься!
– Ты невнимательно слушал. Мальчик с пальчик ясно сказал: «Кладу мой узелок». Ведь если у лабиринта нет выхода, алгоритм тоже не приведет к успеху, поэтому он и уточнил: «Раз я сюда пришел, то хоть один выход есть» (рис. 4). Поэтому, наткнувшись на свой узелок, он поступит следующим образом: возьмет его, у ближайшей развилки выберет не самый правый, а второй справа коридор (рис. 5), ведь из развилки может быть много выходов, и повторит тот же алгоритм: положит узелок, пойдет вдоль правой стенки и так далее. Можно доказать, что если выход есть, то мы его обязательно найдем. А теперь попробуй написать программу выхода из лабиринта.
Вот что после некоторого раздумья написал Сережа:
ПРОГРАММА: «НАЙТИ ВЫХОД».
1. Возьмись правой рукой за стену.
2. Положи узелок у этой стены.
3. Иди по правилу «правой руки» (ситуация).
4. ЕСЛИ ситуация-выход, ТО КОНЕЦ.
ИНАЧЕ:
((5. Возьми узелок.
6. Иди вдоль правой стены до первой развилки.
7. Войди во второй справа коридор.
8. Вернись ко второму пункту программы.))
ПОДПРОГРАММА «ИДИ ПО ПРАВИЛУ» ПРАВОЙ РУКИ» (ситуация).
1. Иди вдоль правой стены до развилки.
2. ЕСЛИ увидел узелок у правой стены, ТО
((ситуация-цикл
ВОЗВРАТ)).
3. Выбери самый правый коридор.
4. ЕСЛИ выход, ТО
((ситуация-выход
ВОЗВРАТ)).
5. Выполняй первый пункт подпрограммы.
– Хорошо, – сказал Чип, – а теперь давай попробуем применить твою программу. Вот в журнале «Веселые картинки» напечатан лабиринт. Давай поищем путь от крота к мышке.
Вот по какому пути шли Сережа с Чипом. Если смотреть сверху, то путь может показаться не самым коротким: зачем обходить явные тупики и заворачивать во все закоулки? Но зато этот путь они прошли, как бы находясь в лабиринте, двигаясь ощупью в полной темноте, и все-таки выбрались наружу.
ОТ РЕДАКЦИИ:
Ребята! Проверьте Сережину программу на других лабиринтах. А если лабиринтов под рукой не найдется, придумайте их сами и пришлите нам. Любителям трудных задач мы предлагаем сочинить программу, которая сама будет строить лабиринты. На конверте напишите девиз: «ЛАБИРИНТ».
