WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Числові функції - Реферат

Числові функції - Реферат

довжини списку. В першому стовпчику запропоновано рекурсивний, в лівому - нерекурсивний варіант програми.
(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] [ELSE] Якщо значення предиката не дорівнює 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 ... Послідовно обчислює форми та повертає результат обчислення формиN.
6. PROG1 ... Послідовно обчислює форми та повертає результат обчислення форми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)
((b,
НСД(a, b - a), якщо ab,
НСД(a, b mod a), якщо aa, якщо b = 0.
b, якщо a = 0.
г) (INVERTBIT a n) - обернути n-ий біт числа a.
д) (EQ2 a b c) - розв'язати квадратне рівняння.
е) (SQTR a b c) - знайти площу трикутника за трьома сторонами (використати формулу Герона).
II Варіант завдань
1. Чи існує таке число, яке міститься у кожному з трьох неспадних послідовностей чисел lst1, lst2 та lst3. Функція (FIND3 lst1 lst2 lst3) повинна знайти це число (якщо воно існує) з часовою оцінкою O(K+L+M), де K, L, M - довжини відповідних послідовностей, інакше повернути NIL.
Відповіді
1. $ (DEFUN LMIN (lst)
((ATOM (CDR lst)) (CAR lst))
(( (CAR lst) (CADR lst)) (LMAX (CONS (CAR lst) (CDDR lst))))
(LMAX (CDR lst)) )
$ (DEFUN INCR (lst)
((ATOM (CDR lst)) T)
(( (CAR lst) (CADR lst)) (DECR (CDR lst))) )
2. a) $ (DEFUN FSUM (lst)
((NULL lst) 0)
((ATOM (CAR lst)) (+ (CAR lst) (FSUM (CDR lst))))
( + (FSUM (CAR lst)) (FSUM (CDR lst))) )
б) $ (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 (/ k l)) ((SETQ r (CDR (divis (* 10 r) n))))
) ) (INCQ k)
)
(+ k 1) )
д) (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 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))) )
Loading...

 
 

Цікаве