Аpифметичнi задачі

((NULL lst1) 0)

(+ (* (CAR lst1) (CAR lst2)) (SCALAR (CDR lst1) (CDR lst2))) )

Задача 1. Дано двi послiдовностi x[1]..x[n] та y[1]..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[1]..y[k1] - пiдпослiдовнiсть x[1]..x[n1], то y[1]..y[k1-1] - пiдпослiдовнiсть x[1]..x[n1-1].

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

Розв'язок. Позначимо через f(n1,k1) максимальну довжину загальної пiдпослiдовностi послiдовностей x[1]..x[n1] та y[1]..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))) )

Функцiї виводу

Функцiї виводу передають результат в поточний поток виводу (COS - Current Output Stream).

1. (PRIN1 obj). Передає символьне представлення об'єкту в COS i повертає об'єкт. Функцiя друкує символи використовуючи їх P-iмена. Друк вiдбувається згiдно з поточною системою числення. Змiнна *PRINT-POINT* контролює максимальну кiлькiсть десяткових цифр для зображення на екранi дисплею.

2. (PRINC obj). Працює як i PRIN1, але P-iмена виводяться з контрольними символами. Значення контрольної змiнної *PRINT-ESCAPE* при виклику PRINC стає рiвним T.

(DEFUN PRINC (obj *PRINT-ESCAPE*)