Урок №1

Вид материала

Содержание

Подобный материал:

1 2

30

УРОК № 5

Этот урок представляет примитивные числовые функции языка MuLISP и некоторые возможности, полезные для записи эффективных математических функций.

MuLISP обеспечивает пользователя и неограниченной точностью целой арифметики и, определяемой пользователем, точностью рациональной арифметики. Это значит, что единственное ограничение размера целых чисел -доступная память ЭВМ. Целые числа, состоящие из тысяч цифр, возможны. Это делает MuLISP полезным в исследованиях в области теории чисел и криптографии.

По умолчанию MuLISP для рациональной арифметики обеспечивает приблизительно 7 цифр точности. Это аппроксимирует точность арифметики с плавающей запятой. Описание функции PRECISION в Главе 5 Справочного описания MuLISP подробно описывает увеличение точности рациональной арифметики.

Это умножение и деление соответственно. Во многих стандартных языках программирования вы вводите числовые выражения использующие следующе представление: операторы ставятся между операндами.

Пример:

2*3-1

Так как LISP - функциональный язык программирования, функциональное представление наиболее естественно и непротиворечиво для числовых выражений.

Пример:

вышеупомянутое выражение вводится так:

$ (- (* 2 3) 1)

Одно из приемуществ функционального представления перед операторным состоит в том, что вы не ограничиваетесь двумя операндами для каждой операции. Функции +, *, -, / могут действовать для переменного числа параметров.

Пример:

$(+ 12-19 34)

$ (* 1 2 3 4 5)

Если числовая функция случайно вызывается с нечисловым параметром, то на экране появится сообщение об ошибке: "Nonnumeric Argument", сопровождаемое обращением к функции обработки ошибок и подсказкой:

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

Тогда вы должны выбрать одну из пяти опций посредством ввода первого символа. Подробное описание функции BREAK находится в Главе 5 Справочного описания MuLISP.

31

Описание ошибок:

Abort: аварийное прекращение работы, возвращение прямо к текущему уровню цикла read-eval-print и предложение пользователю дальнейшего ввода.

Break: ввременно приостанавливает выполнение и запрашивает пользователя о вводе.

Функция обработки ошибок может определяться при исследовании значения переменной BREAK. Для возврата напечатайте (RETURN expn), где <ехрп> - значение, которое будет возвращено как значение функции обработки ошибок.

Continue: продолжает выполнение с использованием возвращенного значения функции обработки ошибок.

Top-level: аварийно прекращает работу, возвращает управление верхнему уровню цикла read-eval-print, и предлагает пользователю произвести дальнейший ввод.

Важной функцией является вычисление факториала. Факториал неотрицательное целое число N, обозначается N ! и может быть определен рекурсивно следующим образом:

0! = 1,

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

Эквивалентное описание MuLISP FACTORIAL:

$ (DEFUN FACTORIAL (N) ((EQL N 0) 1) (* N (FACTORIAL (-N 1))))

Пример использования:

$ (FACTORIAL 3)

$ 6

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

Итерационное описание для FACTORIAL:

$ (DEFUN FACTORIAL (N % Local: % RSLT) (SETQRSLT 1) (LOOP

((ZEROP N) RSLT) (SETQ RSLT (* N RSLT)) (SETQN(-N 1))))MuLISP может обрабатывать очень большие числа. В описании показана примитивная программа - распознавателя ZEROP . (ZEROP N) эквивалентно (EQL N 0), но более эффективно.

32

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

F(0)=1 F(l)=l

F(N)=F(N-1) + F(N-2), если N>1.

Эквивалентное описание MuLISP FIBONACCI:

$ (DEFUN FIBONACCI (N) ((ZEROPN) 1) ((EQLNl)l) (+ (FIBONACCI (-N l))(FIBONACCI (-N 2))))

Пример использования:

$ (FIBONACCI 10)

Из примеров видно, что этот алгоритм неэффективен. Проблема состоит в том, что для вычисления N числа Фибоначчи, (N - 2)-ое число Фибоначчи необязательно вычислять дважды, (N-3)-ee - трижды, (N-4)-oe - пять раз, и дальше еще хуже.

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

По сравнению с вычислением N-ro числа Фибоначчи методом "назад к нулю", гораздо эффективнее способ вычисления от нулевого до N-ro числа Фибоначчи, использующий две переменные для сохранения двух последних вычислений числа Фибоначчи.

Пример рекурсивного описание для чисел Фибоначчи:

$ (DEFUNFIB(NF1 F2) ((ZEROPN) Fl) (FIB(-N 1)(+F1 F2)F1))

FIB - функция трех параметров. Первый параметр - N, второй должен быть 1 и третий - 0. Если вы хотите, чтобы у функции Фибоначчи был один параметр, то определите "интерфейсную" функцию, которая просто вызывает FIB с соответствующими вторым и третьим параметрами.

Возведение в целую степень является важной математической операцией. Чтобы возвести N в М-ую степень все, что вы должны сделать - умножить N на себя М раз.

Итерационное описание функции POWER:

$ (DEFUN POWER (N M % Local: % RSLT) (SETQ RSLT 1) (LOOP ((ZEROP M) RSLT)

33

^ (SETQ RSLT (* N RSLT)) (SETQM(SUB1 M))))

Пример:

$ (POWER 2 4) $ 16

Вызов примитивной функции SUB1 в вышеупомянутом описании эквивалентен, но более эффективен, чем был бы вызов (-N 1). ADD1 - также примитивно определенная функция MuLISP.

Рассмотрим следующие факты:

1). Если М - четное число, тогда N в степени М равняется N квадрат в степени

М/2.

2). Если М - нечетное число, тогда N в степени М - N*N в степени (М-1).

Для выполнения этого алгоритма нужна примитивная функция распознавания EVENP. Она возвращает Т тогда и только тогда, когда параметр -целое четное число; иначе она возвращает NIL.

Рекурсивное описание POWER:

$ (DEFUN POWER (N M) ((ZEROP M) 1) ((EVENP M) (POWER (*N N)(/M 2))) (+ N (POWER N (SUB1 M))))

Примитивная функция TRUNCATE полезна для преобразования дробей и частных в целые числа. Если <п> - число, (TRUNCATE n) округляет <п> до самого близкого целого числа в сторону нуля:

Пример:

$ (TRUNCATE 7/3)

$2

При вызове с двумя параметрами, TRUNCATE возвращает их частное до целого значения. Обратите внимание, что (TRUNCATE n m) эквивалентно (TRUNCATE (/n m)):

Пример:

$ (TRUNCATE 7 3)

$2

TRUNCATE возвращает округленное до целого числа частное двух параметров. Примитивная функция REM возвращает соответствующий остаток от деления двух целых чисел: N = Q * m + г

34

Часто нужно и частное, и остаток с помощью только одной операции. Примитивная функция DIVIDE возвращает последовательность частного и остатка от деления двух параметров.

Примеры:

$ (TRUNCATE 7 3)

$2

$ (REM 7 3) $ 0.3333

$ (DIVIDE 7 3) $ (2.3333 0.3333)

Наибольший общий делитель (НОД) двух чисел - самое большое неотрицательное целое число на которое делятся оба числа. Алгоритм Евклида для НОД целых чисел N и М может быть перефразирован так:

Если N=0, тогда НОД (N, М)=М;
Иначе, НОД (N, M)=(M mod N, N).

Используем функцию REM для получения М mod N.

Пример рекурсивного описание НОД с использованием определения Евклида:

$ (DEFUN GCD (N М) ((ZEROP N) М) (GCD (REM M N) N))

Пример: $(GCD2166)

$3

Фактически, функции НОД и НОМ (наименьший общий множитель) определяются в MuLISP примитивно. Конечно примитивные версии быстрее и могут работать с произвольным числом параметров.

В заключении мы должны упомянуть примитивные числовые функции сравнения: =, /=, <, >, <= и >=.

Примеры:

$ (=34 34.0); Равно $Т

$ (/=3/4 0.75) ; Неравно $NIL

$ (<67 45) ; Меньше $NIL

35

$ (>=10 17 17) ; Больше-равно $Т

Как показывает последний пример, числовые функции сравнения можно вызывать с несколькими параметрами. Если вызывать с нечисловыми параметрами, то произойдет прерывание и появится сообщение об ошибке -"Нечисловой параметр".

Чтобы определить, находится ли номер в пределах данного интервала, функцию < можно вызывать с тремя параметрами.

Пример:

определим является ли "g" символом нижнего регистра:

$ (<96 (ASCII 'g) 123) $Т

Функция ASCII возвращает код ASCII, если дано символьное имя. Оно возвращает эквивалентный символ ASCII, если дано число между 0 и 256.

Функция распознавания LOWERCASE, которая определяет является ли символ символом нижнего регистра:

$ (DEFUN LOWERCASE (CHAR) (<96 (ASCII CHAR) 123))

Пример:

$ (LOWERCASE 'g)

$T

Опишем функцию сортировки списка чисел в порядке увеличения. В данном случае нам не обязательно заботиться об эффективности, поэтому используем простую "сортировка-вставки", алгоритм которой подходит для коротких списков.

Сначала нам нужна функция, которая вставляет число в соответствующее место в сортируемом списке номеров. Требуется написать функцию INSERT-NUM, которая вставляет NUM в LST.

Пример рекурсивного определения функции 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)) $(1259 11 14 1921)

36

Используем функцию INSERT-NUM чтобы написать функцию NUMBER-SORT, которая сортирует список чисел.

Пример рекурсивного определения функции NUMBERT-SORT:

$ (DEFUN INSERT-NUM (NUM LST) ((NULL LST) (LIST NUM) ((< NUM (CAR LST)) (CONS NUM LST)) (CONS (CAR LST)(INSERT-NUM NUM (CDR LST))))

Встроенная функция SORT использует эффективную сортировку с объединением списка. Если - функция сравнения, (SORT list test) сортирует и возвращает основанный на .

Пример:

$ (СОРТИРОВКА "(34 23 -14 27 56 22 83) "<) $(-14 22 23 27 34 56 83)

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

Blog

Урок №1

Содержание