|
||||||||||||||||||||||||||||||||||||||||||||||||
Создание программы для перевода чисел из одной позиционной системы в другуюВ весенних номерах “Информатики” (№ 7, 8/2009) был опубликован практикум по теме “Кодирование текста и чисел” для 9-го или 10-го класса, в котором используются язык программирования Лого и среда ЛогоМиры. Краткое содержание практикума: получение и исследование кодовой таблицы для Windows (CP 1251); получение других однобайтовых кодовых таблиц и сравнение их; создание программы перекодировки текста из одной кодовой таблицы в другую. Непосредственным продолжением этого практикума может быть создание программы для перевода чисел из одной позиционной системы счисления в другую. Для решения этой задачи необходимо, можно сказать, углубиться в программирование: познакомиться со структурами данных в Лого (словами и списками), научиться описывать и использовать функции. В общеобразовательных классах обычно находятся 2–3 “продвинутых” школьника, интересующихся программированием и математикой. Вот им я и предлагаю эту тему. Чтобы они, опередив одноклассников, не скучали на уроках. Другой вариант — этот материал можно использовать на кружке или факультативе. Общий план · Знакомимся с данными типа “слово” и “список”, учимся “разбирать” их на составные элементы. · Пишем программу для перевода числа из недесятичной системы счисления в десятичную. · Знакомимся с описанием функций и вносим улучшения в программу. · Знакомимся с операциями формирования слов и списков. · Учимся описывать рекурсивные функции. · Создаем рекурсивную функцию перевода числа из десятичной системы счисления в недесятичную. · Объединяем обе части в общую программу перевода натурального числа из одной позиционной системы счисления в другую. Основания систем счисления — от двух до тридцати шести (в записи чисел используются цифры и латинские буквы). Типы данных в Лого. Операции над словами и списками Текст программы состоит из команд и операций, большинство которых обрабатывают те или иные данные. Многие из известных вам команд и операций Лого имеют дело с числами. Например, FD 60, RANDOM 100, CHAR 200. Могут ли быть в языке программирования другие типы данных? Да, и их перечень различается в разных языках. В языке машинных команд, понятном процессору, никаких других данных, кроме двоичных кодов (а их можно представлять двоичными числами), нет. Но программисты практически не пользуются языком машинных команд: программирование было бы слишком трудоемким делом. Программисты пишут программы на языках высокого уровня, а потом эти программы автоматически переводятся на язык машинных команд. И во всех языках высокого уровня предусмотрена возможность, кроме простых данных, использовать структуры данных. То есть некоторым образом организованные наборы простых данных. Примеры структур данных: массивы, очереди, списки, графы, стеки. Использование сложных, структурных типов данных позволяет программисту написать компактную и легко “перенастраиваемую” программу. В языке Лого два таких типа данных — слова и списки. Слово — последовательность символов. Например: предмет ;#,..../! 1_А N 175 8,036 Число — это последовательность цифр, поэтому число может рассматриваться и обрабатываться, как слово. Список — это последовательность элементов. Элементами могут быть слова (в частности, числа) и другие списки. Когда в качестве данного хотят записать слово, не являющееся числом, перед ним ставят кавычки (без пробела). Если же в качестве данного записывают список, то его заключают в квадратные скобки. Посмотрим на разные примеры использования команды вывода PRINT (PR): PR 25 PR "Имя? PR [Имя?] PR [Ваше имя?] Таким образом, параметром хорошо вам знакомой команды PRINT может являться и слово, и список. Команды повтора и условного ветвления используют в качестве данных списки инструкций, в которые входят команды и процедуры. Именно поэтому их необходимо заключать в квадратные скобки: REPEAT 3 [FD 40 RT 90] IF :N > 0 [STOP] Команда присваивания MAKE имеет два параметра. Первый параметр — имя переменной, то есть слово (оно может состоять из одной буквы). Именно поэтому, когда вы указываете имя переменной, то должны поставить перед ним двойную кавычку. Второй параметр — данное любого типа: слово (в частности, число) или список. Например: MAKE "A 100 MAKE "Имя [Петров Василий Иванович] MAKE "Телефон "123-45-67 Что можно сделать со словом или списком? Например, сосчитать количество элементов. "Пирог это слово, в нем 5 элементов. [Пирог] список, в нем 1 элемент. [FD 40 RT 90] список с четырьмя элементами. [1 2 [3 4] ] в этом списке 3 элемента, последний элемент сам является списком с двумя элементами. Список может быть пустым, а слово — не содержать ни одного символа: MAKE "L [] MAKE "W " Переменной L присвоено значение пустого списка, а переменной W — значение пустого слова. Количество элементов слова или списка определяет операция COUNT. Каким будет результат выполнения следующих инструкций? PR COUNT [1 2 3] PR COUNT [123] PR COUNT 123 PR COUNT [пирог] PR COUNT "пирог Откройте новый файл ЛогоМиров и проверьте ваши предположения. Не забудьте создать на листе текстовое окно! При необходимости выделить первый или последний элемент слова или списка используются операции FIRST и LAST. Например:
Если нужно получить слово или список без первого или последнего элемента, используют операции BF и BL (сокращения от but first и but last — кроме первого и кроме последнего).
Проверьте все приведенные примеры в вашем файле ЛогоМиров. Обратите внимание на то, что результат выполнения операции во всех примерах передается команде (в данном случае — команде вывода). Правильно записанная программа на Лого может состоять из “цепочек” следующего вида: команда операция операция … операция Сначала в такой цепочке выполняется последняя операция (вычисление или проверка), и ее результат в качестве аргумента передается предыдущей операции. Результат выполнения предпоследней операции передается, в свою очередь, предыдущей. И так до тех пор, пока не окажется выполненной первая операция и ее результат не будет передан команде для выполнения действия. Например, чтобы выделить предпоследний элемент слова или списка, можно использовать одну за другой операции LAST и BL:
Теперь посмотрим, какие задачи можно решать с помощью новых операций. Например, нужно написать программу для распечатывания любого заданного слова по вертикали. Назовем процедуру СТОЛБИК. Она должна работать так:
Первый вариант решения: построим
циклическую программу. Цикл повторяется столько
раз, сколько букв в слове, то есть нужно
использовать операцию COUNT. это столбик1 :слово REPEAT COUNT :слово [ PR FIRST :слово MAKE "слово BF :слово ] END Каждый раз выводится первый элемент слова, но само слово укорачивается на этот элемент. Другими словами, значение переменной слово каждый раз изменяется, так как отбрасывается первая буква. Возможен и рекурсивный вариант решения, но тогда понадобится еще одна операция для определения — не пустое ли слово? Это операция EMPTY? (от англ. “пустой”). Она нужна для того, чтобы вовремя остановить рекурсивную процедуру. это столбик2 :слово IF EMPTY? :слово [STOP] PR FIRST :слово столбик2 BF :слово END Проверьте действие обеих процедур в вашем файле ЛогоМиров. Когда будете запускать процедуру, не забудьте поставить перед задуманным словом двойную кавычку, например: столбик1 "крокодил Итак, в этом параграфе вы познакомились с операциями языка Лого, помогающими “разобрать на составные части” структурные данные — слова и списки.
Примечания. Здесь приводятся не все средства языка Лого для работы со словами и списками. Например, еще можно выделить элемент слова или списка по его номеру. Делается это с помощью операции ITEM, у которой два параметра — номер элемента и слово или список, где этот элемент нужно найти. Но в данном материале не ставится цель полно и всесторонне познакомить учащихся с языком программирования. Используемый подход другой, можно сказать, “практико-ориентированный”. Есть задача, ищем подходящие средства для ее решения, а по дороге, попутно, знакомимся с новыми идеями, средствами и методами. Обобщение в академическом стиле предполагается позже, когда учащиеся на факультативе познакомятся с языком Паскаль, порешают те же задачи на Паскале. Тогда будет полезно и интересно сравнить средства и возможности двух языков. Еще одно замечание о термине “операция”: он имеет здесь тот же смысл, что и слово “датчик” (для Лого), а также “стандартная функция” (для других языков). Задания 1. Напишите процедуру для постепенного укорачивания заданного слова. Например: карта карта карт арта кар или рта ка та к а Подсказка для варианта с командами повтора и присваивания. Программа циклическая, цикл повторяется столько раз, сколько букв в слове (значит, нужно использовать операцию COUNT). В каждом цикле выводится на экран значение переменной — слова. А затем значение этой переменной изменяется (с помощью команды присваивания). Изменение (укорачивание) производится с помощью операций BF или BL. 2. Напишите процедуру, которая печатает заданное слово “наоборот” (например, дом — мод). Подсказка для варианта с командами повтора и присваивания. В каждом цикле выводится на экран последний элемент заданного слова (параметра вашей процедуры). Для этого можно использовать операцию LAST. Затем параметр укорачивается на последнюю букву (с помощью операции BL). Чтобы перевернутое слово оказалось напечатанным в строчку, используйте для вывода команду INSERT. 3. Напишите процедуру для нахождения наименьшего числа в списке чисел. 4. Напишите процедуру для подсчета суммы заданного списка чисел. Подсказка для варианта с командами повтора и присваивания. Программа циклическая. Перед циклом необходимо завести переменную, в которой будет постепенно накапливаться сумма, и присвоить ей начальное нулевое значение. Цикл повторяется столько раз, сколько чисел в списке (операция COUNT). Управляющей переменной будет сам список. При каждом выполнении цикла первый элемент списка прибавляется к значению суммы (операция FIRST). Затем список укорачивается на первый элемент (команда присваивания и операция BF). После завершения повторений — вывод значения переменной, в которой накапливалась сумма. 5. Напишите процедуру для подсчета суммы цифр заданного числа. 6. Повторение и подготовка к заданию следующего параграфа. Напишите процедуру для возведения заданного числа в заданную степень. Примерные решения 1. это флаг :w repeat count :w [pr :w make "w bl :w] end 2. это перевертыш :w repeat count :w [ insert last :w make "w bl :w] end 3. это min :L make "min first :L repeat (count :L) — 1 [ if (first :L) > :min [make "min first :L] make "L bf :L] announce :min end 4, 5. Процедура для обеих задач работает одна и та же, только при запуске нужно по-разному задавать исходные данные. это сумма_цифр :n make "sum 0 repeat count :n [make "sum :sum + last :n make "n bl :n] announce :sum end Создание программы для перевода числа из недесятичной позиционной системы счисления в десятичнуюВ позиционных системах счисления число кодируется последовательностью цифр. Чтобы расшифровать эту последовательность, надо умножить каждую цифру на вес ее позиции в коде, а затем получившиеся произведения сложить. Например, в десятичной системе: 735, 1410 = 7·102 + 3·101 + 5·100 + 1·10-1 + 4·10-2 А в восьмеричной системе та же последовательность знаков расшифровывается по-другому: 735, 148 = 7·82 + 3·81 + 5·80 + 1·8-1 + 4·8-2 В общем случае, перевести число N в позиционную систему счисления с основанием p — значит представить его в виде: N = an pn + an–1 pn–1 + … + a1 p1 + a0 p0 + a–1 p–1 + a–2 p–2 + … +a–k p–k — где коэффициенты a — цифры, обозначающие числа, меньшие чем основание p. Последовательность с an по a0 — запись целой части числа, а последовательность с a–1 по a–k — запись дробной части. Для записи любого числа в позиционной системе счисления с основанием p необходимо и достаточно p различных цифр. Каждый разряд в позиционной системе “весит” в p раз больше своего соседа справа и в p раз меньше соседа слева. Вам необходимо запрограммировать перевод в десятичную систему счисления целого положительного числа N, записанного в системе счисления с основанием p, меньшим десяти. Будем расшифровывать запись целого числа с конца, с последней цифры. Вес последней позиции равен единице. Напоминание: число в Лого можно рассматривать как слово, то есть последовательность символов. Задания 7. Напишите процедуру для перевода натурального числа из недесятичной системы счисления с основанием до десяти в десятичную. Подсказка для варианта с командами повтора и присваивания. Сначала нужно задать начальное значение переменной, в которой будет постепенно накапливаться сумма произведений. Начальное значение этой переменной — ноль. Также нужно задать начальное значение веса позиции (вес позиции будет расти, значит, это тоже переменная величина). Начальное значение веса — единица, так как наше число — целое, последняя цифра показывает число единиц. А затем надо повторить столько раз, сколько цифр в записи, следующие действия: · последнюю цифру умножить на вес и прибавить полученное к сумме (то есть изменить значение суммы); · изменить значение веса — умножить текущее значение на p (то есть подготовиться к расшифровке предыдущей цифры в записи); · “отбросить” последнюю цифру (поскольку она уже “расшифрована”). 8. Используйте возможности среды ЛогоМиры, помогающие сделать работу с вашей программой удобной (кнопки, регуляторы-бегунки, окна диалога). 9. Добавьте в программу проверку введенного кода числа (цифры, входящие в код, должны быть меньше, чем основание системы счисления). Примерные решения 7. это перевод1 :n :p ; n — код числа, p — основание ; системы счисления make "sum 0 make "v 1 ; sum — переменная для накопления ; результата, v — вес разряда repeat count :n [ make "sum :sum + :v * last :n make "n bl :n make "v :v * :p] announce :sum end 8. На листе проекта появляется кнопка с именем перевод и бегунок с именем осн. и диапазоном от 2 до 10. это перевод question [Установите на бегунке основание системы счисления и введите код числа:] make "n answer перевод1 :n осн. announce (se [Код] :n [в системе счисления с основанием] осн. [- это десятичное число] :sum) end
это перевод1 :n :p make "sum 0 make "v 1 repeat count :n [ make "sum :sum + :v * last :n make "n bl :n make "v :v * :p] end
9. Написана вспомогательная процедура для проверки. Защита пока неполная. Главная процедура перевод остается без изменения. это перевод1 :n :p make sum 0 make "v 1 repeat count :n [проверка1 last :n make "sum :sum + :v * last :n make "n bl :n make "v :v * :p] end это проверка1 :sim if not :sim < осн. [announce [Недопустимый код в этой системе счисления!] stopall] end Написанная вами программа может расшифровывать только такие числа, которые записаны цифрами. То есть работает только с системами счисления с основанием до десяти (включительно). Если же основание системы счисления больше десяти, то вместо недостающих цифр принято использовать заглавные латинские буквы. A — это “цифра” десять; B — это “цифра” одиннадцать, и т.д. Поскольку латинских букв двадцать шесть (от A до Z), то легко подсчитать, что таким образом можно записывать числа в системах счисления с основанием до тридцати шести. Как расширить возможности программы, чтобы она могла расшифровывать записи чисел, в которых встречаются и цифры, и заглавные латинские буквы? Для этого можно использовать коды символов. Посмотрим в кодовую таблицу. Коды цифр — от 48 до 57; коды заглавных латинских букв — от 65 до 90. Вполне возможно сформулировать зависимость между кодом буквы и соответствующим этой букве числом: (A) 65 — 10 (B) 66 — 11 (C) 67 — 12 …………… (Z) 90 — 25 Задания 10. Измените программу так, чтобы она воспринимала заглавные латинские буквы в качестве “цифр” в системах счисления от 10 до 36. 11. Процедура проверки пока не учитывает все случаи неправильного ввода. Усовершенствуйте проверку введенного кода числа так, чтобы сообщение об ошибке выдавалось и в том случае, когда в коде встречаются символы, отличные от цифр и заглавных латинских букв. Примерные решения Диапазон значений бегунка с именем осн. стал больше — от 2 до 36. Добавилась вспомогательная процедура для проверки, является ли символ цифрой или заглавной латинской буквой. Главная процедура проверка и вспомогательная проверка1 не изменились. это перевод1 :n :p make "sum 0 make "v 1 repeat count :n [make "sim last :n проверка2 :sim ; проверяем, является ли символ ; цифрой или заглавной лат. буквой if and (ascii :sim) > 64 (ascii :sim) < 91 [make "sim (ascii :sim) — 55] ; если символ — заглавная латинская ; буква, заменяем его на число проверка1 :sim ; проверяем, есть ли такая цифра ; в данной системе счисления make "sum :sum + :v * :sim make "n bl :n make "v :v * :p] end
это проверка2 :sim if not or and (ascii :sim) > 64 (ascii :sim) < 91 ; коды заглавных лат. букв — с 65 до 90 and (ascii :sim) > 47 (ascii :sim) < 58 ; коды цифр — с 48 по 57 [announce [В коде должны быть только цифры и заглавные латинские буквы!] stopall] end
Описание функций В полученной программе несколько раз встречается громоздкое выражение для выяснения, попадает ли код символа в заданный диапазон. Например, при проверке “правильности” введенного символа, записанного в переменную sim: if not or and (ascii :sim) > 64 (ascii :sim) < 91 and (ascii :sim) > 47 (ascii :sim) < 58 [announce [Недопустимый код!] stopall] Когда в программе несколько раз встречается один и тот же набор действий, мы описываем вспомогательную процедуру. Но в нашем случае повторяются не действия, а проверка некоего условия. И это подходящий случай, чтобы познакомиться с описанием и использованием функций. Начиная работу с новым файлом в Лого-среде, мы можем использовать некоторый изначально определенный набор команд и операций. Но затем этот набор можно расширить. Создавая новую процедуру, вы фактически добавляете еще одну новую команду. Ее можно использовать наравне со всеми остальными командами. А можно ли таким же образом расширить перечень операций? Да, пользователь может описать необходимую для него функцию. Например, несколько раз встречающиеся в программе вычисления или проверки условий. Функцию можно будет использовать наравне с операциями языка Лого. Использование функций во многих случаях может сделать программу компактной, более понятной. Таким образом, процедуры пополняют набор команд языка, а функции пополняют набор операций. Для описания функций служит специальная команда OUTPUT — вывести, считать результатом (сокращенный вариант — OP). Пусть в переменной sim хранится символ. Напишем функцию для проверки, попадает ли код символа в заданный диапазон от a до b: это усл :a :b op and (ascii :sim) > :a (ascii :sim) < :b end В вольном переводе получится так: считать результатом верность утверждения, что код символа находится в диапазоне от a до b (концы отрезка не включены). Получилась логическая функция, ее можно использовать, например, в команде ветвления. С использованием этой функции команда условного ветвления, приведенная в начале параграфа, упростится: if not or усл 64 91 усл 47 58 [announce [Недопустимый код!] stopall] Разберем еще пример с вычислениями. Пусть необходимо вычислить площадь поверхности треугольной пирамиды. Все четыре грани такой пирамиды — треугольники. Их стороны — ребра пирамиды — обозначим буквами a, b, c, d, e, f.
Для вычисления площади треугольника по известным трем сторонам a, b, c существует формула Герона:
где p — полупериметр треугольника,
то есть Напишем вспомогательную процедуру для вычисления площади произвольного треугольника: это S_тр :a :b :c make "p (:a + :b + :c) / 2 make "S sqrt :p * (:p — :a) * (:p — :b) * (:p — :c) end Это процедура с тремя параметрами, вычисленное значение запоминается во вспомогательной переменной S. А вот процедура для вычисления площади всей поверхности пирамиды: это S_пов :a :b :c :d :e :f S_тр :a :b :c make "S1 :S S_тр :a :d :f make "S2 :S S_тр :b :d :e make "S3 :S S_тр :c :e :f make "S4 :S pr :S1 + :S2 + :S3 + :S4 end Здесь вспомогательная процедура вычисления площади треугольника вызывается четыре раза, площади четырех граней пирамиды записываются в четыре вспомогательные переменные — S1, S2, S3, S4. А теперь посмотрите, как эту же задачу можно решить, описывая не процедуры, а функции. это S_тр :a :b :c MAKE "p (:a + :b + :c) / 2 OP sqrt :p * (:p — :a) * (:p — :b) * (:p — :c) end Последнюю строку можно перевести так: считать результатом ... Это уже описание функции благодаря специальной команде OP, превращающей описание процедуры в описание функции. это S_пов :a :b :c :d :e :f OP (S_тр :a :b :c) + (S_тр :a :d :f) + (S_тр :b :d :e) + (S_тр :c :e :f) end Этот текст тоже стал описанием функции, возвращающей результат — сумму площадей четырех треугольников. Теперь новую функцию можно использовать, например, так: PR S_пов 3 4 5 5 5 4 Вычисленный функцией S_пов результат передается команде PR. Описание функций (вместо процедур) позволило значительно сократить объем программы и избежать введения вспомогательных переменных. Специальная команда OP может использоваться только в описаниях; она возвращает значение и останавливает процедуру. Проверьте приведенный пример в вашем файле ЛогоМиров. Результатом функции в Лого может быть число, слово или сколь угодно сложный список. Описание функции на листе программ — не единственный способ создать функцию. Когда вы помещаете на лист проекта бегунок, вы создаете новую функцию с соответствующим именем. Возвращаемый этой функцией результат — число, на которое указывает движок. Когда вы помещаете на лист текстовое окно, то вы также создаете новую функцию. Возвращаемый этой функцией результат — слово (все содержимое текстового окна). В обоих случаях это функции без параметров. Задание 12. Добавьте вспомогательную логическую функцию проверки, попадает ли код символа в заданный диапазон, используйте ее в программе перевода. Примерное решение На листе проекта должен быть бегунок с именем осн. и диапазоном значений от 2 до 36. Приведем полный текст программы для перевода из недесятичной системы в десятичную: это перевод question [Установите на бегунке основание системы счисления и введите код числа:] make "n answer перевод1 :n осн. announce (se [Код] :n [в системе счисления с основанием] осн. [- это десятичное число] :sum) end
это перевод1 :n :p make "sum 0 make "v 1 repeat count :n [make "sim last :n проверка2 :sim if усл 64 91 [make "sim (ascii :sim) — 55] проверка1 :sim make "sum :sum + :v * :sim make "n bl :n make "v :v * :p] end
это усл :a :b op and (ascii :sim) > :a (ascii :sim) < :b end
это проверка1 :sim if not :sim < осн. [announce [Недопустимый код в этой системе счисления!] stopall] end
это проверка2 :sim if not or усл 64 91 усл 47 58 [announce [В коде должны быть только цифры и заглавные латинские буквы!] stopall] end В случае неправильно введенного кода процедуры проверка1 или проверка2 выдают сообщение об ошибке и прерывают выполнение программы. Операции формирования слов и списков Если в языке Лого есть средства для разборки на составные части слов и списков, то должны быть и средства для составления сложных данных из элементов. Именно они нам понадобятся, чтобы написать вторую часть программы — для перевода из десятичной системы в недесятичную. Операция WORD служит для сборки “по частям” слова. Например:
У операции WORD может быть больше двух параметров, и в таком случае, по правилам Лого, все они вместе с именем операции должны быть заключены в круглые скобки:
Для получения списка из заданных элементов в Лого имеется несколько операций. Одна из них — SE (от англ. sentence — предложение). Эта операция вам уже знакома, вы много раз использовали ее при программировании диалогов. Разберем еще раз детально пример использования операции SE в диалоге.QUESTION [Как Вас зовут?] MAKE "N ANSWER ANNOUNCE (SE[Приятно познакомиться,] :N [!]) Выводимая на экран строка состоит из трех разнородных частей. Сначала идет одинаковый всегда текст, затем — значение переменной, затем опять одинаковый для всех случаев текст. То есть выводимые данные — структура, имеющая три составные части. Это список из трех элементов. Команда вывода ANNOUNCE получила в качестве параметра один общий список, возвращенный операцией SE.Если у операции SE больше двух параметров, то все они вместе с именем операции должны быть заключены в круглые скобки. Новые операции языка Лого, которые служат для формирования составных данных из частей:
Задания 13. Напишите процедуру, выдающую пароль — слово, являющееся случайным набором букв. Длина слова задается пользователем, то есть процедура должна быть с параметром. Буквы — русские строчные. Подсказка. Перед циклом необходимо установить начальное значение переменной, в которой будет постепенно “накапливаться” слово. Начальное значение — пустое слово. В цикле повторяется одно-единственное действие — изменение значения переменной с помощью операции WORD, приклеивающей к слову выбранную случайным образом букву. Выбрать букву помогут операции CHAR и RANDOM. Другими словами, выбирать нужно символ со случайным кодом. Это случайное число должно находиться на отрезке, соответствующем в кодовой таблице малым русским буквам. 14. Напишите процедуру, преобразующую слово следующим образом: кенгуру енгурук нгуруке гурукен урукенг рукенгу укенгур кенгуру Такое преобразование слова можно пояснить следующим образом. Представьте себе, что слово напечатано на полоске бумаги. Затем концы полоски склеиваются и получается кольцо. Началом слова тогда можно считать любую букву. Примерные решения 13. это пароль :n make "p " ; начальное значение переменной — ; пустое слово repeat :n [make "p word :p char 224 + random 32] ; приклеиваем букву с кодом от 224 ; до 255 announce :p end 14. это кольцо :w repeat count :w [pr :w make "w word bf :w first :w] end Рекурсивные функции Вы умеете описывать и использовать рекурсивные процедуры, а теперь научитесь создавать рекурсивные функции. Это нужно нам, чтобы запрограммировать обратный перевод, из десятичной системы в недесятичную. Разберем пример: возведение числа в заданную степень. Вы уже писали процедуру с командами повтора и присваивания. Такую организацию повторений в программе называют итерацией. Эту итеративную процедуру можно превратить в функцию: это степ_ит :N :K make "R 1 repeat :k [make "R :R * :N] op :R end Вычисления начинаются с единицы. В цикле каждый раз вычисляется очередное значение умножением на N. Но можно действовать по-другому и записать рекурсивную формулу: Nk = N · N k –1; N0 = 1 То есть функция возведения в степень определяется через саму себя (только с пониженным показателем). А когда показатель равен нулю, результатом считать единицу. Попробуем это записать на языке Лого: это степ_рек :N :K if :K = 0 [op 1] op :N * степ_рек :N :K — 1 end В этом случае вычисления начинаются, наоборот, с конца и проводятся как бы в обратном направлении, пока показатель степени не станет равным нулю. В рекурсивном варианте запись всегда содержит условие остановки процесса, выхода из повторений. В первой строчке как раз и записано это условие. Разберем еще пример — с обработкой слова. Пусть нужно “перевернуть” слово: крокодил — лидокорк, компьютер — ретюьпмок… Вы уже писали итеративную процедуру для такого переворота. Теперь попробуем дать рекурсивное определение “перевертышу”: перевертыш слова — это последняя буква, к которой “приклеен” перевертыш остатка слова (то есть слова без последней буквы). Напишем рекурсивную функцию получения перевернутого слова: это наоборот :w if empty? :w [op " ] op word last :w наоборот bl :w end Здесь остановка рекурсивного процесса запрограммирована тогда, когда последний “остаток” пустой (нет ни одной буквы). Проверьте приведенные примеры в вашем файле ЛогоМиров. Итак, чтобы описать рекурсивную функцию, надо записать рекурсивную формулу или сформулировать рекурсивное определение. Разобранные примеры совсем простые, и выигрыш от использования рекурсивной функции пока не очевиден, но во многих случаях запись рекурсивной функции намного короче и красивее. А в некоторых случаях по-другому, не рекурсивно, описать процесс затруднительно. Правда, исполнение рекурсивных программ требует от компьютера больше ресурсов (может не хватить места в оперативной памяти), занимает больше времени, чем исполнение итеративных программ. Задания 15. Напишите два варианта для функции вычисления факториала натурального числа (рекурсивный и итеративный). Вот два разных определения факториала: N! = 1 · 2 · 3 · … · N; N! = N · (N – 1)! ; 1! = 1. 16. Напишите функцию определения наибольшего числа из двух заданных. Затем напишите рекурсивную функцию нахождения максимального числа в списке чисел, опираясь на следующее рекурсивное определение: · если в списке всего одно число, считать результатом это число; · иначе считать результатом наибольшее из двух чисел: первого в списке и наибольшего в “остатке” списка (то есть списка, полученного “отбрасыванием” первого элемента). Сравните с написанной ранее итеративной процедурой нахождения минимума в списке чисел. Решения 15. это факт_ит :n make "P 1 make "K 0 repeat :n [ make "K :K + 1 make "P :P * :K ] op :P end
это факт_рек :n if :n = 1 [op 1] op :n * факт_рек :n — 1 end
16. это max_2 :a :b ifelse :a > :b [op :a][op :b] end
это max :L if 1 = count :L [op first :L] op max_2 first :L max bf :L end Создание программы для перевода числа Наша следующая задача — перевод числа, записанного в десятичной системе счисления, в недесятичную. Существует подходящий для программирования алгоритм перевода, который часто называют правилом деления. Необходимо последовательно делить исходное число и получаемые частные на основание p, выписывая остатки. Деление продолжается до тех пор, пока очередное частное не станет равно нулю. Затем нужно выписать полученные остатки в обратном порядке, заменив их цифрами p-ичной системы счисления. Получившаяся запись — код числа в системе с основанием p. Здесь имеется в виду целое частное, то есть надо выяснить, сколько раз одно число целиком “уложится” в другое. Например, целое частное от деления семнадцати на пять равно трем; а целое частное от деления трех на пять равно нулю. Пример 1. Перевести десятичное число 37 в двоичную систему счисления.
Пример 2. Перевести десятичное число 218 в шестнадцатеричную систему счисления.
Для нахождения остатка от деления одного целого числа на другое в Лого существует операция REMAINDER (остаток) с двумя параметрами.
А для получения целого частного можно использовать операцию INT (от англ. integer, целое). Она возвращает целую часть входного параметра (числа). Например:
Вот как можно сформулировать рекурсивное определение перевода десятичного числа n в систему счисления с основанием p: · если n < p, то считать результатом n; · иначе считать результатом остаток от деления n на p, “приклеенный” в конец слова, полученного от перевода целого частного n и p. Задания 17. С помощью правила деления переведите число двести в двоичную, троичную, пятеричную, шестнадцатеричную системы счисления. Проверьте результаты с помощью написанной вами программы для перевода недесятичных чисел. 18. Используя операции REMAINDER и INT, найдите целые частные и остатки для пар чисел 63 и 7; 63 и 117; 63 и 5. 19. Напишите рекурсивную функцию перевода десятичного числа в недесятичную систему счисления с основанием до 10. Решение это перевод2 :n :p if :n < :p [op :n] op word перевод2 int :n / :p :p remainder :n :p end Пока возможности программы ограниченны: основание системы счисления не может быть больше десяти, код числа может состоять только из цифр. Чтобы реализовать перевод в системы счисления с основаниями от двух до тридцати шести, надо написать функцию преобразования числа (остатка) в цифру недесятичной системы счисления. То есть создать функцию преобразования десяти в букву A, тринадцати — в букву D, и т.д. Сделать это можно, руководствуясь кодами символов. Коды цифр — от 48 до 57; коды заглавных латинских букв — от 65 до 90. После такого усовершенствования можно будет наконец объединить все написанные процедуры и функции в одной общей программе перевода. 20. Напишите функцию преобразования числа от нуля до тридцати шести в цифру недесятичной системы счисления (то есть в обычную цифру, если заданное число меньше десяти, а в противном случае — в заглавную латинскую букву). Используйте для этого данные из кодовой таблицы. 21. Используя полученную функцию преобразования, усовершенствуйте функцию перевода десятичного числа в другую систему счисления. Теперь диапазон систем счисления будет такой: от двух до тридцати шести. 22. Объедините все написанные процедуры и функции. В окончательном варианте программа должна переводить заданное число из одной системы счисления в другую. 23. Проверьте полученную программу, ее реакцию на неправильный ввод. Выясните границы применения программы: какое самое большое число может быть переведено? Какие функции или операции ограничивают вводимое для перевода число? Какие у вас есть предположения о причине ограничения? Полный текст программы На листе проекта должны быть два
бегунка с одинаковым диапазоном от 2 до 36 и
именами осн_1 и осн_2.
это перевод2 :n :p if :n < :p [op симв :n] op word перевод2 int :n / :p :p симв remainder :n :p end это симв :k ifelse :k < 10 [op :k][op char :k + 55] end это перевод1 :n :p make "sum 0 make "v 1 repeat count :n [ make "sim last :n проверка1 :sim if усл 64 91 [make "sim (ascii :sim) — 65 + 10] проверка2 :sim make "sum :sum + :v * :sim make "n bl :n make "v :v * :p] end это усл :a :b op and (ascii :sim) > :a (ascii :sim) < :b end это проверка1 :sim if not or усл 47 58 усл 64 91 [announce [В коде должны быть только цифры и заглавные латинские буквы!] stopall] end это проверка2 :sim if not :sim < осн_1 [announce [Недопустимый код в этой системе счисления!] stopall] end это перевод question [Установите на бегунках основания систем счисления и введите код числа:] make "n answer перевод1 :n осн_1 ; результат перевода в десятичную систему оказался в переменной sum announce (se [Код] :n [в системе счисления с основанием] осн_1 [- это] перевод2 :sum осн_2 [в системе счисления с основанием] осн_2) end
Наибольшее число, которое может быть переведено, определяет операция REMAINDER. Предел для этой операции — десятичное число 2 147 483 646 или 231–1. Можно сделать предположение, что целое число для среды ЛогоМиры 2.0 занимает 4 байта, один разряд отводится под знак. Итак, подведем итог. Постепенно создавая модули программы, учащиеся освоили на начальном уровне работу со структурами данных — словами и списками. А также познакомились с описанием и использованием функций, в том числе рекурсивных функций. Причем, как я замечаю, некоторые учащиеся очень увлекаются загадочными рекурсивными функциями. То есть описанный проект и система заданий обеспечивают мотивацию (конечно, для достаточно сильных учеников). Во-первых, получается полезная программа, а во-вторых, привлекательными являются новые и интересные приемы программирования. Правда, полученная программа не отличается единством стиля: перевод1 — это процедура, а перевод2 — функция. Но это объясняется тем, что задания как бы проводят учащегося “за руку” от стандартного процедурного подхода к функциональному рекурсивному. И, конечно, могут дать только первое представление о различии этих подходов. Ал. Ге. Юдина | ||||||||||||||||||||||||||||||||||||||||||||||||
|
|
,
.
