Common Lisp/Обробка масивів

Обробка масивів

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

Задача. В масивах 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) повертає список коефіцієнтів добутку вихідних многочленів. Наприклад, вихідні многочлени (x³+2x²+1) та (x²-4x-1) зададуться списками lst1 = (1 2 0 1), lst2 = (1 -4 -1). Результатом їх множення буде многочлен x⁵ - 2x⁴ - 9x³ - x² - 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))) )

Знаючи довжини списків lst1 та lst2 (k та l відповідно), ми знаємо довжину результуючого списку lst3 (m=k+l). Необхідно згенерувати список lst3, який складається з m елементів, кожний з яких дорівнює 0. Це зробить функція (GEN0 n).

Функція (mas lst n) повертає n-ий елемент списку lst. Функція (CHANGE lst n value) повертає список lst, в якому n-ий елемент набув значення value.

(DEFUN MAS (lst n)(DEFUN CHANGE (lst n value)

((ZEROP n) (CAR lst))((ZEROP n) (POP lst) (PUSH value lst))

(MAS (CDR lst) (- n 1)) )(CONS (CAR lst) (CHANGE (CDR lst) (- n 1) value))

Тоді функція MULTPOL, яка написана на Паскалі, на Ліспі набуває наступного вигляду:

(DEFUN MULTPOL (lst1 lst2)
(SETQ k (LENGTH lst1) l (LENGTH lst2) lst3 (GEN0 (+ k l)))
(SETQ i 0)
(POP lst3)
(LOOP
((= i k) lst3)
(SETQ j 0)
(LOOP
((= j l))
(SETQ lst3 (CHANGE lst3 (+ i j) (+ (MAS lst3 (+ i j)) (* (MAS lst1 i) (MAS lst2 j)))) )
(INCQ j) )
(INCQ i) ) )

Середовище muLisp має також вмонтовану функцію MAKE-LIST, яку можна використовувати для створення списків заданого розміру. Функція (MAKE-LIST n об’єкт список) утворює список з n елементів, кожний з яких приймає значення об’єкту, приєднані до списку. Якщо не задано перший аргумент, то по замовченню n = 0. Якщо другий аргумент не задано, то вважається об’єкт = NIL.

$ (MAKE-LIST 3 ‘(q w))$ (MAKE-LIST 4)$ (MAKE-LIST 3 5 ‘(2 3))

((q w)(q w)(q w))(NIL NIL NIL NIL)(5 5 5 2 3)

Наведену функцію можна визначити наступним чином (ім’я змінено на MAKE-LST):

(DEFUN MAKE-LST (N OBJ LST)

((AND (INTEGERP N) (PLUSP N))

(CONS OBJ (MAKE-LIST (SUB1 N) OBJ LST)) )

LST )

Функця (OBLIST) що не має аргументів, утворює та повертає список активних на поточний момент символів у системі. Символи розташовані в тому порядку, в якому вони прочитані або згенеровані строковими функціями: нові символі розташовані зліва від старих.

Завдання

1. Написати функцію:
   1. (GORNER n lst x) — обчислення значення многочлена степеня n в точці x, коефіцієнти якого задані в списку lst.
   2. (APPL lst1 lst2) — злиття двох відсортованих списків у відсортований список.
   3. (SCALAR lst1 lst2) — скалярний добуток двох векторів, координати яких задані списками.
2. Дано список з n чисел та натуральне число m<n. Для кожної групи з m елементів, що знаходяться поруч, обчислити її суму. Видати список з усіх можливих сум. Загальна кількість дій повинна бути O(n).

   Приклад: (7 1 4 2 3), m=3. S= (12 7 9).

3. Список LST зберігає перестановку чисел 1,2,..,n. Визначити кількість перестановок.
4. Список LST зберігає перестановку чисел 1,2,..,n. Визначити кількість циклів в перестановці. Наприклад, 152463 = (1)(5632)(4) — три цикла.
5. Надрукувати квадрати всіх натуральних чисел від 0 до n. Розв’язати також цю задачу використовуючи тільки додавання та віднімання, при цьому кількість дій повинна бути O(n).
6. Написатии функції:
   1. (MATR_GET m i j) – повернути значення m[i][j], де m – матриця n * n, i<=n, j<=n.
   2. (MATR_CHANGE m i j value) – повернути матрицю, у якій m[i][j]=value.
   3. (GENMATR0 i j) – згенерувати нульову матрицю i * j.
   4. (PMATR m i j) – надрукувати матрицю m як таблицю i * j (вивід форматувати).

Відповіді

1. a) $ (DEFUN GORNER (n lst x)Горнер рекурсивний

(SETQ k 0 y (POP lst))(DEFUN GORREC (lst x)

(LOOP((NULL (CDR lst)) (CAR lst))

((= k n) y) (GORREC (CONS (+ (* (CAR lst) x)

(SETQ y (+ (* y x) (POP lst))) (CADR lst)) (CDDR lst)) x)

) ))

б) $ (DEFUN APPL (lst1 lst2)

((NULL lst1) (APPEND lst3 lst2))

((NULL lst2) (APPEND lst3 lst1))

((< (CAR lst1) (CAR lst2))

(CONS (CAR lst1) (APPL (CDR lst1) lst2)))

(CONS (CAR lst2) (APPL lst1 (CDR lst2))) )

в) $ (DEFUN SCALAR (lst1 lst2)

((/= (LENGTH lst1) (LENGTH lst2)) NIL)

(SETQ s 0)

(LOOP

((NULL lst1) s)

(SETQ s (+ s (* (CAR lst1) (CAR lst2))))

(SETQ lst1 (CDR lst1) lst2 (CDR lst2))

) )

2. $ (DEFUN SMLIST (lst m)(LOOP

(SETQ n (LENGTH lst) res NIL)((= i n))

(SETQ i 0 s 0)(SETQ s (- s (MAS lst (- i m))))

(LOOP(SETQ s (+ s (mas lst i)))

((= i m))(PUSH s res)

(SETQ s (+ s (MAS lst i)))(INCQ i) )

(INCQ i) )(REVERSE res) )

(PUSH s res)

3. $ (DEFUN perestan (list)

(SETQ res 0)

(LOOP

(SETQ x 0)

((ATOM list) res)

(SETQ a (POP list))

(SETQ q (LENGTH list))

(LOOP

((= x q) res)

(IF (> a (mas list x)) (INCQ res))

(INCQ x)

)) )

4. $ (DEFUN CYCLES (lst)$ (DEFUN ISPLUS (lst t1)

(SETQ a 0) ((NULL lst) NIL)

(LOOP ((> (CAR lst) 0) t1)

(SETQ t1 (ISPLUS lst 1)) (ISPLUS (CDR lst) (+ t1 1)) )

((NOT t1))

(INCQ a)

(LOOP

((> 0 (MAS lst (- t1 1))))

(SETQ lst (change lst (- t1 1) (- (mas lst (- t1 1)))))

(SETQ t1 (- (mas lst (- t1 1)))) )

) a )

5. $ (DEFUN PRSQ (n)$ (DEFUN PRSQOPT (n)

(SETQ i 0) (SETQ k 0 ksq 0)

(LOOP (WRITE ksq) (SPACES 1)

((> i n)) (LOOP

(WRITE (* i i)) (SPACES 1) ((= k n ))

(INCQ i)(INCQ k) )

) )(INCQ ksq (SUB1 (+ k k)))

(WRITE ksq) (SPACES 1)

) )

6. a) $ (DEFUN MATR_GET (m i j) в) $ (DEFUN GENMATR0 (i j)

(LOOP (SETQ lst (gen0 j) res NIL)

((ZEROP i) (SETQ m (CAR m))) (LOOP

(POP m)((ZEROP i) res)

(DECQ i)(PUSH lst res)

)(DECQ i)

(LOOP )

((ZEROP j) (CAR m))

(POP m)

(DECQ j)

) )

б) $ (DEFUN MATR_CHANGE (m i j value) г) $ (DEFUN PMATR (m nx ny)

(SETQ head NIL) (SETQ i 0 j 0)

(LOOP (LOOP

((ZEROP i)(SETQ current (CAR m) t (CDR m))) ((= i nx))

(PUSH (POP m) head) (SETQ j 1)

(DECQ i) (LOOP

)((= j ny))

(SETQ current (CHANGE current j value)) (WRITE (matr_get m i j)) (SPACES 2)

(PUSH current t) (INCQ j)

(LOOP)

((NULL head) t) (TERPRI 1)

(PUSH (POP head) t) (INCQ i)

) ) ) )