Породження комбінаторних об’єктів

Розглянемо задачі, в яких необхідно отримати всі елементи деякої множини.

1. Надрукувати всі послідовності довжини n з цифр 0,1. (P11 n).

Функція P11 викликається з одним аргументом n, аргумент lst – допоміжний.

(DEFUN p11 (n lst) (DEFUN p13 (n lst)

((ZEROP n) (PRIN1 lst) (TERPRI)) ((ZEROP n) (PRN13 lst) (TERPRI))

(P11 (- n 1) (CONS 0 lst)) (P13 (- n 1) (CONS 0 lst))

(P11 (- n 1) (CONS 1 lst)) ) (P13 (- n 1) (CONS 1 lst)) )

2. Надрукувати всі послідовності довжини k з чисел 1..n. (P12 k n).

Друкуватимемо послідовності у лексикографічному порядку. За допомогою функції (GEN1 n) згенеруємо список з n елементів, кожен з яких дорівнює 1. Список lst зберігатиме поточну перестановку. Функція (NEXT lst n) знаходить перестановку, яка буде наступною після lst. Функція P12BEST є найкращим рекурсивним розв’язком цієї задачі.

(DEFUN GEN1 n) (DEFUN NEXT (lst n)

((ZEROP n) NIL) ((< (CAR lst) n) (CONS (+ (CAR lst) 1) (CDR lst)))

(CONS 1 (GEN1 (- n 1))) ) ((NULL (CDR lst)) NIL)

(CONS 1 (NEXT (CDR lst) n))

Шукана функція має вигляд: (DEFUN P12BEST (n k lst c)

(DEFUN P12 k n) ((ZEROP n) (PRIN1 lst) (TERPRI))

(SETQ lst (GEN1 k)) (PUSH 1 c)

(LOOP (LOOP

(( (CAR c) k))

(PRIN1 lst) (TERPRI) (P12BEST (- n 1) k (CONS (CAR c) lst) c)

(SETQ lst (NEXT lst n)) (SETQ c (CONS (+ 1 (CAR c)) (CDR c)))

) ) ) (POP c) )

3. Надрукувати всі підмножини множини {1..n}. (P13 n).

Оскільки всі підмножини будь-якої множини {1..n} перебувають у взаємно однозначній відповідності зі всіма послідовностями з 0 та 1 довжини n, то ця задача зводиться до задачі 1.1. Функція (P13 n) наведена в 1.1. Тільки замість виведення списку з 0 та 1 необхідно виводити номери всіх елементів списку, які дорівнюють 1. Функція (PRN13 lst) виводить необхідні номери елементів.

(DEFUN PRN13 (lst)

(SETQ i 0)

(LOOP

((NULL lst))

(INCQ i)

(IF (= 1 (POP lst)) (PROGN (PRIN1 i) (SPACES 1)))

) )

4. З перестановки (1 2 3 ... n ) необхідно отримати перестановку (n ... 2 1) за найменшу кількість кроків. Кроком будемо називати обмін місцями довільних двох сусідніх чисел. Наприклад, з перестановки (1 3 4 2) можна отримати одну з наступних: (3 1 4 2), (1 4 3 2), (1 3 2 4).

Нехай lst – поточна перестановка. Опишемо алгоритм, за яким будемо знаходити наступну перестановку. Для цього, переглядаючи список lst зліва направо, знайдемо такі два числа що знаходяться поруч, де перше менше за друге. Поміняємо їх місцями та викличемо рекурсивно функцію move_per над отриманим списком.

(defun move_per (lst)

(prin1 lst) (terpri 1)

(SETQ cur NIL)

(LOOP

((ATOM (CDR lst)))

(( 1 (CAR list)) (RETURN (POP list)))

(calc (- i 1))

(PUSH (- (POP list) 1) list)

) )

4. а) $ (DEFUN INTEGRATE (function a b n) (defun f (x)

(SETQ step (/ (- b a) n) intsumma 0) (* x x)

(LOOP )

((= a b) (* intsumma step))

(INCQ intsumma (FUNCALL function a)) Виклик: (INTEGRATE f 0 1 100)

(INCQ a step)

) )

б) (DEFUN HALFDIV (function a b eps)

(SETQ middle (/ (+ a b) 2) res (FUNCALL function middle))

((< (- b a) eps) middle)

(IF (MINUSP (* res (FUNCALL function a)))

(HALFDIV function a middle eps) (HALFDIV function middle b eps))

)

в) $ (DEFUN SQRT2 (n eps) г) $ (DEFUN DIFF (function x)

(SETQ s (/ n 2)) (SETQ delta 0.01)

(LOOP (/ (- (FUNCALL function (+ x delta))

(SETQ snew (/ (+ s (/ n s)) 2)) (FUNCALL function x)) delta)

((< (ABS(- s snew)) eps) snew) )

(SETQ s snew)

) )

Вказівка: x1 = n/2, xi = (xi-1 + n/xi-1) / 2. f’ (x) = (f(x + dx) - f(x)) / dx, де dx = 0.001.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать