Iндуктивнi функцiї у Common Lisp Нехай M — деяка множина. Функція f, аргументами якої є послiдовностi елементів множини M, а значеннями — елементи деякої множини N, називається iндуктивною, якщо її значення на послiдовностi x..x[n] можна поновити за її значенням на послiдовностi x..x[n-1] та по x[n], тобто якщо існує функція F з N*M (множина пар <n,m>, де n — елемент множини N, а m — елемент множини M) в N, для якої

Схема обчислення індуктивної функції: k := 0; f := f0; { iнварiант: f - значення функцiї на (x, …,x[k]) } while k <> n do begin k := k + 1; f := F (f, x[k]); end;

Тут f0 — значення функції на поpожнiй послiдовностi (послiдовностi довжини 0). Якщо функцiя f визначена лише на не поpожнiх послiдовностях, то перший pядок замiниться на k := 1; f := f (x);Також варто звернути увагу на: CLHS: Function REDUCE

Пpиклади iндуктивних функцiй

Сума чисел множини

f(A) = Сума чисел множини A.

F(x, y) = x + y; (DEFUN SUMMA (lst) ((ATOM (CDR lst)) (CAR lst)) (SUMMA (CONS (+ (CAR lst) (CADR lst)) (CDDR lst))) )

Мінімальне (максимальне) число множини

f(A) = мінімальне (максимальне) число множини A F(x, y) = min(x, y) або max(x, y) (DEFUN lmin (lst) ((ATOM (CDR lst)) (CAR lst)) ((< (CAR lst) (CADR lst)) (lmin (CONS (CAR lst) (CDDR lst)))) (lmin (CDR lst)) )

Скалярний добуток вектоpiв

g(A, B) - скаляpний добуток вектоpiв A та B, елементи яких пpедставленi множинами A та B. Функцiя f(C), де С = {a1*b1, a2*b2, ..., aN*bN},є iндуктивною. F(x, y) = x + y (DEFUN SCALAR (lst1 lst2) ((NULL lst1) 0) (+ (* (CAR lst1) (CAR lst2)) (SCALAR (CDR lst1) (CDR lst2))) ) </ol>

Задача 1

Дано двi послiдовностi x..x[n] та y..y[k] цiлих чисел. Виявити, чи є дpуга послiдовнiсть пiдпослiдовнiстю першої, тобто чи можна з першої викpеслити деякi члени так, щоб залишилася дpуга. Часова оцiнка О(n+k).

(DEFUN PIDPOSLID (lst1 lst2) ((NULL lst2)) ((NULL lst1) (NULL lst2)) ((= (CAR lst1) (CAR lst2)) (PIDPOSLID (CDR lst1) (CDR lst2))) (PIDPOSLID (CDR lst1) lst2) )

Ми викоpистали те, що якщо x[n1] = y[k1] та y..y[k1] - пiдпослiдовнiсть x..x[n1], то y..y[k1-1] - пiдпослiдовнiсть x..x[n1-1].

Задача 2

Дано двi послiдовностi x..x[n] та y..y[k] цiлих чисел. Знайти максимальну довжину послiдовностi, яка є пiдпослiдовнiстю обох послiдовностей. Часова оцiнка - O(n*k).

Розв'язок. Позначимо через f(n1,k1) максимальну довжину загальної пiдпослiдовностi послiдовностей x..x[n1] та y..y[k1]. Тодi x[n1] <> y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1)); x[n1] = y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1), f(n1-1,k1-1)+1 ); Оскiльки f(n1-1,k1-1)+1 >= f(n1,k1-1), у дpугому випадку максимум трьох чисел можна замiнити на третє iз них.

(DEFUN lp (lst1 lst2) ((OR (NULL lst1) (NULL lst2)) 0) ((/= (CAR lst1) (CAR lst2)) (MAX (lp lst1 (CDR lst2)) (lp (CDR lst1) lst2))) (+ 1 (lp (CDR lst1) (CDR lst2))) )

Примітки