Засоби та принципи програмування на Ліспі

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

3. Обробка масивівВ Ліспі є поняття списку, але немає поняття масиву. Масиви можна емулювати за допомогою списків. Для цього необхідно написати функції конструювання масивів, доступу до елемента масива, та зміни значення елемента масива. Розглянемо цю техніку на прикладі.

Задача. В масивах a:array [0..k] of integer та b:array [0..l] of integer зберігаються коефіцієнти двох многочленів степеней k та l. Заповнити масив c:array[0..m] of integer коефіцієнтами їх добутку. Числа k,l,m — натуральні, m=k+l. Елемент масива з індексом i містить коефіцієнт при x в степені i.

Розв’язок. Розв’язок цієї задачі на Паскалі має наступний вигляд:

for i := 0 to m do c[i] := 0;

for i := 0 to k do

for j := 0 to l do

c[i+j] := c[i+j] + a[i] * b[j];

Масиви коефіцієнтів многочлена представлятимемо списком відповідної довжини. Нехай lst1 та lst2 — списки коефіцієнтів заданих в умові многочленів. Нехай функція (MULTPOL lst1 lst2) повертає список коефіцієнтів добутку вихідних многочленів. Наприклад, вихідні многочлени (x3+2x2+1) та (x2-4x-1) зададуться списками lst1 = (1 2 0 1), lst2 = (1 -4 -1). Результатом їх множення буде многочлен x5 - 2x4 - 9x3 - x2 - 4x -1, який представиться списком lst3 = (1 -2 -9 -1 -4 -1). Спочатку нам необхідно знайти значення k та l (якщо ми не передаємо їх як аргументи). Для цього необхідно просто знайти довжину списків lst1 та lst2. Це зробить функція (LENGTH lst):

(DEFUN LENGTH (lst)(DEFUN GEN0 (n)

((NULL lst) 0)((ZEROP n) NIL)

(+ 1 (LENGTH (CDR lst))) )(CONS 0 (GEN0 (- n 1))) )