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

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))) )

Визначена таким чином функцiя не є ефективною, оскiльки для обчислення N-ого числа Фiбоначчi необхiдно обчислити (N-2) число Фiбоначчi двiчi, (N-3) - тричi i так далi. Визначимо функцiю FIB з трьома аргументами, останнi два з яких при виклику функцiї повиннi дорiвнювати вiдповiдно F(0) та 0).

$ (DEFUN FIB (n f1 f2)$ (FIB 20 1 0)

((ZEROP n) f1)10946

(FIB (- n 1) (+ f1 f2) f1) )

Завдання

1. Визначити функцiї MIN, MAX, INCR, DECR для спискiв.

Функцiя INCR (DECR) повертає iстину, якщо значення аргументiв знаходяться у зростаючому (спадному) порядку.

2. Написати функцiю, яка за списком з пiдсписками знаходить:

a) суму елементiв в) кiлькiсть пiдспискiв

б) кiлькiсть елементiв г) лiнеризує список

3. Написати функцiї:

a) (DIVIS x y) - повертає частку та остачу вiд дiлення x на y. Повернути результат у виглядi конса. Не використовувати функцiй дiлення та остачi.

б) (POW x y) - x в степенi y. Запропонувати алгоритми з часовою оцiнкою O(y) та O(log y).

в) (SLIST n) - розклад числа n на простi множники. Як результат виконання функцiї повернути список простих чисел, добуток яких дорiвнює n.

г) (PERLEN n) - за натуральним числом n повернути довжину перiоду дробу 1/n.

д) (SUMFACT n) - сума 1/0! + 1/1! + ... + 1/n!.

4. (UNITE lst1 lst2). Злити два неспаднi списки lst1 та lst2 в один неспадний список.

5. Написати функцiю:

а) (BINARY n) - кiлькiсть знакiв у двiйковому представленнi числа n.

б) НСД та НСК двох чисел за алгоритмом Евклiда.

НСД(a, b) = НСД(a - b, b), якщо a > b,