MULISP8

File: MULISP6.LES (c) 03/10/92 СПбЭТУ

CLRSCRN

В течение этого урока мы обсудим примитивные числовые функции

muLISPа и технику программирования математических функций.

muLISP позволяет работать с целыми числами с неограниченным

числом знаков и рациональными числами с заданной точностью. Это озна-

чает, что ограничение на длину целых чисел задает лишь доступный объем

памяти. В принципе можно оперировать целыми числами, состоящими из

тысяч цифр. Это делает возможным использование muLISPа для исследова-

ний в области теории чисел.

По принципу умолчания muLISP обеспечивает вычисления над рацио-

нальными числами с точностью 7 знаков. ( В главе 5 Руководства по

использованию muLISPа (muLISP Reference Manual) описывается функция

PRECISION, использование которой позволяет повысить точность арифмети-

ческих действий над действительными числами.)

CONTINUE

Начнем обсуждение с примитивных числовых функций muLISPа. Функции

+, -, *, и / обозначают сложение, вычитание, умножение и деление,

соответственно. Во многих распространенных языках программирования Вы

можете записывать арифметические выражения с использованием инфиксной

нотации (в которой знак операции ставится между операндами). Например:

3 * 4 + 5

Поскольку LISP является языком функционального программирования,

для написания арифметических выражений употребляется функциональная

нотация, при которой знак операции стоит на первом месте, а затем пе-

речисляются операнды. Например, предыдущее арифметическое выражение

будет записано следующим образом:

$ (+ (* 3 4) 5)

Во время паузы потренируйтесь в вычислениях с использованием ука-

занных четырех арифметических действий. Когда Вам захочется вернуться

в среду урока, обратитесь к функции (RETURN).

BREAK

CLRSCRN

Одно из преимуществ функциональной нотации перед инфиксной заклю-

чается в том, что вместо двух Вы можете использовать произвольное

число операндов. Функции +, *, -, и / позволяют употреблять различное

число аргументов. Например:

$ (+ 45 -23 57)

$ (* 1 2 3 4 5)

Во время паузы с помощью тестирования функций - и / выясните, что

возвращается в качестве результата, если при обращении употреблено бо-

лее двух аргументов.

BREAK

CLRSCRN

Если при вызове числовой функции Вы употребили нечисловые аргу-

менты, то происходит прерывание и появляется сообщение об ошибке

"Nonnumeric Argument" (Нечисловой аргумент), за которым следует

подсказка о необходимости выбрать одну из опций (режимов):

Abort, Break, Continue, Top-level, Restart, System?

(Прекратить, Прервать, Продолжить, Верхний-уровень, Рестарт, Система?)

В таком случае Вы должны выбрать одну из опций, нажав на клавишу

с латинской буквой, совпадающей с первой буквой названия выбранного

Вами режима. Подробное описание функции BREAK (Прервать) приводится в

главе 5 Руководства по использованию muLISPа (muLISP Reference

Manual). На следующем экране Вы увидите пояснения, которые помогут Вам

выбирать нужную опцию.

CONTINUE

Сведения о режимах, которые можно выбирать при прерывании из-за

ошибки:

Abort (Прекратить): прекращает выполнение, передает управление на те-

кущий уровень цикла "прочитать-оценить-напечатать"

(the read-eval-print loop) и выдает подсказку для

пользователя, означающую, что можно ввести новое

предложение.

Break (Прервать): временно приостанавливает выполнение и выдает под-

сказку для пользователя, свидетельствующую о воз-

можности ввода. Функция, вызвавшая диагностику

ошибки, может быть определена по значению перемен-

ной BREAK. Для возвращения из режима приостановки

вычислений нужно ввести (RETURN expn), где <expn>

(expression - выражение) определяет значение, ко-

торое Вас интересует.

CONTINUE

Continue (Продолжить): продолжает выполнение, вызывая ту функцию, ко-

торая была прервана при выдаче сообшения об ошибке.

Top-level (Верхний-уровень): прекращает выполнение, передает управле-

ние на верхний уровень цикла "прочитать-оце-

нить-напечатать" (the read-eval-print loop) и вы-

дает подсказку для пользователя, означающую, что

можно ввести новое предложение.

Restart (Рестарт): ликвидирует существующую среду muLISPа и снова вы-

зывает muLISP.

System (Система): прекращает работу интерпретатора muLISP и передает

управление операционной системе.

CONTINUE

Пожалуй, достаточно говорить об ошибках, давайте вернемся к мате-

матике ! Функция "факториал" от числового аргумента имеет большое зна-

чение в теории вероятностей. Факториал от неотрицательного целого N,

обозначаемый N!, может быть рекурсивно определен с помощью следующих

формул:

0! = 1,

N! = N*(N-1)! если N > 0

Соответствующая запись на muLISPе для функции FACTORIAL:

$ (DEFUN FACTORIAL (N)

((EQL N 0) 1)

(* N (FACTORIAL (- N 1))) )

$ (FACTORIAL 5)

Это эффективное определение, однако при больших значениях N воз-

можно появление ошибки из-за полного израсходования памяти при пере-

полнении стека. Во время паузы напишите итеративный вариант определе-

ния функции FACTORIAL и проверьте его работу на примерах. Подсказка:

Вам придется ввести накапливающую переменную для получения результата.

BREAK

Приведем итеративное определение функции FACTORIAL и пример ее

тестирования:

$ (DEFUN FACTORIAL (N

% Local: % RSLT)

(SETQ RSLT 1)

(LOOP

((ZEROP N) RSLT)

(SETQ RSLT (* N RSLT))

(SETQ N (- N 1)) ) )

$ (FACTORIAL 100)

Как показывает приведенный пример, muLISP позволяет работать с

очень большими числами. В определении функции для вычисления факториа-

ла мы использовали примитивную функцию-распознаватель ZEROP (предикат,

выясняющий, имеет ли аргумент нулевое значение) . Обращение (ZEROP N)

эквивалентно обращению (EQL N 0), но несколько более эффективно.

CONTINUE

А теперь рассмотрим новый пример.

Числовая последовательность, имеющая название "числа Фибоначчи",

встречается в природе в самых неожиданных местах. N-ое число Фибонач-

чи, обозначаемое как F(N), может быть рекурсивно определено следующим

образом:

F(0) = 1,

F(1) = 1,

F(N) = F(N-1) + F(N-2) для N > 1.

Эквивалентная запись на muLISPе определения функции FIBONACCI :

$ (DEFUN FIBONACCI (N)

((ZEROP N) 1)

((EQL N 1) 1)

(+ (FIBONACCI (- N 1)) (FIBONACCI (- N 2))) )

$ (FIBONACCI 10)

Во время паузы попробуйте оценить эффективность написанного алго-

ритма определения функции FIBONACCI, вызывая эту функцию для аргумен-

тов, образующих возрастающую последовательность.

BREAK

CLRSCRN

Как Вы, наверное, убедились, это очень неэффективный алгоритм.

Дело в том, что при вычислении N-го числа Фибоначчи (N-2)-ое число Фи-

боначчи придется вычислять дважды, (N-3)-ье - три раза, (N-4)-ое -

пять раз, а все последующие - все большее число раз.

Поскольку это рекурсивный алгоритм, большинство программистов

пришло бы к заключению, что виновата рекурсия, и некоторые пользовате-

ли попытались бы создать более трудно воспринимаемое итеративное опре-

деление для повышения эффективности вычислений. Однако проблема вовсе

не в применении рекурсии, а в самом алгоритме.

Вместо того, чтобы начинать вычисления с попытки определить N-ое

число Фибоначчи и при этом в рекурсивном процессе продвигаться "вниз"

к нулю, более эффективный способ - начать с нуля и продвигаться

"вверх" к N-ому числу Фибоначчи, запоминая два самых последних из вы-

численных чисел Фибоначчи как значения двух переменных.

Во время паузы попробуйте создать более эффективное рекурсивное

определение функции Фибоначчи с названием FIB. Сравните эффективность

работы функций FIB и FIBONACCI.

BREAK

Эффективное рекурсивное определение функции вычисления чисел Фи-

боначчи:

$ (DEFUN FIB (N F1 F2)

((ZEROP N) F1)

(FIB (- N 1) (+ F1 F2) F1) )

$ (FIB 10 1 0)

$ (FIBONACCI 10)

FIB является функцией трех аргументов. Первый аргумент - это само

число N, второй аргумент 1, а третий аргумент 0. Если Вам более по ду-

ше функция Фибоначчи с одним аргументом, Вы можете определить "обрам-

ляющую" ( a "front-end" ) функцию, которая вызывает FIB с подходящими

значениями второго и третьего аргументов.

Тем, кто еще не убедился в элегантности и эффективности рекурсии,

мы предлагаем написать итерационное определение функции вычисления

чисел Фибоначчи и сравнить его с приведенным выше определением. Если

Вы уже поверили в рекурсию, можете продолжать.

CONTINUE

Возведение выражения в целую степень - это важная математическая

операция. Для того, чтобы возвести N в M-ую степень, Вы должны просто

напросто умножить N само на себя M раз.

Во время паузы напишите итеративное определение функции возведе-

ния в степень POWER как функции двух аргументов.

BREAK

Итеративное определение функции POWER:

$ (DEFUN POWER (N M

% Local: % RSLT )

(SETQ RSLT 1)

(LOOP

((ZEROP M) RSLT)

(SETQ RSLT (* N RSLT))

(SETQ M (SUB1 M)) ) )

$ (POWER 2 10)

Вызов примитивной функции SUB1 в приведенном выше примере эквива-

лентен вызову (- N 1), однако этот вызов предпочтительнее с точки зре-

ния эффективности вычислений. ADD1 также представляет собой примитив-

ную функцию muLISPа.

Существует еще более эффективный способ вычисления функции возве-

дения в целую степень. Перейдем к следующему экрану.

CONTINUE

Примем во внимание следующие обстоятельства:

1. Если M - четное число, то возведение N в M-ую степень эквива-

лентно возведению "квадрата" N в (M/2)-ую степень.

2. Если M - нечетное число, то возведение N в M-ую степень можно

представить как произведение N на N, возведенное в (M-1)-ую

степень.

Для реализации алгоритма Вам потребуется примитивная функ-

ция-распознаватель EVENP (even - четный). Эта функция возвращает зна-

чение T в том и только в том случае, когда ее аргумент является четным

числом; в противном случае она возвращает значение NIL.

Во время паузы напишите рекурсивное определение функции РOWER,

используя приведенные выше соображения.

BREAK

Эффективное рекурсивное определение функции POWER:

$ (DEFUN POWER (N M)

((ZEROP M) 1)

((EVENP M)

(POWER (* N N) (/ M 2)) )

(* N (POWER N (SUB1 M))) )

$ (POWER 10 100)

CONTINUE

Примитивная функция TRUNCATE (усекать, обрезать) полезна для пре-

образования рациональных чисел в целые. Если <n> является числом, то

обращение (TRUNCATE n) "усекает" <n> до ближайшего целого в направле-

нии к нулю:

$ (TRUNCATE 7/3)

$ (TRUNCATE -0.95)

Если функция TRUNCATE вызывается с двумя аргументами, то она

возвращает "усеченное" частное. Заметьте, что (TRUNCATE n m) эквива-

лентно (TRUNCATE (/ n m)):

$ (TRUNCATE 7 3)

$ (TRUNCATE -46.3 5.2)

CONTINUE

Функция TRUNCATE возвращает "усеченное" целое частное. Примитив-

ная функция REM возвращает остаток от деления первого аргумента на

второй. Функции TRUNCATE и REM определены таким образом, что они вы-

числяют целую часть частного и остаток от деления. Если (TRUNCATE n m)

возвращает целое q, а (REM n m) возвращает число r, то

n = q*m + r

Иногда нужно получить целую часть частного и остаток от деления

одного числа от другого обращением к одной функции. Примитивная функ-

ция DIVIDE возвращает точечную пару, содержащую целую часть частного и

остаток от деления первого аргумента на второй.

$ (TRUNCATE 7 3)

$ (REM 7 3)

$ (DIVIDE 7 3)

CONTINUE

Наибольший Общий Делитель (Greatest Common Divisor или сокращенно

GCD) двух целых чисел - это наибольшее целое, на которое без остатка

делится каждое из двух чисел. Алгоритм Евклида для нахождения наиболь-

шего общего делителя двух чисел может быть сформулирован следующим об-

разом:

1. Если N = 0, то GCD (N, M) = M;

2. В противном случае GCD (N, M) = GCD (M mod N, N).

Во время паузы попробуйте запрограммировать вычисление наибольше-

го общего делителя, определив функцию GCD с использованием алгоритма

Евклида, и проверьте ее работу на тестовых примерах. Используйте функ-

цию REM для определения M mod N.

BREAK

Рекурсивное определение функции GCD с использованием алгоритма

Евклида:

$ (DEFUN GCD (N M)

((ZEROP N) M)

(GCD (REM M N) N) )

$ (GCD 21 56)

В действительности функция определения наибольшего общего делите-

ля GCD и функция определения наименьшего общего кратного LCM (Least

Common Multiple) - примитивные функции muLISP. Эти примитивные функции

работают быстрее и позволяют задавать произвольное число аргументов.

CONTINUE

В заключение необходимо упомянуть примитивные функции, вычисляющие

отношения =, /=, <, >, <=, и >=. Например:

$ (= 34 34.0) ;Проверка на равенство

$ (/= 3/4 0.75) ;Проверка на неравенство

$ (< 67 45) ;Проверка на "меньше чем"

$ (>= 19 17 17) ;Проверка на "больше или равно"

Как показывает последний пример, функции, вычисляющие значение

отношения, могут иметь более двух аргументов. Если при вызове употреб-

лены нечисловые аргументы, то возникает прерывание и сообщение об

ошибке: "Nonnumeric Argument" (Нечисловой аргумент).

CONTINUE

Чтобы узнать, принадлежит ли введенное число заданному числовому

интервалу, можно вызвать функцию "<" с 3 аргументами. Например, чтобы

определить, является ли "g" строчной буквой, введите

$ (< 96 (ASCII 'g) 123)

Функция ASCII возвращает ASCII-код заданного знака. Если задать

число в пределах от 0 до 256, то функция ASCII возвратит обозначение

соответствующей буквы.

Во время паузы напишите определение функции-распознавателя

LOWERCASE, которая определяет, является ли введенный символ строчной

буквой.

BREAK

Функция-распознаватель LOWERCASE :

$ (DEFUN LOWERCASE (CHAR)

(< 96 (ASCII CHAR) 123) )

$ (LOWERCASE 'g)

CONTINUE

Давайте завершим урок написанием функции, которая производит сор-

тировку чисел в возрастающем порядке. Мы не будем уделять большое вни-

мание вопросу эффективности сортировки, поэтому реализуем простой ал-

горитм "вставки", который будет вполне удовлетворительно работать с

короткими списками.

Прежде всего нам понадобится функция, которая вставляет число на

такое место в сортированный список, чтобы список остался сортированным.

Во время паузы напишите функцию INSERT-NUM, которая вставляет заданное

число NUM в сортированный список LST. Используйте либо итерацию, либо

рекурсию в соответствии с Вашим вкусом .

BREAK

Рекурсивное определение функции INSERT-NUM:

$ (DEFUN INSERT-NUM (NUM LST)

((NULL LST)

(LIST NUM) )

((< NUM (CAR LST))

(CONS NUM LST) )

(CONS (CAR LST) (INSERT-NUM NUM (CDR LST))) )

$ (INSERT-NUM 12 '(5 9 11 14 19 21))

Во время паузы напишите функцию NUMBER-SORT для сортировки задан-

ного числового списка с использованием только что написанной функции

INSERT-NUM.

BREAK

Рекурсивное определение функции NUMBER-SORT:

$ (DEFUN NUMBER-SORT (LST)

((NULL LST) NIL)

(INSERT-NUM (CAR LST) (NUMBER-SORT (CDR LST))) )

$ (NUMBER-SORT '(34 23 -14 27 56 22 83))

Встроенная функция сортировки SORT основана на использовании бо-

лее эффективного алгоритма слияния. Если <test> - знак операции срав-

нения, (SORT list test) сортирует исходный список <list> и возвращает

в качестве значения список, сортированный в соответствии с <test>.

Например:

$ (SORT '(34 23 -14 27 56 22 83) '<)

На этом мы завершим обсуждение техники числового программирова-

ния на muLISPе. Поздравляем Вас с успешным освоением материала урока.

CONTINUE

$ (RDS)