Реферат на тему:

Числові функції

Числові функції виконують основні математичні операції над цілими та
дробовими числами. Користувач може обрати для роботи точну або наближену
раціональну арифметику. Для точної раціональної арифметики розмір цілих
чисел, чисельників та знаменників обмежений приблизно до 25000
десяткових знаків.

Примітивними числовими функціями є додавання, віднімання, множення та
ділення. В мові програмування Лісп вони є n-арними, тобто кількість
їхніх аргументів необмежена. Синтаксис числових функцій наступний:

1. (+ ). 3. (* )

2. ( — ) 4. (/ )

Функція додавання повертає суму своїх аргументів. Функція віднімання
повертає різницю першого аргумента та суми всіх інших аргументів.
Функція множення повертає добуток своїх аргументів. Функція ділення
повертає частку від ділення першого аргумента та добутку інших
аргументів.

$ (+ 2 4 6 7) $ (- 20 3 5 6) $ (* 2 4 6) $ (/ 24 2 2 3)

19 6 48 2

Функції збільшення та зменшення мають наступний синтаксичний вигляд:

1. (ADD1 ). Повертає значення, яке на одиницю більше за аргумент.

2. (SUB1 ). Повертає значення, яке на одиницю менше за аргумент.

3. (INCQ ) Збільшує значення символа на число .

4. (DECQ ) Зменшує значення символа на число .

Якщо функцію додавання (віднімання) одиниці запустити без аргументів, то
виникне переривання по помилці: недостатня кількість аргументів. Якщо у
функцію INCQ або DECQ передати один аргумент — символ, то збільшення
(зменшення) значення символа відбудеться на одиницю. Окрім того, що
функції INCQ та DECQ повертають результат арифметичної дії, значення
символів, які передаються до них як аргументи, змінюється.

$ (ADD1 6) $ (SUB1 10)

7 9

$ (SETQ S 10) $ (INCQ S 14) $ (DECQ S 4)

10 24 30

Функції MIN та MAX повертають символ з відповідно мінімальним
(максимальним) значенням.

1. (MIN ). $ (MIN 12 3 45 67) $ (MAX 1 2 5 3)

2. (MAX ). 3 5

Числові вирази в Ліспі записуються в префіксній формі. Вираз 3*5+5*7 для
обчислення треба подати у вигляді (+ (* 3 5) (* 5 7)), вираз (3+6)*7 — у
вигляді (* (+ 3 6) 7).

Функції порівняння менше та більше мають n аргументів.

1. ( < ) Повертає істину, якщо < < ... < .

2. < > ) Повертає істину, якщо > > … >
.

3. ( /= ) Повертає істину, якщо існують хоча б два
числа, які не

дорівнюють одне одному.

До функцій порівняння також відносяться <= , = та >=.

$ (< 2 4 6) $ (>= 5 3 3 2) $ ( /= 4 4 5)

T T T

$ (< 6 6 8 15) $ (<= 6 6 8 15) $ ( /= 4 4 4) NIL T NIL 1. Функції округлення (TRUNCATE m n), (ROUND m n), (CEILING m n) (FLOOR m n) Ці функції використовуються для округлення дробових чисел до цілих. TRUNCATE виконує округлення до ближчого цілого у напрямку нуля. ROUND виконує округлення до ближчого цілого по значенню до m/n. CEILING виконує округлення до ближнього цілого по верхній межі, FLOOR — по нижній межі. Виклик будь-якої функції з двома аргументами ( m n)
еквівалентний виклику функції з одним аргументом: ( (/ n m)), де f —
будь-яка з наведених чотирьох функцій.

$ (TRUNCATE 6/4) $ (TRUNCATE -6/4) $ (CEILING 9 4) $ (CEILING -9 4)

1 -1 3 -2

$ (FLOOR 6 4) $ (FLOOR -6 4) $ (FLOOR 6/4) $ (FLOOR -6/4)

1 -2 1 -2

2. Функції остачі

(REM m n), (MOD m n), (DIVIDE m n)

Примітивна функція REM повертає остачу від ділення числа m на n. Функція
MOD працює як REM, але повертає модуль остачі. Якщо (TRUNCATE m n)
повертає q, а (REM m n) повертає r, то m=q*n+r. Функція (DIVIDE m n)
повертає конс, CAR якого дорівнює частці, а CDR — остачі від ділення m
на n.

$ (REM 6 4) $ (DIVIDE 7 2) $ (REM -6 4) $ (MOD 6 4)

2 (3 . 1) -2 2

3. Знак числа

(SIGNUM n)

Повертає значення -1, 0 або 1 якщо n відповідно від’ємне, 0, або
додатнє.

4. Модуль числа

(ABS n) – Модуль числа n.

5. Чисельник та знаменник

(NUMERATOR n), (DENOMINATOR n) – чисельник та знаменник числа n.

$ (signum -5/3) $ (abs -5/3) $ (numerator 10/8) $ (denominator 10/8 )

-1 5/3 5 4

6. Побітові логічні функції

(LOGAND ), (LOGIOR ), (LOGXOR
), (LOGNOT n).

$ (LOGAND 5 7 3) $ (LOGIOR 4 2 1) $ (LOGXOR 5 2 3) $ (LOGNOT 6)

1 7 4 -7

7. Булеві функції

(NOT <об’єкт>), (AND <форма1> <форма2> … <формаN>), (OR <форма1>
<форма2> … <формаN). $ (AND (EQL ‘as ‘as) (< 2 4)) $ (OR NIL (< 4 56)) $ (NOT (EQL ‘d ‘g)) T T T 8. Зсув (SHIFT m n) — зсув числа m на n бітів. $ (SHIFT 3 1) $ (SHIFT 3 -1) $ (GCD 24 66 600) $ (LCM 24 66 600) 6 1 6 6600 9. НСД, НСК (GCD n1 n2 ... nM), (LCM n1 n2 ... nM). Ці функції знаходять відповідно найбільший спільний дільник M чисел та найменше спільне кратне. В файлі irratnal.lsp міститься великий набір ірраціональних та трансцендентних функцій. Аргументи тригонометричних функцій задаються в радіанах. (EXP x) експонента ex (EXPT x y) степінь xy (LOG x y) логарифм logyx. Якщо y не задано, основа вважається рівною e. (LN x) натуральний логарифм (SQRT x) квадратний корінь (ISQRT x) ціла частина з квадратного кореня (SIN x) та (ASIN x) сінус та арксінус (COS x) та (ACOS x) косинус та арккосинус (TAN x) та (ATAN x) тангенс та арктангенс (RANDOM n) генерується натуральне число, менше за n. Задача 1. Список lst має 100 елементів, які дорівнюють 0 або 1. Написати функцію (CHANGE01 lst), яка повертає список, у якому всі елементи 0 замінені на 1, а 1 – на 0. Необхідно замість використання умовного оператора застосувати дію X := 1 - X. (DEFUN CHANGE01 (lst) ((NULL lst) NIL) (CONS (- 1 (CAR lst)) (CHANGE01 (CDR lst))) ) Задача 2. Змінним a та b присвоєні числа. Записати функцію в одному рядку (не визначати цю функцію), в результаті якої змінні обмінюються своїми значеннями. Використовувати допоміжні змінні забороняється. $ (SETQ a 2 b 3) // a = 2, b = 3 $ (SETQ a (+ a b) b (- a b) a (- a b)) // a = 3, b = 2 Задача 3. Відомо, що lst – список, який містить неспадну послідовність чисел. Функція (NUM lst) повинна обчислювати кількість різних чисел у ньому. (DEFUN NUM (lst) ((NULL (CDR lst)) 1) ((/= (CAR lst) (CADR lst)) (+ 1 (NUM (CDR lst)))) (NUM (CDR lst)) ) Задача 4. Списки lst1 та lst2 містять строго зростаючі послідовності чисел. Знайти кількість спільних елементів у цих масивах. Часова оцінка алгоритму повинна дорівнювати O(K+L), де K та L – довжини списків lst1 та lst2 відповідно. (DEFUN COMELEMENT (lst1 lst2) ((OR (NULL lst1) (NULL lst2)) 0) ((< (CAR lst1) (CAR lst2)) (COMELEMENT (CDR lst1) lst2)) ((> (CAR lst1) (CAR lst2)) (COMELEMENT lst1 (CDR lst2)))

(+ 1 (COMELEMENT (CDR lst1) (CDR lst2))) )

Контрольні конструкції

MuLisp використовує неявну форму PROGN для обчислення форм, які
складають тіло функції. Окрім того, інтерпретатор muLіsp розпізнає в
тілі функції неявні COND конструкції. Неявні COND-и роблять визначення
функцій читабельними, короткими та ефективними. Спеціальні форми
забезпечують контроль за обчисленням форм в процесі виконання програм.
Розглянемо деякі контрольні інструкції.

1. QUOTE <об’єкт> повертає об’єкт без його обчислення. QUOTE може
використовуватися для запобігання обчислення значень констант, які
передаються як аргумент функції, що обчислюється.

$ (SETQ a 125)

$ a $ (QUOTE a) $ (CAR (CONS 4 7)) $ (CAR ‘(CONS 4 7))

125 a 4 CONS

2. LOOP <форма1> <форма2> … <формаN> Повторно обчислює форми у
послідовному порядку доти, поки не зустрінеться неявний COND з
предикатом, не рівним NIL. Розглянемо функцію LENGTH обчислення довжини
списку. В першому стовпчику запропоновано рекурсивний, в лівому —
нерекурсивний варіант програми.

(DEFUN LENGTHr (lst) (DEFUN LENGTH (lst)

((NULL lst) 0) (SETQ ct 0)

(+ 1 (LENGTHr (CDR lst))) ) (LOOP

((NULL lst) ct)

(SETQ lst (CDR lst) ct (+ 1 ct)) ) )

3. IF <предикат> [THEN] <форма1> [ELSE] <форма2> Якщо значення предиката
не дорівнює NIL, то видається [THEN] форма, інакше видається [ELSE]
форма.

$ (IF (EQL ‘r ‘r) (CAR ‘(q w e r t y)) (CDR ‘(q w e r t y))) — q

$ (IF (EQL ‘r ‘w) (CAR ‘(q w e r t y)) (CDR ‘(q w e r t y))) — (w e r
t y)

4. IDENTITY <об’єкт> Повертає об’єкт без жодних змін. Ця функція
застосовується для використання змінних як предикатів в умовних виразах.

5. PROGN <форма1> <форма2> … <формаN> Послідовно обчислює форми та
повертає результат обчислення формиN.

6. PROG1 <форма1> <форма2> … <формаN> Послідовно обчислює форми та
повертає результат обчислення форми1. Функцію використовують для того,
щоб вводити допоміжні змінні для збереження результатів в процесі
обчислення інших виразів.

$ (SETQ a ‘(q w e r t y)) $ a

$ (PROG1 (CAR a) (SETQ a (CDR a))) (w e r t y)

q

7. COND Обчислює CAR кожної COND форми доти,
доки не зустрінеться деяке значення, відмінне від NIL, або доки всі
предикати не будуть обчислені. В першому випадку COND обчислює CDR
елемент cons — форми з предикатом, який не дорівнює NIL, як тіло
функції, використовуючи неявну функцію PROGN. Якщо CDR — елемент COND
форми, яка не дорівнює NIL, є порожнім, то повертається значення
предиката. Якщо обчислені всі предикати та всі вони повернули NIL, то
COND повертає NIL.

8. COMMENT <коментар> Ігнорує свої аргументи та повертає NIL. Визначає
засіб включення коментарів безпосередньо у визначені функції.

9. RETURN <об’єкт> Зупиняє виконання функції, яка містить RETURN,
звільняє стек та повертає об’єкт в ролі свого значення.

10. RESTART Закриває всі відкриті файли, відмовляється від поточного
середовища та ініціює нову систему muLisp. Всі зв’язки між змінними,
функції користувача та значення властивостей поточного середовища
знищуються.

11. SYSTEM Закриває всі відкриті файли, завершує виконання muLisp та
повертає керування операційній системі.

12. EXECUTE <програма> <командний рядок> Зупиняється робота системи
muLisp, передається керування програмі з командним рядком. EXECUTE
повертає код виходу з програми або NIL, якщо <програма> не знайдена.

$ (EXECUTE “command.com” “/c dir c:”)

Обчислення рекурсивних функцій

1. Факторіалом числа n називається число (позначається n!), яке
рекурсивно визначається наступним чином:

0! = 1 $ (DEFUN FACTORIAL (n) $ (FACTORIAL 10)

N! = N*(N-1)! якщо N>0. ((ZEROP n) 1) 3628800

(* n (FACTORIAL (- n 1))) )

Якщо в рекурсивній програмі аргументом буде велике число, то може
виникнути переповнення стеку. Використовуючи команду циклу LOOP можна
уникнути рекурсивного виклику. Наступна функція буде більш ефективною:

$ (DEFUN FACTORIAL1 (n rslt) $ (FACTORIAL1 10)

(SETQ rslt 1) 3628800

(LOOP

((ZEROP n) rslt ) $ (FACTORIAL 0 a)

(SETQ rslt (* n rslt)) 1

(SETQ n (- n 1)) ) )

2. Послідовність чисел, кожен елемент якої дорівнює сумі двох
попередніх, а перші два елементи дорівнюють 1, називається послідовністю
Фібоначчі. N-те число послідовності Фібоначчі F(N) може бути знайдене за
рекурсивною формулою:

F(0)=1, F(1)=1, F(N) = F(N-1) + F(N-2).

$ (DEFUN FIBON (n) $ (FIBON 20)

((<= n 1) 1) 10946 (+ (FIBON (- n 1)) (FIBON (- n 2))) ) Визначена таким чином функція не є ефективною, оскільки для обчислення N-ого числа Фібоначчі необхідно обчислити (N-2) число Фібоначчі двічі, (N-3) — тричі і так далі. Визначимо функцію FIB з трьома аргументами, останні два з яких при виклику функції повинні дорівнювати відповідно F(0) та 0). $ (DEFUN FIB (n f1 f2) $ (FIB 20 1 0) ((ZEROP n) f1) 10946 (FIB (- n 1) (+ f1 f2) f1) ) Завдання 1. Визначити функції MIN, MAX, INCR, DECR для списків. Функція INCR (DECR) повертає істину, якщо значення аргументів знаходяться в зростаючому (спадному) порядку. 2. Написати функцію, яка за списком з підсписками знаходить: a) суму елементів в) кількість підсписків б) кількість елементів г) лінеризує список 3. Написати функцію: a) (DIVIS x y) — повертає частку та остачу від ділення x на y. Повернути результат у вигляді конса. Не використовувати функцій ділення та остачі. б) (POW x y) — x в степені y. Запропонувати алгоритми з часовою оцінкою O(y) та O(log y). в) (SLIST n) — розклад числа n на прості множники. Як результат виконання функції повернути список простих чисел, добуток яких дорівнює n. г) (PERLEN n) — за натуральним числом n повернути довжину періоду дробу 1/n. д) (SUMFACT n) – сума 1/0! + 1/1! + ... + 1/n!. 4. (UNITE lst1 lst2). Злити два неспадні списки lst1 та lst2 в один неспадний список. 5. Написати функцію: а) (BINARY n) – кількість знаків у двійковому представленні числа n. б) НСД та НСК двох чисел за алгоритмом Евкліда. НСД(a, b) = НСД(a - b, b), якщо a>b,

НСД(a, b — a), якщо ab,

НСД(a, b mod a), якщо a (CAR lst) (CADR lst)) (LMAX (CONS (CAR lst) (CDDR lst))))

(LMAX (CDR lst)) )

$ (DEFUN INCR (lst)

((ATOM (CDR lst)) T)

((< (CAR lst) (CADR lst)) (INCR (CDR lst))) ) $ (D????????†???????????†??????????????????????†???????????????†††???????? †††?????????????????????????†††????????????????????? б) $ (DEFUN FLEN (lst) ((NULL lst) 0) ((ATOM (CAR lst)) (+ 1 (FLEN (CDR lst)))) ( + (FLEN (CAR lst)) (FLEN (CDR lst))) ) в) $ (DEFUN FLIST (lst) ((NULL lst) 0) ((ATOM (CAR lst)) (FLIST (CDR lst))) (+ 1 (FLIST (CAR lst)) (FLIST (CDR lst))) ) г) $ (DEFUN LINER (lst) ((NULL lst) NIL) ((ATOM (CAR lst)) (CONS (CAR lst) (LINER (CDR lst)))) (APPEND (LINER (CAR lst)) (LINER (CDR lst))) ) 3. a) $ (DEFUN DIVIS (x y) б1) $ (DEFUN POW (x y) ((ZEROP y) NIL) ((ZEROP y) 1) (SETQ ch 0) (* (POW x (- y 1)) x) ) (LOOP ((< x y) (CONS ch x)) (SETQ x (- x y) ch (+ 1 ch))) ) б2) $(DEFUN POWLOGY (x y) (SETQ k y b 1 c x) (LOOP ((= k 0) b) (if (= 0 (mod k 2)) (SETQ k (/ k 2) c (* c c)) (SETQ k (SUB1 k) b (* b c)) ) ) ) в) $ (DEFUN SLIST (n) г) $ (DEFUN PERLEN (n) (SETQ k n lst NIL) (SETQ r 0 l 1) (LOOP (LOOP ((= k 1) lst) ((= l (+ n 1))) (SETQ l 2) (SETQ r (CDR (divis (* 10 r) n))) (LOOP (INCQ l) ((ZEROP (CDR (DIVIS k l)))) ) (INCQ l) (SETQ c r r (CDR (divis (* 10 r) n)) k 0) (LOOP (PUSH l lst) ((= r c)) (SETQ k (/ ?????????????????‰?????†?†?????????????? д) (DEFUN SUMFACT (n) (SETQ k 1 fct 1 s 1) (LOOP ((= k n) s) (SETQ k (INCQ k) fct (* fct k) s (+ s (/ 1 fct))) ) ) Пояснення. г) період дробу дорівнює періодові в послідовності остач (доведіть це; зокрема, необхідно довести, що він не може бути меншим). Окрім цього, в цій послідовності всі члени, що періодично повторюються, різні, а передперіод має довжину не більшу за n. Тому достатньо знайти (n+1)-й член послідовності остач і потім мінімальне k, за якого (n+1+k)-й член співпадає з (n+1)-м. 4. (DEFUN UNITE (lst1 lst2) ((NULL lst1) lst2) ((NULL lst2) lst1) ((<= (CAR lst1) (CAR lst2)) (CONS (CAR lst1) (UNITE (CDR lst1) lst2))) ((> (CAR lst1) (CAR lst2)) (CONS (CAR lst2) (UNITE lst1 (CDR
lst2)))) )

5. a) $ (DEFUN BINARY (n) б) (DEFUN NOD (a b)

((= n 0 ) 1) ((= a b) a)

(SETQ c 0) (IF (> a b) (NOD (- a b) b)

(LOOP (NOD (- b a) a)

((= n 0) c) ) )

(SETQ n (SHIFT n -1)) (INCQ c) (DEFUN NOK (a b)

) ) (/ (* a b) (NOD a b)) )

в) $ (DEFUN NODM (a b) г) $ (DEFUN INVERTBIT (a n)

((ZEROP a) b) (SETQ s (SHIFT 1 (SUB1 n)))

((ZEROP b) a) (LOGXOR a s)

(IF (> a b) (NODM (MOD a b) b) )

(NODM (MOD b a) a)

) )

д) $ (LOAD ‘irratnal) е) $ (DEFUN sqtr (a b c)

$ (DEFUN eq2 (a b c) (SETQ p (/ (+ a b c) 2))

(SETQ d (- (* b b) (* 4 a c))) (SQRT (* p (- p a) (- p
b) (- p c))) )

((MINUSP d) NIL)

((ZEROP d) (/ (- b) (* 2 a)))

(LIST (/ (+ (- b) (SQRT d)) (* 2 a)) (/ (- (- b) (SQRT d)) (* 2
a))) )

II Варіант завдань

1. $ (DEFUN FIND3 (lst1 lst2 lst3)

((OR (NULL lst1) (NULL lst2) (NULL lst3)) NIL)

((= (CAR lst1) (CAR lst2) (CAR lst3)) (CAR lst1))

((< (CAR lst1) (CAR lst2)) (FIND3 (CDR lst1) lst2 lst3)) ((< (CAR lst2) (CAR lst3)) (FIND3 lst1 (CDR lst2) lst3)) ((< (CAR lst3) (CAR lst1)) (FIND3 lst1 lst2 (CDR lst3))) )

Похожие записи