((ATOM (CDR lst)) (CAR lst))
(SUMMA (CONS (+ (CAR lst) (CADR lst)) (CDDR lst))) )
2. f(A) = мiнiмальне (максимальне) число множини 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)) )
3. 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))) )
Задача 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)))
|
Скачати "Реферат на тему Аpифметичнi задачi"
