51
Язык Лого
А. А. ДУВАНОВ, Ю. А. ПЕРВИН
Урок 4:
Структура данных в Лого
Алгоритмический язык и Лого
Te из читателей, которые проходят информацию в школе, наверняка сравнивают описываемый в учебнике алгоритмический язык и знакомый по «Кванту» Лого. Легко увидеть сходство обих языков в средствах графики, условий командах, команде присваивания. Соотношение циклов в Лого и алгоритмическом языке сложнее. От цикла ДЛЯ алгоритмического языка легко перейти к циклу ПОВТОРИ. Так, вычислить объем «пирамиды», составленной из нескольких колес, можно с помощью цикла ДЛЯ:
V:=0
ДЛЯ R OT 10 ДО 50 ШАГ 10
НЦ
V:=V+3.14R**2H
КЦ
На Лого это программируется так:
СДЕЛАЙ” V 0
ПОВТОРИ 5
[СДЕЛАЙ” V СЛОЖИ УМНОЖЬ УМНОЖЬ R R H 3.14 V]
А вот цикл ПОКА, существующий в алгоритмическом языке, не имеет прямого аналога в Лого. В таком цикле всегда за словом ПОКА записывается условие. Это условие — ключ, открывающий вход в тело цикла: если условие истинно, то выполняются команды цикла и вовь проверяется условие; если же условие нарушается, машина переходит к выполнению команды, следующего за циклом. В школьном учебнике информаники приведен алгоритм вычисления НОД с помощью цикла ПОКА. Для того чтобы в Лого реализовать действия, повторяющиеся не фиксированное число раз, а зависящее от
52
некоторого условия (включающего переменную), надо воспользоваться ресурсей. Используйте эту поддержку для выполнения следующого задания.
Задача 1. Напишите на Лого функцию вычисления НОД двух чисел.
Основное сходство, которое родит алгоритмический язык и Лого, состоит в возможности составлять описания сложного действия из более простых. Такие описания в Лого называются процедурами, а в алгоритмическом языке — вспомогательными алгоритмами. Столь же близки понятия функции в общих языках.
Важно, однako, оставиться на различных. Один из таких различий является способ возврата значения функции в вызывающую программу. В Лого для этого использовать команда ВЕРНИ α. Она заканчивает выполнение функции и возврашает в программу значение выражения α. В алгоритмическом языке нет специальных средств возврата. Выход из функции производится после выполнения последней команды. В качестве результата возврашает значение специальной переменной ЗНАЧ, которая совпадает по типу с типом функции.
В большинстве языков программирования существует возможность представления и обработки литераных величины, как они называются в алгоритмическом языке. В Лого для выполнения такого типа существует простое название — «слово». Слово — это конечная упорядоченная последовательность символов, отличающихся от пробела. Слову в программе представуется как вычка, которая не входит в счет символов слова. Слово может быть пустым — в таком слове нет ни одного символа, его обозначение — кавычка, за которой следует пробел (в алгоритмическом языке литераная переменная оказывается парой кавычек). Примеры слов Лого: “НАДЯ — в слове 4 буквы; “У — отдельный символ считается словом, состоящим из одного этого символа; “1918—1988 — слов из 9 символов.
Раннее слова были использованы для обозначения имен переменных. По команде СДЕЛАЙ “КЛЕТКА 1 переменная КЛЕТКА получает значение 1. Команда СДЕЛАЙ “КЛЕТКА” “СЛОН делает значение переменной KЛЕТКА слова СЛОН. В алгоритмическом языке последняя команда имея бы вид: KЛЕТКА:=“СЛОН”
Такие разные слова!
Представьте разговор двух мальчиков. Сережа расссказывает:
— ABВА — это имя, которое я дал свой собак.
— Забавное имя, — говорит Антон,— а как оно пишется?
— «ABВА» — это так: сначала «А», потом «В», еще «В» и в конце опять «А».
— Она знает свое имя? — интересно узнать Антону.
Сережа рад продемонстрировать способности своего собаки:
— Ну, конечно! ABВА! Вот и она!
Trijsды в этом разговоре употреблено слово ABВА и каждый раз — в разной своей роли. ABВА — это имя собаки; «ABВА» — это слово, представляющее собой последовательность букв в строком порядке; ABВА! — это команда собака немедленно является к своему хозяйству. В устной речи разное использование слов можно отметить интонацией. Если же такой разговор надо записать, то для различения разных роли слова потребуется специальное обозначение — знаки препиниания.
В Лого дело obstит точно так же. Для расположения смысла использовых в программе слов примера также синтаксические правила:
53
— двоечие ставят перед именем величины для того, чтобы обозначить значение, принимаемое этой величиной в текущий момент; так :ОТМЕТКА есть значение переменной ОТМЕТКА;
— кавычки ставят перед словом, представляющим собой целочку символов; по положению такого слова в команде (по контексту) судят о смысле обозначемого слова; так, в команде присваивания СДЕЛАЙ “КЛЕТКА” СЛОН слова в последней позиции — “СЛОН с кавычкой в начале — есть литера常数та, а слова в предшествующей позиции — “КЛЕТКА — есть имя переменной КЛЕТКА; сравните команду СДЕЛАЙ “КЛЕТКА :СЛОН, где переменная КЛЕТКА получает значение, которое имела переменная с именем СЛОН;
— перед вызовами процедур и функции (так же, как перед командами и операциями) не ставятся ни двоечие, ни кавычка; запись КЛЕТКА :СЛОН означает вызов процедуры КЛЕТКА с параметром СЛОН.
Зайемся обработкой списков
Программисты часто используют термин «данные». Этот термин можно считать синономом понятия «информация». Обрабатываемая машиной информация может быть организована по-разному. Это либо единние символы, либо их упорядоченный конечный набор — слова, либо упорядоченная группа слов — список, либо какой-нибудь другой более сложный способ обедининия символов, слов и списков. Организованную по тому или иному способу информацию называют структурой данных.
В алгоритмическом языке каждой структура данных должна с помощью специального имен — типа величины — нат, веще, лит и т. д. В Лого нет описания типов, однако каждой из структур алгоритмического языка имеет свои аналоги в Лого. Для представления таблицы и более сложных структур данных Лого использует списк, расширяющие понятие табличной величины алгоритмического языка.
Обработка списков требует совсемины операций, чем аргументические расчеты. Пусть необходимо заполнить в памяти ЭВМ информацию об учениках класса — списк сведений по каждому ученику. Для работы с такой структурой полезно иметь операции, которые позволяютставлять, удалять, находить, изменять элементы списка.
Выборка первого элемента структуры — ПЕРВЫЙ α (или ПРВ α). Аргумент этой операции — слова или список, результат — первый элемент(structуры. Например,
ПРВ “ЛОГО = “Л,
ПРВ [ЛОГО язык ПРОГРАММИРОВАНИЯ]=
= “ЛОГО
Структура без первого элемента — КРОМЕПЕРВОГО α (или КПРВ α). Аргумент этой операции — слова или список, результат — последний элемент(structуры. Например,
КПРВ “ЛОГО = “ОГО
КПРВ [ЛОГО язык ПРОГРАММИРОВАНИЯ] =
[Язык ПРОГРАММИРОВАНИЯ]
Последний элемент(structуры — ПОСЛЕДНИЙ α (или ПСЛ α). Аргумент этой операции — слова или список, результат — последний элемент(structуры. Например,
ПСЛ “ЛОГО = “ОГО
ПСЛ [ЛОГО язык ПРОГРАММИРОВАНИЯ] =
[Язык ПРОГРАММИРОВАНИЯ]
Структура без последнего элемента — КРОМЕПОСЛЕДНЕГО α (или КПСЛ α). Аргумент операции — слова или список, результат — структура без последнего элемента. Например,
КПСЛ “ЛОГО = “ЛОГ
КПСЛ [ЛОГО язык ПРОГРАММИРОВАНИЯ] =
[ЛОГО язык ПРОГРАММИРОВАНИЯ]
Включение элемента в начало(structуры — ВНАЧАЛО αβ (или ВНАЧ αβ). Первый аргумент — включаем элемент, второй — изменяем(structура. Например,
ВНАЧ “Л” “ОГО = “ЛОГО
ВНАЧ “ЛОГО [Язык ПРОГРАММИРОВАНИЯ] =
[ЛОГО язык ПРОГРАММИРОВАНИЯ]
Включение элемента в конец(structуры — ВКОНЕЦ αβ (или ВКОН αβ). Первый аргумент — включаем
54
мый элемент, второй — изменяемая структура. Например,
ВКОН “О “ЛОГ = “ЛОГО
ВКОН “ПРОГРАММИРОВАНИЯ [ЛОГО Язык] = [ЛОГО Язык ПРОГРАММИРОВАНИЯ]
Определение длины структуры — ДЛИНА α. Аргумент этой операции — слово или список; результат — число элементов в структуре. Например,
ДЛИНА “ЛОГО = 4
ДЛИНА [ЛОГО Язык ПРОГРАММИРОВАНИЯ] = 3
ДЛИНА [[РУЧКИ 3] [ТЕТРАДИ 2] [ПЕНА-лы 5]] = 3
Для анализа структуры данных в Лого, кроме ранее введенных, используются следующие виды условий структуры:
Число? СЛОВО? СПИСОК? ПУСТО?
Эти условия проверяют, является ли структура числом, словом, списком или она пуста.
Итак, данные об учениках класса хранятся в виде списка:
КЛАСС=
[[ИВАНОВ ПЕТЯ ПОЛЕВАЯ 35 17]
[ДАНИЛОВ САША ПУШКИНА 58 2]
…]
Нужно составить список фамилии всех учеников класса. «Досье» Иванова достанем из списка КЛАСС операцией ПРВ :КЛАСС:
[ИВАНОВ ПЕТЯ СТАРОСТА ПОЛЕВАЯ 35 17]
Из этого списка нам снова нужен первый элемент:
ПРВ ПРВ :КЛАСС = “ИВАНОВ”
Фамилии мы будем собирать в списке ФАМ:
СДЕЛАЙ “ФАМ ВКОН ПРВ ПРВ :КЛАСС :ФАМ
(1)
Команда (1) удаляет список ФАМ на один элемент. Слово ИВАНОВ добавляется в его конец. А как бы с Петровым? Очень просто: надо-yко-ротить список КЛАСС:
СДЕЛАЙ “КЛАСС КПРВ :КЛАСС
(2)
и снова выполнить команду (1). А дальше? Все повторяется: за командой (1) нужна команда (2) и т. д., пока весь список КЛАСС не исчерпается. Вот как выглядит описание нужной функции:
ЭТО ФАМИЛИИ :КЛАСС :ФАМ
ПОВТОРИ ДЛИНА :КЛАСС
[СДЕЛАЙ “ФАМ ВКОН ПРВ ПРВ
:КЛАСС :ФАМ
СДЕЛАЙ “КЛАСС КПРВ :КЛАСС
]
ВЕРНИ :ФАМ
КОНЕЦ
Составив такое описание, получаем желаемый список фамилий при помощи команды:
ВЫВЕДИ ФАМИЛИИ :КЛАСС []
(3)
Построенная функция — не единственная, которая решает поставленную задачу. Можно предложить ее рекурсивный вариант:
ЭТО ФАМИЛИИ :КЛАСС :ФАМ
ЕСЛИ ПУСТО? :КЛАСС [ВЕРНИ :ФАМ]
СДЕЛАЙ “ФАМ ВКОН ПРВ ПРВ :КЛАСС :ФАМ
ВЕРНИ ФАМИЛИИ КПРВ :КЛАСС :ФАМ
КОНЕЦ
Здесь команда:
ЕСЛИ ПУСТО? :КЛАСС [ВЕРНИ :ФАМ ]
обеспечивает окончание рекурсии, когда список КЛАСС будет исчерпан. Команда:
СДЕЛАЙ. “ФАМ ВКОН ПРВ ПРВ :КЛАСС :ФАМ
добавляет очередную фамилию в список ФАМ. Команда:
ВЕРНИ ФАМИЛИИ КПРВ :КЛАСС :ФАМ
делает рекурсивный вызов функции ФАМИЛИИ с укороченным списом КЛАСС.
Задание 2 и 3. Напишите два варианта функции АДРЕС (рекурсивный и с командой цикла), которая по фамилии выдавала бы в качестве своего значения адрес ученика. Например, результатом вывода АДРЕС: КЛАСС “ИВАНОВ должен быть список [ПОЛЕВАЯ 35 17], а результатом вывода АДРЕС: КЛАСС “ДАНИЛОВ — список [ПУШКИНА 58 2].
Функция должна предсматривать вызов сообщения [ТАКОГО УЧЕНИКА НЕТ] в случае ошибочного фамилии.
Задание 4. Напишите функцию, вычисляющую число слов в списке. Ясно, что стандартная функция ДЛИНА не всегда сравняется правильно. Например, число элементов в списке [[ВАСЯ ПЕТЯ] КОЛЯ] — два, в то время как число слов — три.
Внимание! О дальнейшем порядке работы 3ШП читайте на с. 47.