SINCLAIR LOGO
(Продолжение) Начало см. на с. 69-74, 90-95, 178 - 182.
7. И снова об обработке списков.
Мы уже видели с Вами некоторые процедуры, выдающие какой-то результат и назвали их операциями. С помощью команды OUTPUT Вы можете сами создавать такие операции. В этом случае команда OUTPUT определяет то значение, которое должно быть возвращено в качестве результата. Например, если мы хотим создать процедуру, которой нам не хватает в стандартной версии ЛОГО, такую, которая будет вычислять разность двух чисел аналогично тому, как процедура SUM вычисляет их сумму, то мы делаем так:
ТО DIFFERENCE: NUM1: NUM2 OUTPUT :NUM1 - :NUM2
END
и тогда:
PRINT DIFFERENCE 7 5 даст результат:
2
Когда ЛОГО встречает команду OUTPUT, он передает то значение, которое находится справа от слова OUTPUT и останавливает процедуру. Поэтому DIFFERENCE 7 5 имеет значение 7-5.
Вы можете в одной процедуре иметь несколько команд OUTPUT, но в этом случае они должны стоять в разных ветвях IF, поскольку первая же встреченная команда OUTPUT прервет исполнение процедуры, действительно, нам ведь нужен только один результат ее работы.
Например, Вы можете сделать так, чтобы процедура вычисления разности двух чисел всегда выдавала положительный результат. Для этого надо, чтобы оба числа сравнивались между собой и из большего вычиталось меньшее.
ТО DIFFERENCE :NUM1 :NUM2
IF :NUM1> :NUM2 [OUTPUT :NUM1-:NUM2] OUTPUT :NUM2 - :NUM1
END
PRINT DIFFERENCE 10 3 7
PRINT DIFFERENCE 2 6 4
Можно, конечно, было записать и так:
IF :NUM1> :NUM2 [OUTPUT :NUM1-:NUM2][OUTPUT :NUM2-:NUM1]
но в этом нет особой необходимости, если исполняется первая команда OUTPUT, то и процедура закончится, а до второй команды OUTPUT дело и не дойдет.
Точно так же можно сконструировать и процедуру, выдающую по команде OUTPUT слово или список. Например, мы хотим узнать, начинается ли слово с гласной буквы или нет. Если да, то в качестве артикля перед ним надо ставить по правилам английской грамматики не "А", а "AN".
Поскольку нас интересует только первая буква в слове, то неплохо проверить, не является ли слово пустым списком.
Вот пример, который выдает значение "AN", если слово начинается с гласной, или выдает "А", если слово начинается с иной буквы или выдает пустой символ, если слово -пустое.
ТО ARTICLE :AWORD
IF EMPTYP :AW0RD [OUTPUT "]
IF MEMBER? FIRST :AWORD[A E I O U][OUTPUT "AN]
OUTPUT "A
END
Попробуйте сами изменить процедуру ARTICLE так, чтобы она могла работать не только с прописными, но и со строчными буквами тоже. Бывают случаи, когда операциями надо пользоваться очень осторожно. Прежде всего, некоторые операции могут иметь побочные эффекты, т.е. они могут вести себя как команды. Например, мы можем создать операцию, которая запросит имя пользователя и выдаст первое из введенных в нее слов в качестве результата.
ТО GETNAME
PRINT [WHAT IS YOUR NАMЕ] OUTPUT FIRST READLIST
END
Поэтому:
MA№ "YOU GETNAME даст сообщение
WHAT IS YOUR NAME
и будет ждать ввода с клавиатуры, прежде чем передаст первое прочитанное слово в качестве результата операции. Все это выглядит достаточно просто, но что будет, если Вы попробуете:
PRINT GETNAME
Обратите внимание на то, что внутри процедуры GETNAME тоже имеется команда печати PRINT. ЛОГО вычисляет результат работы процедуры справа налево и потому сначала исполнит GETNAME, а затем передаст результат команде PRINT. То же самое произойдет и в команде:
PRINT SENTENCE "HELLO GETNAME
Здесь и GETNAME и "HELLO обеспечивают входные данные для команды SENTENCE, которая передает свой результат команде PRINT. Попробуйте:
PRINT (SENTENCE GETNAME "ALIAS GETNAME)
и посмотрите, получится ли в итоге именно тот результат, которого Вы ждете. Второй момент, о котором нужно всегда помнить, заключается в том, что всякий раз, когда вызывается исполнение операции, она работает, как в первый раз.
PRINT DIFFERENCE 7 5 2
PRINT DIFFERENCE 7 5 2
Так все и должно быть и ничего иного мы и не ждем (но при многократных повторных вычислениях на это уходит много времени). Сколько бы раз Вы не вызывали GETNAME, эта процедура всегда будет делать запрос и ждать ввода с клавиатуры. Если же Вам надо запомнить то имя, которое было введено в самый первый раз, то Вам надо присвоить его символьной переменной и обращаться к ней всякий раз, когда Вам будет необходимо:
MAKE "YOU GETNAME
PRINT SENTENCE "HELLO :YOU
PRINT SENTENCE [I AM GLAD TO MEET YOU]: YOU
Уровни процедур.
Когда одна процедура вызывает другую, мы говорим, что мы перешли на второй уровень процедуры. Если и эта процедура, в свою очередь, вызывает еще одну, то это уже третий уровень и т. д. Вот, например, три процедуры:
ТО PRОC1
PRINT [LEVEL 1] PROC2
END
TO PROC2
PRINT [LEVEL 2] РRОСЗ
END
ТО PROC3
PRINT [LEVEL 3]
END
Здесь PROC1 - это первый уровень. Когда она вызывает PROC2, мы переходим на второй уровень. Когда же она вызывает PROC3, то это уже третий уровень, после чего Вам надо выполнить три команды END, STOP или OUTPUT, прежде чем мы вновь вернемся на верхний уровень (нулевой уровень).
Нулевой уровень в ЛОГО - это командный уровень, именно на нем Вы находитесь, когда перед Вами на экране изображено приглашение "?". Есть и специальная команда TOPLEVEL, которая позволяет сразу вернуться на верхний уровень, независимо от того, где Вы находитесь. Впрочем, этой командой пользоваться не рекомендуется, разве что в случае крайней необходимости.
Уровень, на котором Вы находитесь, никак не зависит от содержания тех процедур, которые Вы исполняете, а зависит только от того, сколько процедур, вложенных друг в друга, Вы исполнили. Представьте себе, что каждая встреченная на Вашем пути процедура -это ступенька вниз, а каждая встреченная команда END, STOP или OUTPUT - это ступенька вверх. Поэтому, если находясь на самом верхнем (командной) уровне Вы вызовете PROC3, то перейдете на первый уровень, хотя по своему содержанию PROC3 устроена так, что выдаст сообщение <LEVEL3>.
Интересны реккурентные процедуры. Они могут уходить в глубину на очень много уровней.
ТО DOLEVEL :N
PRINT SENTENCE "LEVEL :N IF :N<10[DOLEVEL :N+1]
END
Тогда команда DOLEVEL1 даст следующую печать:
LEVEL1 LEVEL2 LEVEL3 LEVEL4 LEVEL5 LEVEL6 LSVEL7 LEVEL8 LEVEL9
Когда же, в конце концов, N станет равно 10, мы выполним команду END на 9-ом уровне, потом на 8-ом и так далее до верхнего уровня, в этом можно и убедиться самому, если изменить DOLEVEL так:
ТО DOLEVEL :N
PRINT SENTENCE -LEVEL :N IF :N<10 [DOLEVEL:N+1] PRINT "FINISH
END
DOLEVEL 1 LEVEL1 LEVEL2 LEVEL3 LEVEL4 LEVEL5 LEVEL6 LEVEL7 LEVEL8 LEVEL9 FINISH FINISH FINISH FINISH FINISH FINISH FINISH FINISH FINISH
Глобальные и локальные переменные.
Когда слово используется в качестве входного параметра в процедуру (при определении процедуры), тогда при вызове процедуры это слово должно принимать то значение, которое было задано при вводе. Простой пример:
ТО SAYNUM :N
PRINT SENTENCE [N IS] :N
END
И тогда:
SAYNUM 5
дает ожидаемый результат:
N IS 5
Теперь попробуйте так:
MAKE "N 7 SAYNUM 5 N IS 5
А теперь попробуйте:
PRINT N
На этот раз результат будет неожиданным - 7. ЛОГО запомнит то значение, которое имела переменная N до вызова процедуры и отложит его до тех пор, пока процедура не закончится.
Итак, мы можем считать, что переменная N в процедуре SAYNUM является локальной для данной процедуры, т.е. SAYNUM имеет свое собственное значение N, которое может быть использовано только внутри этой процедуры. Те же слова, которые не указаны при определении процедуры в качестве ее параметров, являются глобальными (т.е. значения этих переменных одинаковы во всех частях программы). Отсюда вытекает одно важное следствие для того случая, когда используем несколько уровней вложения процедур. Мы покажем его на примере трех процедур PROC1, PROC2, PROC3. ТО PROC1 :N
PRINT SENTENCE "PROC1 :NUM PROC2 5
PRINT SENTENCE [PROC1 AGAIN] :NUM
END
TO PROC2 :N
PRINT SENTENCE "PROC2 :NUM PROC3 7
PRINT SENTENCE [PROC2 AGAIN] :NUM
END
TO PROC3 :N
PRINT SENTENCE "PROC3 :NUM
END
Здесь процедуры 1 и 2 печатают значение своего параметра прежде, чем вызывать следующую процедуру, поэтому:
PROC1 3 PROC2 5 PROC3 7 PROC2 AGAIN 5 PROC1 AGAIN 3
Итак, ЛОГО "помнит", какому уровню процедур, какое значение NUM соответствует. Проще всего, по-видимому, представлять себе локальные переменные, как совершенно новые переменные, когда Вы находитесь внутри процедуры, несмотря на то, что они могут иметь то же имя, что и переменные, встречающиеся вне этой процедуры.
Если локальная переменная изменяется внутри процедуры, то это не имеет никаких эффектов на все одинаковые переменные вне этой процедуры. Если же изменяется глобальная переменная, то это изменение действует всюду, например:
ТО TEST :NUM
MAKE "NUM :NUM+1 PRINT :NUM
MAKE "OTHER :OTHER+1
END
MAKE "NUM 5
MAKE "OTHER 7
TEST 5
6
PRINT :NUM 5
PRINT :OTHER 8
Это имеет важное значение для рекурсии, Вы можете положиться на ЛОГО, когда он закончит рекуррентную процедуру в том смысле, что ЛОГО "помнит", где он был и каковы были там значения локальных переменных.
Команда OUTPUT для реккурентных процедур.
Вы можете использовать процедуры рекуррентно, поставив в команду OUTPUT имя самой этой же процедуры, но если Вам надо, чтобы эта процедура все-таки закончилась и при этом выдала бы какой-то результат. Вам надо иметь еще хотя бы один OUTPUT, в котором не происходит реккурентного вызова этой процедуры еще раз.
Чтобы все это стало ясным, мы изменим ранее использованную процедуру GETNAME так, чтобы она запрашивала имя пользователя и выдавала бы первое слово введенного имени, если это возможно, а если нет, то печатала бы соответствующее сообщение и вызывала бы саму себя для повторения попытки. Правда, имейте в виду, что это приведет и к повторной печати запроса. Мы не будем здесь пользоваться конструкцией FIRST READLIST.
Поскольку оператор FIRST не любит пустые списки (и это естественно) и потому сначала проверим, не является ли введенный список пустым, а только потом будем к нему применять оператор FIRST.
ТО GETNAME
PRINT [ПОЖАЛУЙСТА НАЗОВИТЕ ВАШЕ ИМЯ] MAKE "YOU READLIST
IF EMPTYP :Y0U[PRINT[Х0ТЯ БЫ ОДНО ИМЯ У ВАС ДОЛЖНО БЫТЬ] MAKE "YOU FIRST :YOU
IF NUMBERP:YOU[HOMEP ВМЕСТО ИМЕНИ БЫВАЕТ ТОЛЬКО У ЗАКЛЮЧЕННЫХ] OUTPUT GETNAME] OUTPUT :YOU
END
Это же можно проиллюстрировать на примере процедуры, входными параметрами которой будут число и слово, а в качестве результата будет слово, в которое будут вводить
столько символов, сколько указано входным числом. Итак:
START 5 "RECURSIVE выдаст
RECUR.
Если :N - это число, а :INWORD - входное слово, то мы хотим получить от него :N первых символов. Теперь мы можем выделить из слова первый символ. После этого можно рекуррентно вызывать процедуру START до тех пор, пока еще не будут выданы :N-1 символов от оставшейся части входного слова :INWORD, т.е.
START :N-1 BUTFIRST :INWORD,
а затем поместить первый символ в новое слово:
WORD FIRST :INWORD
START :N-1 BUTFIRST :INWORD,
после чего выдать его в качестве результата с помощью OUTPUT.
Пока все идет хорошо, но встает традиционный вопрос: "Где же остановить рекурсию?" Поскольку N постепенно уменьшается и указывает на то, сколько еще символов мы хотим получить, то остановиться надо тогда, когда :N равно нулю и выдать "пустое слово" для обеспечения перехода START вверх на предыдущий уровень.
ТО START :N :INWORD IF :N= [О OUTPUT"] OUTPUT WORD FIRST :INWORD START :N-1 BUTFIRST :INWORD
END
PRINT START 5 "RECURSIVE RECUR
Давайте проследим ход работы процедуры с помощью следующей таблицы (табл. 1):
:INWORD
RECURSIVE ECURSIVE CURSIVE URSIVE RSIVE
RSIVE URSIVE CURSIVE ECURSIVE RECURSIVE
FIRST INWORD R E C U R
R E C U R
Уровень
1 2
3
4
5
6 5 4 3 2 1
BUTFIRST :INWORD ECURSIVE CURSIVE URSIVE RSIVE SIVE
Таблица 1
OUTPUT
R=WORD"R" UR=WORD"U"R CUR=WORD"C"UR ECUR=WORD"E"CUR RECUR=WORD"R"ECUR
Вложенные списки.
В качестве элементов списков в ЛОГО тоже могут быть списки. В этом нет ничего удивительного. Если мы составим список того, что лежит у нас в кармане, то можем получить:
[МОНЕТА КАРАНДАШ ЛАСТИК СПИСОК ПОКУПОК]
Обратите внимание на то, что объекты, входящие в список покупок вовсе не являются элементами списка того, что лежит у нас в кармане, таким образом, список содержимого кармана имеет 4 элемента, несмотря на то, что список покупок сам является списком:
[ХЛЕБ МОЛОКО МЯСО МАРКИ]
а ХЛЕБ не является вещью, находящейся в кармане.
Более того, ЛОГО даже допускает создать такой список содержимого кармана:
[МОНЕТА КАРАНДАШ ЛАСТИК [ХЛЕБ МОЛОКО МАСЛО МАРКИ]]
и в этом списке по-прежнему всего 4 элемента, несмотря на то, что четвертый элемент представляет из себя список из 4-х элементов.
Сколько же элементов в следующем списке?
[[ХЛЕБ МОЛОКО МАСЛО МАРКИ][ДЖЕЙН ДЭВИД РОЗМАРИ][СТИРКА ГЛАЖКА]
[8_МАЯ 20_ИЮНЯ 1_ИЮЛЯ 10_СЕНТЯБРЯ 2 3_НОЯБРЯ]]
В этом списке 4 элемента. Все они - тоже списки. Проще было бы дать им имена:
[ПОКУПКИ ДРУЗЬЯ ЗАБОТЫ ДАТЫ]
Вы составили такой список для себя, теперь Вы можете составить аналогичный список для друга и еще раз для кого-то и тогда получите список списков:
[МОЙ ТВОЙ ЧУЖОЙ]
Здесь МОЙ - это [ПОКУПКИ ДРУЗЬЯ ЗАБОТЫ ДАТЫ], точно так же ТВОЙ и ЧУЖОЙ. Так можно продолжать и дальше, вкладывая список один в другой, но наверное стоит остановиться и предоставить такую работу ЛОГО.
Процедуры создания списков
Мы уже использовали команду SENTENCE для того, чтобы создать список из двух и более элементов, которые могут быть словами или списками. Эта команда объединяет их в один список, снимая внешние квадратные скобки и переписывая весь список заново. Например:
(SENTENCE [ВОТ ВАМ][ПРИМЕР ДЕЙСТВИЯ][ОПЕРАТОРА SENTENCE])
выдает в качестве результата:
[ВОТ ВАМ ПРИМЕР ДЕЙСТВИЯ ОПЕРАТОРА SENTENCE]
Сейчас же мы с Вами рассмотрим три новых оператора, по-разному создающих списки.
FPUT (это First PUT). Имеет два входных параметра. Второй параметр - список. Команда FPUT создает новый список, в котором первый элемент берется из первого входного параметра, а остальная часть списка из второго.
Например:
FPUT "РАЗ[ДВА ТРИ ЧЕТЫРЕ]
выдаст список:
[РАЗ ДВА ТРИ ЧЕТЫРЕ]
В отличие от SENTENCE здесь не происходит слияния внешних квадратных скобок при объединении списков, например:
FPUT [РАЗ ДВА][ТРИ ЧЕТЫРЕ]
дает:
[[РАЗ ДВА][ТРИ ЧЕТЫРЕ]
Можете считать, что FPUT берет свой первый параметр и ставит его в первую позицию второго параметра.
Другой оператор, который мы рассмотрим, - это LPUT (Last PUT). Он работает совершенно аналогично, но с одним исключением. Первый параметр LPUT ставится последним элементом в списке, выраженном вторым входным параметром.
LPUT [ПОСЛЕДНИЕ СЛОВА][ЭТО]
дает:
[ЭТО [ПОСЛЕДНИЕ СЛОВА]]
Третий оператор - LIST. Он имеет два или более входных параметров и выдает их в виде списка, независимо от того, являются ли они списками или словами.
LIST "БАНК [ХЛЕБ МОЛОКО МАСЛО МАРКИ]
имеет два входных параметра и выдает список следующего содержания:
[БАНК [ХЛЕБ МОЛОКО МАСЛО МАРКИ]
Если LIST имеет более двух входных параметров, то они должны быть заключены в круглые скобки.
(LIST "БАНК [ХЛЕБ МОЛОКО МАСЛО МАРКИ][ДЖЕИН ДЭВИД РОЗМАРИ]).
выдает список:
[БАНК [ХЛЕБ МОЛОКО МАСЛО МАРКИ][ДЖЕИН ДЭВИД РОЗМАРИ]]
Можете полагать, что команда LIST просто берет все свои параметры и ставит вокруг них дополнительную пару квадратных скобок.
ВНИМАНИЕ! Когда LIST используется более, чем с двумя параметрами и один из них равен самому списку LIST, то в этих случаях оператор не всегда работает правильно. Он также может вызвать проблемы, если включен в квадратные скобки при операторе REPEAT или в список IF. Очень сложные конструкции, таким образом, следует создавать постепенно.
Сортировка чисел.
Теперь мы посмотрим, как можно использовать списки для создания сложных структур данных и для некоторых других практических целей. Сначала мы рассмотрим вопрос сортировки последовательности чисел, введенных с клавиатуры, сортировка данных это очень важный вопрос, в котором проявляется мощь компьютеров. Существует много методов для выполнения сортировки, но мы остановимся на одном из них.
Мы будем хранить числа в структуре, называемой "деревом". На рис. 1 показан пример такого дерева.
7
/
3
/
5
/
4
Рис. 1
Если не очевидно, почему эта структура получила такое название, переверните рисунок вверх ногами. Каждое обведенное число называется "узлом", в каждом из узлов дерево может ветвиться (максимум на две ветви).
Посмотрите, как это организовано. Возьмем, например, число 6 и введем его в наше дерево. Начнем с вершины и в каждом узле будем сравнивать наше число с тем, что содержится в данном узле. Если наше число меньше, то из узла пойдем по левой ветви, а если больше - то по правой.
Представим, что число 6 помещается на вершину дерева, поскольку 6<7, то идем вниз по левой ветви к числу 3. Здесь у нас 6>3 и продолжаем путь по правой ветви к числу 5. Раз 6>5. то и здесь надо пойти по правой ветви, но на сей раз у нас правой ветви нет и ее надо сделать. Просто пририсуем правую ветвь к узлу 5 и поставим в ее конце узел 6.
Итак, каждый узел может иметь две ветви, одну влево для чисел, которые меньше, чем значение в узле и одну вправо для чисел, которые больше, чем значение в узле, простой вопрос "наше число больше, чем значение в узле или меньше?" определяет, по какой ветви нам идти.
Точно так же можно построить дерево и для списков. Каждый узел может быть представлен списком из трех элементов.
Средний элемент - это номер узла, а два других элемента - тоже списки. Первый элемент определяет левую ветвь дерева, а последний - правую, каждая ветвь выстраивается аналогично. Если из узла ветвь не исходит, то ей соответствует пустой список. Таким образом, пустые списки служат как бы маркерами, показывающими, что мы дошли до конца данной ветви.
Вы, наверное, не удивитесь, когда узнаете, что такие конечные узлы называют "листьями", а исходный узел - "корнем".
Дерево для структуры списков показано на рис. 2.
|
|
[[. |
] 7 [.]] |
|
|
/ |
|
|
[[ |
] 3 [. |
]] [[ ] 8 [ ]] |
|
/ |
|
|
|
[[ ] 2 |
[ ]] |
[[.] 5 [ ]] |
|
|
|
/ |
|
|
[[ |
] 4 [ ]] |
Рис.2
В тех узлах, где список не пустой, стоит "точка" [.] и стрелка, показывающая содержимое данного списка, поэтому несмотря на то, что списки находятся один внутри другого, такой "развернутый" вид действительно демонстрирует похожесть на настоящее дерево.
Давайте еще раз посмотрим, как число 6 вписывается в это дерево. Рассмотрим корневой узел на вершине диаграммы, он имеет 3 элемента, из которых средний - число 7. Новое число 6 меньше и потому мы идем по левой ветви, рассматривая левый список. Этот список имеет средний элемент, равный 3. Поскольку 6 больше, то мы ищем правое продолжение, новый список имеет средним элементом 5. Раз 6 больше, чем 5, мы ищем опять правое продолжение. На этот раз список пуст, мы дошли до конца ветви и теперь нашли место, в которое должно быть помещено число 6. Поскольку это последняя точка, то мы отмечаем ее пустыми списками: [[]6[]].
Итак, существуют только два правила для того, чтобы поместить новое число в дерево.
1) Если число помещается в узел, в центре которого уже есть число, то эти числа сравниваются и, если новое число меньше, то оно помещается в начальный список, а если больше, то в конечный.
2) Если число помещается в пустой список, оно становится в средний элемент, а справа и слева добавляются по пустому списку.
Если мы начнем с пустого списка и будем вводить числа в порядке 7,3,5,8,... то у нас будет создаваться список так, как показано в табл. 2. На каждом шагу мы показываем только новые вошедшие в список элементы, дабы сделать структуру проще и нагляднее.
Таблица 2
ШАГ
1 [ ]
2 [ ]7[ ]
3 [ ]3[ ]
4 [ ]5[ ]
5 [ ]8[ ]
Как видите, числа ложатся в список в правильном порядке.
Теперь рассмотрим, как сделать это на языке ЛОГО. Сначала нам нужна процедура, которая выдаст пользователю необходимые инструкции и создаст исходный пустой список, затем выполнит ввод чисел и распечатает упорядоченный список.
ТО SORT
PRINT [Введите числа]
PRINT [Когда закончите, наберите END]
MAKE "NUMLIST []
INPUT
PRINTINORDER :NUMLIST
END
Теперь рассмотрим процедуру INPUT. Она должна принять с клавиатуры первое слово и проверить, не число ли это. Мы используем тот факт, что это не число для того, чтобы сигнализировать о том, что ввод закончен. Если же это число, то его надо ввести в список и посмотреть, куда оно ложится, после чего сформировать новый список.
ТО INPUT
MAKE "NUM FIRST READLIST IF NOT NUMBERP :NUM [STOP] MAKE "NUMLIST RENEW :NUMLIST
END
Здесь мы впервые использовали операцию NOT. Она берёт то условие, которое стоит в качестве ее параметра и изменяет полученный результат с TRUE на FALSE или, соответственно, наоборот. Так что она работает достаточно просто и выдает результат TRUE (ИСТИНА), если :NUM числом не является.
Теперь нам нужно записать процедуру RENEW, которая проверит введенное число по всем имеющимся спискам и вставит его на свое законное место. Эта процедура должна создавать списки из трех элементов, обычно по результатам IF. Как было указано в предыдущей главе, LIST нельзя использовать с круглыми скобками внутри, так что мы начнем с того, что напишем процедуру, которая примет три параметра и сделает из них список:
ТО LIST :A :B :С
OUTPUT (LIST :A :B :C)
END
Теперь, когда мы проверяем введенное число по имеющемуся списку (назовем процедуру ALIST), у нас могут быть три возможности исхода:
- список может быть пустым, в этом случае мы заменяем его новым списком из трех элементов, внешние из которых являются пустыми списками, а средний - введенным числом;
LIST 3 []:NUM[]
- если вводимое число больше, чем средний элемент списка, то новый список замещает тот, который был. В нем первые два элемента остаются неизменными, а в качестве третьего вводится новый список, содержащий вводимое число:
LIST3 FIRST :ALIST ITEM2 :ALIST
RENEW LAST :ALIST
- если вводимое число меньше, чем средний элемент, то в новом списке меняется первый элемент:
LIST3 RENEW FIRST :ALIST ITEM2 :ALIST LAST :ALIST Теперь мы пришли к процедуре RENEW:
TO RENEW :ALIST
IF EMPTYP :ALIST [OUTPUT LIST3[] :NUM[]] IF :NUM>ITEM2 :ALIST
[OUTPUT LIST3 FIRST :ALIST ITEM2 :ALIST RENEW LAST .ALIST] [OUTPUT LIST3 RENEW FIRST :ALIST ITEM2 :ALIST LAST :ALIST]
END
Как мы уже видели, в результате наши числа будут упорядочены по старшинству. Проблемой, однако, является большое количество квадратных скобок. К счастью, здесь помогает сила рекурсии. Для того, чтобы упорядочить список, состоящий из списка, числа и еще одного списка, нам надо распечатать первый список в упорядоченном виде, число и второй список в упорядоченном виде. Если список пуст, то вообще ничего печатать не надо:
ТО PRINTINORDER :ALIST IF EMPTYP :ALIST [STOP] PRINTINORDER FIRST :ALIST PRINT ITEM2 :ALIST PRINTINORDER LAST :ALIST
END
Когда Вы закончите ввод процедур, дайте команду SORT. Введите несколько чисел, по одному на строке. Заканчивайте ввод чисел словом END или любым другим удобным словом, но не числом.
После того, как числа будут распечатаны в отсортированном порядке. Вы можете попробовать:
PRINT :NUMLIST
Теперь Вы увидите, как список хранится в структуре "дерева". Если же Вы хотите увидеть, как создается новый отсортированный список. Вы можете попробовать вставить эту команду в процедуру INPUT.
Самообучающаяся игра.
Сейчас мы попробуем использовать структуру "дерева" для того, чтобы написать игру. Суть игры состоит в том, что один играющий задумывает некоторое животное, а другой должен его угадать. При этом он может задавать любые вопросы, но ответ может быть только "да" или "нет". Но самая интересная часть игры состоит в том, что программа способна самообучаться. В начале игры она знает только двух животных, а по мере того, как Вы с ней играете, она становится все более и более образованной.
Вся информация хранится в виде дерева. Каждый узел - это список, состоящий из трех элементов. Обычно средний элемент списка - вопрос, который надо задать игроку. Если ответ "да", то программа использует первый элемент списка (а он тоже список) для следующего хода. Если же ответ "нет", то программа использует последний элемент списка.
Мы неизбежно дойдем до последней точки. Она выявляется по тому факту, что и первый и последний элемент являются пустыми списками. В данном случае средний элемент - это уже не вопрос к играющему, а название животного.
Когда имя животного выдается игроку, то у него есть две возможности:
- если компьютер угадал верно, то программу не надо обучать;
- но если пользователь задумал другое животное, то программа запрашивает вопрос, с помощью которого можно различить то животное, которое задумал пользователь, и то, которое назвала программа. Это вопрос теперь становится средний элементом в новом узле, а названия животных - в узлах справа и слева. Опять же к каждому из этих названий добавляется справа и слева по пустому списку. Входная процедура должна ввести пользователя в суть игры и создать корневой список перед тем, как игра начнет свою работу.
ТО ANIMAL
PRINT " PRINT [Добро пожаловать на викторину] PRINT [Отвечайте только "ДА" или "НЕТ"] MAKE "NODE [[[][УТКА][]] [ОНО ПЛАВАЕТ?] [[][СВИНЬЯ][]]]
GO
END
Рабочая процедура GO просит играющего задумать животное, проверяет элементы своего списка и обеспечивает повтор всего процесса для другого животного.
ТО GO
PRINT [ЗАДУМАЙ ЖИВОТНОЕ] PRINT "
MAKE "NODE TRY :NODE PRINT [ЕЩЕ РАЗ?] MAKE "YN FIRST READLIST IF YN= "YES [GO]
END
Процедура GO проверяет текущий узел. Это может привести к изменению списка, поэтому процедура TRY выдает новое содержание узла.
Необходимо предусмотреть две возможности. Средний элемент в узле может быть либо вопросом, который надо задать игроку, либо готовым ответом.
Программа различает эти два случая, проверив первый элемент. Если он пуст, то во втором элементе содержится ответ.
ТО TRY :ANODE
IF EMPTYP FIRST :ANODE [OUTPUT GUESSANSWER] [OUTPUT PUTQUESTION]
END
Теперь процедура GUESSANSWER должна угадать ответ и, если он верен, то изменений делать не надо, а если нет, то надо сконструировать новый узел?
ТО GUESSANSWER PRINT "
PRINT SENTENCE [ЭТО]
ITEM2 :ANODE
MAKE "YN FIRST READLIST
IF :YN= "YES
[PRINT [Я ТАК И ДУМАЛ]
OUTPUT :ANODE]
[OUTPUT NEWNODE]
END
Процедура NEWNODE запрашивает правильный ответ и конструирует новый узел для двух животных, используя при этом полученный от пользователя вопрос. "Новое" животное должно быть помещено в новый список между двумя пустыми списками. "Старое" животное уже организовано таким образом в текущем узле.
Здесь нам вновь будет нужна процедура LIST3, о которой мы говорили выше:
ТО NEWNODE
PRINT [Сдаюсь! что это за животное?] MAKE "ANIMAL1 READLIST MAKE "NEWPART[LIST[1:ANIMAL1[]] MAKE "ANIMAL2 ITEM2 :ANODE
PRINT [SENTENCE[Дайте мне вопрос, чтобы отличить] :ANIMAL1 "и :ANIMAL2] MAKE "QUESTION READLIST
PRINT [SENTENCE[и для ] :ANIMAL1 [ответ будет да?]
MAKE "YN FIRST READLIST IF :YN="ДА[OUTPUT LIST3 :NEWPART :QUESTION :ANODE] [OUTPUT LIST3 :ANODE :QUESTION :NEWPART]
END
Это самая сложная процедура в программе, но ключ к ее пониманию лежит в двух операциях OUTPUT, записанных в ее конце.
ТО PUTQUESTION PRINT "
PRINT ITEM2 :ANODE MAKE "YN FIRST READLIST IF :YN=" ДА [OUTPUT LIST3 TRY FIRST :ANODE ITEM2 :ANODE LAST :ANODE]
[OUTPUT LIST3 FISTST :ANODE ITEM2 :ANODE TRY LAST :ANODE]
END
И здесь тоже основная смысловая часть процедуры заключена в двух последних операциях OUTPUT.
Теперь, если все сделано правильно. Вы можете дать команду ANIMAL и, работая с программой, увидеть, как происходит ее самообучение.
8. Некоторые математические операции.
ЛОГО различает два различных вида чисел: целые (например 1, -23, 245 и т.д.) и десятичные (0.67, 28.91 и т.п.). Обычно Вам не надо думать о том, что между ними есть разница, вероятно, единственный случай, когда различие между ними существенно, это тогда, когда Вы пытаетесь ввести десятичное число в процедуру, которая ожидает в качестве своего параметра целое число. И даже в этом случае, как правило, ЛОГО предупредит Вас.
Операция INT (INTEGER) принимает в качестве входного любое число, а свой результат выдает в виде целого. Она, таким образом, отрезает десятичную часть числа.
PRINT INT 3,14 3
PRINT 6
PRINT INT -2.1 -1
Обратите внимание на то, что хотя 6,999 очень близко к числу 7, результатом все-таки будет число 6. Этот процесс всегда ведет к округлению вниз.
В некоторых случаях такая особенность может быть полезной. Например, иногда бывает важным найти результат деления одного числа на другое и образующийся при этом остаток.
Может это быть полезным, когда Вы проверяете, является ли данное число целым или нет. Если оно целое, то применение к нему функции INT уже не изменит его.
ТО TESTINT1 :NUM IF :NUM-INT :NUM
[PRINT "YES] [PRINT ^О]
END
Таким же способом можно определить и делится ли одно число на другое нацело.
ТО TESTDIV :NUM1 :NUM2
IF (NUM1/NUM2) = INT(:NUM1/:NUM2) [PRINT "YES] [PRINT "NO]
END
Если же Вам на самом деле нужно ближайшее целое число, то Вы можете воспользоваться операцией ROUND. Она тоже может принимать любое число в качестве входного и выдает ближайшее целое число.
PRINT ROUND 3.14 3
PRINT ROUND 6.99 7
PRINT ROUND -2.9 -3
Эта операция берет свое название из термина rounding ("округление"). Она может быть использована для того, чтобы выдавать ответ с заданной степенью точности, с небольшими усилиями ее можно использовать и для получения результата с заданным количеством десятичных знаков.
Так, например, если Вам надо округлить 3.14159 до двух десятичных знаков, то Вы можете умножить это число на 100 (314.159), округлить его (314) и снова разделить на 100 (3.14). Эту операцию можно конвертировать в рекуррентную процедуру, на каждом шагу умножая исходное число на 10. Если количество десятичных чисел равно нулю, то число просто округляется.
ТО CORRECT :NUM :DECPLS
IF DECPLS=0 [OUTPUT ROUND :NUM] OUTPUT (CORRECT :NUM*10 :DECPLS -1)/10
END
Есть еще одна операция, которая всегда выдает в результате своей работа целое число. Это операция REMAINDER. Она требует два входных параметра и выдает остаток от деления нацело первого числа на второе.
PRINT REMAINDER 12 5 2
Эта операция обеспечивает еще один путь для проверки делится ли одно число на другое нацело. Если это так, то результат операции равен нулю.
ИСТИНА и ЛОЖЬ (TRUE и FALSE)
Мы можем писать процедуры, которые проверяют условия и выдают в качестве результата TRUE или FALSE, это можно сделать одним из двух возможных способов, Вы можете выдавать результат в виде слова TRUE, FALSE и т.п., например:
ТО DIVISIBLE :A :B
IF O=REMAINDER :A :B [OUTPUT "TRUE] [OUTPUT "FALSE]
END
Второй способ - получение ответа сразу в результате проверки и немедленной выдачи результата:
ТО DIVISIBLE :A :B
OUTPUT O=REMAINDER :A :B
END
Здесь, если действительно остаток от деления :A на :B равен нулю, результат равен TRUE, а если нет - то результат равен FALSE.
Такой результат можно напрямую использовать для оператора IF.
IF DIVISIBLE 20 5 [PRINT "YES] [PRINT "NO]
Фактически Вы только что определили предикативную процедуру и чтобы это подчеркнуть, ее можно назвать DIVISIBLEP.
Иногда мы сталкиваемся с тем, что будет ли результат операции иметь значение TRUE или FALSE, зависит от одного или большего количества условий, ЛОГО обеспечивает три операции, работающих с предикатами (условиями), мы уже рассмотрели NОТ, изменяющую результат условия на противоположный. Есть еще операция AND, которая дает в результате значение TRUE, если все входящие выражения имеют значение TRUE. Обычно операция AND обрабатывает два условия, но их может быть и больше, если применить круглые скобки.
PRINT AND 1<2 3<7
TRUE
Другая операция - OR (ИЛИ). Она дает в результате TRUE, если хотя бы одно из входящих выражений имеют значение TRUE. Так же, как и AND, операция OR может иметь более двух входных выражений.
При аккуратной работе можно объединять AND и OR в одном выражении. Например, Вы можете прийти ко мне на день рождения, если Вас зовут Фред или Вы женщина и к тому же красивая.
Возведение в степень и извлечение корня.
Узнать квадрат числа можно умножив его само на себя, другие степени числа легко находятся с помощью рекурсии.
ТО POWER :A :В
IF :B<2 [OUTPUT :A] OUTPUT (POWER :A :B -1)*А
END
Для вычисления корней квадратных из числа, ЛОГО имеет специальную функцию
SQRT.
PRINT SQRT 25
5
Мы можем воспользоваться теоремой Пифагора для вычисления расстояния между двумя точками с известными координатами (координата X и координата Y). В учебниках по математике Вы найдете, что расстояние между двумя точками с координатами [X1, Y1] и [X2, Y2] можно найти, как
V(x2 - Х1 )2 + (У2 - Ух )2
Рис. 3
ТО DISTANCE :POS1 :POS2
MAKE "XDIF FIRST :POS1-FIRST :POS2 MAKE "YDIF LAST :POS1-LAST :POS2 OUTPUT SQRT(XDIF*XDIF+YDIF*YDIF)
END
Поиск простых чисел.
Простое число - это число, которое нацело делится только на единицу или само на себя. Проблема поиска простых чисел волнует математиков уже несколько тысяч лет. Пока не найдена формула, по которой можно было бы найти все простые числа, а те формулы, которые уже известны, выдают определенную последовательность из простых чисел, но начиная с какого-то числа выдают и непростые числа (См. ZX-РЕВЮ^, №7,8. с. 133).
Хоть и не существует вполне надежной формулы для простых чисел, зато существует метод. Мы можем просто брать числа по очереди и проверять, делятся ли они нацело на другие числа, которые меньше, чем оно само. Задача упрощается тем, что нужно проверять не все числа, а только до корня квадратного из исходного числа. Ведь если оно делится на что-то, что больше, чем квадратный корень, то в результате получим частное, которое меньше, чем квадратный корень, а эти числа мы уже проверили.
ТО TESTPRIME :NUM :N
IF :N>SQRT :NUM[OUTPUT "TRUE] IF DIVISIBLE :NUM :N[OUTPUT "FALSE] OUTPUT TESTPRIME :NUM :N+1
END
Проверку надо начинать с числа 2 - это наименьшее простое число.
ТО PRIMESFORM :NUM
IF TESTPRIME :NUM2[PRINT :NUM] PRIMESFORM :NUM+1
END
Теперь команда PRIMESFORM 2 будет распечатывать простые числа, начиная с числа 2 и выше.
Тригонометрические операции.
Если Вы уже знакомы с тригонометрическими функциями, то можете пропустить один абзац. Если же нет, то читайте дальше.
Если наша "черепашка" имеет значение HEADING, равное углу :ANGLE, то на каждом шаге она проходит разные расстояния вдоль экрана и поперек. Если "черепашка" пройдет в направлении своего движения единицу пути, то ее перемещение по горизонтали равно синусу угла :ANGLE, а перемещение по вертикали - равно косинусу угла :ANGLE. Если путь, пройденный "черепашкой" равен единице, то очевидно, что путь, пройденный ею по горизонтали, меньше единицы, то же и путь, пройденный по вертикали.
Может быть, Вас интересует не один шаг, пройденный "черепашкой", а сразу 10. В этом случае ее перемещение по горизонтали:
10*SINE :ANGLE
а путь по вертикали:
10*COSINE :ANGLE
COSINE :ANGLE
Рис. 4 Синус и косинус угла.
Математики пользуются еще двумя функциями: тангенс (это частное от деления синуса угла на его косинус) и котангенс (частное от деления косинуса на синус).
ЛОГО предоставляет возможность использования четырех операций: SINE, COSINE, TANGENT, COTANGENT, в сокращенной форме SIN, COS, TAN, COT. У ЛОГО есть большое преимущество перед другими языками программирования в том смысле, что ЛОГО принимает углы для этих операции в градусной мере, в то время как другие языки программирования предпочитают иметь дело с радианами. Поэтому, если Вы привыкли к другим языкам и к радианной мере, то теперь вздохнете с облегчением. Если же Вы к ней не привыкли и никогда о ней не слышали, то тем более вздохнете с облегчением, поскольку можно о ней и не думать.
Кроме 4-х описанных выше операций, есть еще четыре: ARCSIN, ARCCOS, ARCTAN, ARCCOT, которые имеют прямо противоположное действие.
В качестве входного параметра они принимают число, а на выходе выдают угол в градусах, который имеет соответствующий синус (косинус, тангенс, котангенс).
Так, PRINT ARCCOS 0.5 даст Вам угол, косинус которого равен 0.5, т.е. 60 градусов.
Эти операции имеют огромное значение в изучении электроники, волновых явлений и вибраций. С помощью этих функций можно также исполнять очень красивые и интересные кривые. Рассмотрим, например, пару следующих процедур, которые изображают график функции косинус для углов от 0 до 360 градусов. Координаты X и Y здесь распечатываются через угол и его косинус, соответственно. Масштаб избран таким, чтобы изображение хорошо вписывалось в экран. Когда "черепашка" дойдет до границы экрана, Вы получите сообщение "turtle out of bounds".
TO SHOWCOS PENUP
SETPOS [120 0] PENDOWN SETPOS [120 0] DO COS 0
END
TO DOCOS :ANGLE
MAKE "X 2* :ANGLE/3-120 MAKE "Y 80*COS :ANGLE SETPOS SE :X :Y DOCOS :ANGLE+15
END
Вы увидите колебания в вертикальной плоскости. Что произойдет, если мы добавим сюда еще и колебания по горизонтали? Вы получите фигуры, названные именем их первооткрывателя - фигуры Лиссажу.
ТО LISSAJOU :A :B :C :D :INC SHOWTURTLE CLEARSCREEN PENUP LISS 0
END
TO LISS :ANGLE
MAKE "X 120*COS(:A*:ANGLE+:B) MAKE "Y 80*C0S(:C*:ANGLE+:D) SETPOS SE :X :Y PENDOWN
LISS :ANGLE+:INC
END
Перо опустится после первой команды SETPOS (и после этого останется опущенным), поэтому "черепашка" пойдет в стартовую позицию без изображения линии. Чем выше значение INC, тем более угловатой будет полученная графика.
Попробуйте:
LISSAJOU 11 20 21 40 1
Введение в графику цвета позволяет получать очень интересные эффекты. Вот еще несколько примеров "черепашьей" графики:
ТО CYCLO :K :ANGLE :SIZE
FORWARD :SIZE*SIN(:K*HEADING)
RIGHT :ANGLE
CYCLO :K :ANGLE :SIZE
END
Попробуйте
CYCLO 1 10 10 CYCLO 4 5 20
И еще одна процедура:
ТО LOBE :A :B :INC :ANGLE FORWARD 1
RIGHT :A :B :INC :ANGLE+:INC
END
Попробуйте:
LOBE 2 3 9 0 LOBE 10 8 6 0 LOBE 2 8 6 0 LOBE 2 9 3 0
(Окончание в следующем номере).
Стюарт Николс.