Lisp LabWork
Содержание
отсчета
- Постановка задачи
- Описание алгоритма
- Описание тестирования
- Оценка сложности алгоритмов
- Текст программы
- Результаты
.
1. Постановка задачи
Числа от 1 до N выписаны подряд в
строку. Разрешается менять местами любые
два числа, между которыми в строке стоят ровно
P1, P2, ... , Pm чисел(числа P1,
P2, ... ,Pm заданы).
Например, пусть N=5, M=2, P1=3, P2=2. Тогда после
перестановки чисел в позициях
1 и 4 (между ними стоят два числа) и числа в позициях
1 и 5 (между ними стоят
три числа), получается последовательность 5, 2,
3, 1, 4. Написать программу на
языке функционального программирования isp. Программа
должна вычислять
количество расположений чисел в строке, которые
можно получить из начальной
строки какой-либо последовательностью перестановок.
Ограничения:
2<=N<=3000
1<=M&t;=500
Для всех i(1<=i<=M) выполняется 0<=Pi<=N-2.
2. Описание алгоритма
Рассматривая исходные данные получаем графическую
интерпритацию перестановок:
Составляем списки, где элементами списка будут вершины
соответствующих графов:
1-й список : (1 2 4 5) 2-й список (3) .
Количество перестановок будет равно :
где
a1 - количество элементов
первого списка,
a2 - количество элементов
второго списка,
! - операция взятия факториала
от указанного аргумента.
Эта формула справедлива для данного частного случая.
Для общего случая будет
n -списков и следовательно применяется формула:
где
a1 - количество элементов
первого списка,
a2 - количество элементов
второго списка,
an - количество элементов
n-ого списка,
n - количество списков,
! - операция взятия факториала
от указанного аргумента.
3. Описание тестирования
При N=5, P1=2 получаем
четыре графа со следующими вершинами:
(1 5) (2) (3) (4).
Исполбзуя формулу получаем, что число перестановок
равно:
2! * 1! * 1! * 1! = 2
При N=5, P1=2, P2=3 получаем
два графа со следующими вершинами:
(1 4 5 2) (3) .
Исполбзуя формулу получаем, что число перестановок
равно:
4! * 1! = 24
При N=7, P1=1
получаем два графа со следующими вершинами:
(1 3 5 7) (2 4 6) .
Используя формулу, получаем, что число перестановок
равно:
4! * 3! = 144
При N=5, P1=2 получаем
три графа со следующими вершинами:
(1 4) (2 5) (3).
Используя формулу, получаем, что число перестановок
равно:
2! * 2! * 1! = 4
При N=6, P1=3 получаем
четыре графа со следующими вершинами:
(1 5) (2 6) (3) (4).
Используя формулу, получаем, что число перестановок
равно:
2! * 2! * 1! * 1! = 4
4. Оценка сложности
алгоритмов
памяти для реализации. Поэтому,
для выполнении программы уменьшена длина входного
массива, иначе происходит
переполнение стека, вызванное вычислением больших
факториалов и неверная работа
программы.
5. Текст программы
Программа "Числообменник" Выполнили
ст. гр. 6-19-2 Штоколов Антон и Зимин Петр
;Функция fact производит вычисления факториала
(defun fact (N)
- (cond
- ((= N 0) 1)
- (t (* N (fact (1- N))))
- )
)
(defun qqq (N L)
- (umnozh_fact (getist (reverse (buildlist N)) N L nil))
)
; функция производит умножение факториалов длин списков, представляющих
вершины полученных
графов
(defun umnozh_fact (L)
)
; функция umnozh_fact_ вспомогательная функция для функции umnozh_fact
(defun umnozh_fact_ (L P)
- (cond
- ((null L) P)
- (t (umnozh_fact_ (cdr L) (* P (fact (length (car L))))))
- )
)
(defun buildlist (N)
- (cond
- (t (cons N (buildlist (1- N))))
- )
)
(defun getlist (V N L Q)
- (cond
- ((null V) Q)
- (t (getlist (except V (visible (car V) N L (list (car V)))) N L (cons
(visible (car V) N L (list (car V))) Q)))
- )
)
(defun except (V E)
)
; функция except_ вспомогательная функция для функции except
(defun except_ (V E L)
- (cond
- ((null V) (reverse L)) ((member (car V) E) (except_ (cdr V) E L))
- (t (except_ (cdr V) E (cons (car V) L)))
- )
)
(defun visible (V N L W)
- (append (qqql V N L (qqqr V N L W L) L) )
)
; функция qqqr просматривает для элемента наличие связей с последующими
элементами
(defun qqqr (V N L W LS)
- ((null L) W) ((member (+ V (car L) 1) W) (qqqr V N (cdr L) W LS))
- ((<= (+ V (car L) 1) N) (qqqr V N (cdr L) (visible (+ V (car L)
1) N LS (cons (+ V (car L) 1) W)) L))
- (t (qqqr V N (cdr L) W L))
- )
)
; функция qqql просматривает для элемента наличие связей с предыдущими
элементами
(defun qqql (V N L W LS)
- (cond
- ((null L) W) ((member (- V (+ (car L) 1)) W) (qqql V N (cdr L) W LS))
- ((>= (- V (+ (car L) 1)) 1) (qqql V N (cdr L)
- (visible (- V (+ (car L) 1)) N LS (cons (- V (+ (car )1))W)) L))
- (t (qqql V N (cdr L) W L) )
- )
)
6. Результаты
C:\LANG\LISP\LABA2>c:\lang\lisp\xlisp\xlisp antlab2.lsp
XLISP version 2.0, Copyright (c) 1988, by David
Betz ;
loading "antlab2.lsp"
> (qqq 5 '(3)) 2
> (qqq 5 '(2 3)) 24
> (qqq 7 '(1)) 144
> (qqq 5 '(2)) 4
> (qqq 6 '(3)) 4
-