Отчет по лабораторной работе

"Задача "Подсветка фонтана""

по курсу "Функциональное программирование"


Выполнил: ст-т группы 6-19-2 Колотвинов С.В.






Содержание:



  1. ПОСТАНОВКА ЗАДАЧИ
  2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ЗАДАЧИ
  3. АЛГОРИТМЫ РЕШЕНИЙ
  4. ТЕКСТ ПРОГРАММЫ
  5. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ






1.ПОСТАНОВКА ЗАДАЧИ


Плоское дно фонтана описывается замкнутой ломаной линией без самопересечений, причем никакие три вершины ломаной не лежат на одной прямой. Для организации подсветки фонтана между двумя заданными углами (вершинами) по дну проложен гибкий натянутый кабель (см. рис.1). Требуется написать программу, вычисляющую длину этого кабеля.

Входные данные:
    - число вершин N (N&t;=100);
    - список координат, состоящий из подсписков с координатами
      X и Y для каждой вершины в порядке обхода ломаной против
      часовой стрелки, в формате :
            '((x1 y1) (x2 y2) ... (xn yn));
    - номера соединяемых вершин K и L (1<=K<L<=N).

Координаты вершин являются вещественными числами. Все входные данные корректны.

Выходные данные:
 - длина минимального пути от вершины K до вершины L.






2.МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ЗАДАЧИ


Для того, чтобы найти минимальный путь от начальной вершины до конечной надо проверить все возможные комбинации путей. Для этой цели из начачальной точки проводится (если возможно) прямая во все вершины, начиная с первой в порядке ввода координат вершин. Далее проверяется, можно ли провести прямую из текущей вершины в конечную. Если провести можно, то поиск текущего пути закончен и проверяется следующий путь из вершины, отстоящей на одну от текущей. Так находят все возможные пути, а потом среди них выбирают самый короткий
При разработке алгоритма задачи встретилась трудность в выборе условия, по которому можно было бы провести прямую от некоторой точки A1 до точки A2. Для правильного выбора этого условия, рассмотрим конкретный пример.
Пусть мы имеем 7 вершин с координатами:

(2 0) (5 0) (6 3.5) (5 6) (4 2) (3 7) (0 5)

и нам надо провести кабель от вершины A3 до вершины A7.

ПЕРИМЕТР ФОНТАНА


Рис.1.

Например, для проверки условия проведения прямой из вершины A3 в A1 вершину, составим уравнение прямых, проходящих через вершины A3, A1 и A4, A5 :

         A1*x + B1*y + C1 = 0        (1)

         A2*x + B2*y + C2 = 0        (2)

Сделав ряд математических преобразований, из уравнений (1) и (2) получим координаты X и Y точки пересечения этих двух прямых:

             C1*A1 - C2*A1
         y=-----------------         (3)
             B2*A1 - B1*A2

             -B2*y - C2
         x=--------------            (4)
                 A2
где коэффициенты A, B, C находятся следующим образом:

         A = 2*(x2-x1)               (5)

         B = 2*(y2-y1)               (6)

                2  2  2  2
         C = (x1+y1-x2-y2)           (7)

Таким образом, прямую между вершинами провести можно, если выполняется следующее условие:


  (y1<=y<=y2) and (x1<=x<=x2)  (8)

где x, y - координаты точки пересечения двух прямых;

x1, y1, x2, y2 - координаты точек, через которые проводится вспомогательная прямая (для полной уверенности, что прямую провести можно, в качестве вспомогательных прямых проверяют все грани "фонтана").






3.АЛГОРИТМЫ РЕШЕНИЙ


Словесно алгоритм решения задачи можно описать следующим образом.

Если из начальной вершины проверены все варианты проложения кабеля ко всем другим вершинам (исключая начальную вершину), то поиск закончен и требуется найти минимальное значение пути из списка путей.

Если из начальной вершины можно провести прямую в конечную вершину (условие, по которому проверяется возможность проведения прямой между двумя точками, описано в п.2, то поиск минимального пути закончен и в качестве ответа получаем длину пути из начальной вершины в конечную.

Если из текущей вершины можно провести прямую конечную вершину, то при следующей итерации головную функцию (Font1) будем вызывать со следующими параметрами:
      - список координат (ls) и начальная (nv) с конечной (kv)
        вершины остаются без изменений;
      - в качестве текущей вершины (tv) берется вершина,
        отстоящая на две от конечной в списке номеров вершин
        текущего пути (vlist);
      - в качестве следующей вершины (sv) берется вершина,
        которая является следующей за вершиной, отстоящей на
        одну от конечной вершины и не находящейся в списке
        номеров вершин текущего пути (vlist);
      - если длина списка номеров вершин текущего пути
        (vlist) равна 1 (т.е. в списке находится только одна
        вершина), то количество вершин, проверенных из нача-
        льной вершины (kol_t), передаем, увеличив его на 1,
        в противном случае передаем то же (не измененное)
        значение kol_t;
      - в качестве списка номеров вершин текущего пути
        (vlist) передается список, полученный путем объеди-
        ненияи вершины, которая является следующей за верши-
        ной, отстоящей на одну от конечной вершины (kv) и не
        находящейся в списке номеров вершин текущего пути и
        предыдущего списка без первых двух элементов вершины
        списка;
      - в качестве текущей длины текущего пути (dl) задается 0;
      - в качестве списка длин путей (dllist) передается список,
        полученный путем объединения текущей длины текущего пу-
        ти (dl) и предыдущего списка длинн путей (dllist).

Если из текущей вершины можно провести прямую в следующую по порядку вершину (начиная с первой), через которую еще не проводился текущий путь, то при следующей итеращии головную функцию (Font1) будем вызывать со следующими параметрами:
      - список координат (ls) и начальная (nv) с конечной (kv)
        вершины остаются без изменений;
      - в качестве текущей вершины (tv) передается вершина,
        которая является на данный момент 'следующей' (sv);
      - в качестве следующей вершины (sv) берется вершина,
        которая является следующей за вершиной, являющейс
        'следующей' в данный момент и не находящейся в списке
        номеров вершин текущего пути (vlist);
      - количество вершин, проверенных из начальной вершины
        (kol_t) передается без изменений;
      - в качестве списка номеров вершин текущего пути (vlist)
        передается список, полученный путем объединения сле-
        дующей вершины за вершиной, которая является 'следую-
        щей' в данный момент и предыдущего списка vlist;
      - в качестве текущей длины текущего пути (dl) передаетс
        длина, полученная путем сложения текущего значения dl
        с длиной пути от текущей вершины (tv) до следующей
        (sv);
      - список длин путей (dllist) передается без изменений.

Если из текущей вершины нельзя провести прямую в следующую по порядку ыершину (начиная с первой), через которою еще не проводился текущий путь, то при следующей итерации головную функцию (Font1) будем вызывать со следующими параметрами:
      - список координат (ls) и начальная (nv) с конечной
        (kv) вершины остаются без изменений;
      - текущая вершина (tv) остается без изменений;
      - в качестве следующей (sv) вершины берется вершина,
        которая является 'следующей' в данный момент и не
        находится в списке номеров вершин текущего пути
        (vlist);
      - количество вершин, проверенных из начальной вершины
        (kol_t) передается без изменений;
      - в качестве списка номеров вершин текущего пути
        (vlist) передается список, полученный путем объеди-
        нения следующей вершины за вершиной, которая являетс
        'следующей' в данный момент и предыдущего списка без
        первого элемента;
      - текущая длина текущего пути (dl) передается без изме-
        нений;
      - список длинн путей (dllist) передается без изменений.

Процесс повторяется.






4.ТЕКСТ ПРОГРАММЫ


;; ;; Стартовая функция. ;; Параметры : ko_v - количество вершин ;; list_ - список координат вершин в ;; формате: ;; '((x1 y1) (x2 y2) ... (xn yn)) ;; nv - начальная вершина ;; kv - конечная вершина ;; (defun fontan (kol_v list_ nv kv) (font1 list_ nv kv nv (sled (list nv) 0) 1 (list nv) 0 ()) ) ;; ;; Основная функция производящая перебор вершин и ;; и вычисляющая длины возможных путей. ;; Параметры : ls - список координат ;; nv - начальная вершина ;; kv - конечная вершина. ;; tv - текущая вершина ;; sv - следующая вершина ;; kol_t - количество вершин, проверенных ;; из начальной вершины ;; vlist - список-путь ;; dl - длина текущего пути ;; dllist - список длин путей ;; (defun font1 (ls nv kv tv sv kol_t vlist dl dllist) (cond ((= kol_t (- (length ls) 1)) (res_font1 dllist 0)) ((prov_yes ls nv kv 1 T) (long ls nv kv)) ((cond ((prov_yes ls tv kv 1 T) (font1 ls nv kv (nth 2 vlist) (sled vlist (nth 1 vlist)) (cond ((= (length (cdr (cdr (cdr vlist)))) 1) (+ kol_t 1)) ((kol_t)) ) (cons (sled vlist (nth 1 vlist)) (cdr (cdr vlist))) 0 (cons (+ dl (long ls tv kv)) dllist) ) ) ((prov_yes ls tv sv 1 T) (font1 ls nv kv sv (sled vlist sv) kol_t (cons (sled vlist sv) vlist) (+ dl (long ls tv sv)) dllist ) ) ((font1 ls nv kv tv (sled vlist sv) kol_t (cons (sled vlist sv) (cdr vlist)) dl dllist )) )) ) ) ;; ;; Функция, находящая минимальную длину пути из списка ;; длин путей. ;; Параметры : lis - список длин путей ;; min_ - минимальная длина пути ;; (defun res_font1 (is min_) (cond ((null lis) min_) ((&dt; min_ (car lis)) (res_font1 (cdr lis) (car lis))) ((res_font1 (cdr lis) min_)) ) ) ;; ;; Функция возвращает номер следующей за TV вершины, не ;; находящейся в списке LS. ;; Параметры : tv - номер текущей вершины ;; ls - список формата : '(a1 a2 ... an) ;; (defun sled (ls tv) (cond ((not (poisk ls (+ tv 1))) (+ tv 1)) ((sled ls (+ tv 1))) ) ) ;; ;; Функция производит поиск элемента V в списке LS. ;; Параметры : v - искомый элемент ;; ls - список формата : '(a1 a2 ... an) ;; (defun poisk (ls v) (cond ((null ls) nil) ((equal v (car ls)) T) ((poisk (list (car ls)) v)) ) ) ;; ;; Функция, проверяющая условие проведения прямой между ;; двумя точками. ;; Параметры : ls_ - список координат ;; nv_ - точка, из которой надо провести ;; kv_ - точка, в которую надо провести ;; n - количество проверенных ребер ;; bool - логическая переменная ;; (defun prov_yes (ls_ nv_ kv_ n bool) (cond ((and (= n (+ (length ls_) 1)) bool) T) ((not bool) nil) ((cond ((and (or (>= (koord_y (nth 0 (nth (- nv_ 1) ls_)) (nth 1 (nth (- nv_ 1) ls_)) (nth 0 (nth (- kv_ 1) ls_)) (nth 1 (nth (- kv_ 1) ls_)) (nth 0 (nth (- n 1) ls_)) (nth 1 (nth (- n 1) ls_)) (nth 0 (nth n ls_)) (nth 1 (nth n ls_)) ) (nth 1 (nth (- n 1) ls_) ) ) (<= (koord_y (nth 0 (nth (- nv_ 1) ls_)) (nth 1 (nth (- nv_ 1) ls_)) (nth 0 (nth (- kv_ 1) ls_)) (nth 1 (nth (- kv_ 1) ls_)) (nth 0 (nth (- n 1) ls_)) (nth 1 (nth (- n 1) ls_)) (nth 0 (nth n ls_)) (nth 1 (nth n ls_)) ) (nth 1 (nth n ls_) ) ) ) (or (&dt;= (koord_x (nth 0 (nth (- nv_ 1) ls_)) (nth 1 (nth (- nv_ 1) ls_)) (nth 0 (nth (- kv_ 1) ls_)) (nth 1 (nth (- kv_ 1) ls_)) (nth 0 (nth (- n 1) ls_)) (nth 1 (nth (- n 1) ls_)) (nth 0 (nth n ls_)) (nth 1 (nth n ls_)) ) (nth 0 (nth (- n 1) ls_) ) ) (<= (koord_x (nth 0 (nth (- nv_ 1) ls_)) (nth 1 (nth (- nv_ 1) ls_)) (nth 0 (nth (- kv_ 1) ls_)) (nth 1 (nth (- kv_ 1) ls_)) (nth 0 (nth (- n 1) ls_)) (nth 1 (nth (- n 1) ls_)) (nth 0 (nth n ls_)) (nth 1 (nth n ls_)) ) (nth 0 (nth n ls_) ) ) ) ) (prov_yes ls_ nv_ kv_ (+ n 1) T) ) ((prov_yes ls_ nv_ kv_ (+ n 1) nil) ) )) ) ) ;; ;; Функция, вычисляющая координату X точки пересечения ;; двух прямых. ;; (defun koord_x (xn yn xk yk x1 y1 x2 y2) (/ (- (* (- 0 (a_b y1 y2)) (koord_y xn yn xk yk x1 y1 x2 y2)) (c x1 y1 x2 y2) ) (a_b x1 x2) ) ) ;; ;; Функция, вычисляющая координату Y точки пересечения ;; двух прямых. ;; (defun koord_y (xn yn xk yk x1 y1 x2 y2) (/ (- (* (a_b x1 x2) (c xn yn xk yk)) (* (a_b xn xk) (c x1 y1 x2 y2)) ) (- (* (a_b xn xk) (a_b y1 y2)) (* (a_b x1 x2) (a_b yn yk)) ) ) ) ;; ;; Функция, вычисляющая коэффициенты A и B. ;; (defun a_b (kn kk) (* 2 (- kk kn)) ) ;; ;; Функция, вычисляющая коэффициент C. ;; (defun c (xn yn xk yk) (- (+ (* xn xn) (* yn yn)) (+ (* xk xk) (* yk yk))) ) ;; ;; Функция вычисления длины отрезка от т. A(x1,y1) ;; до т. B(x2, y2). ;; Параметры : nw - номер начальной точки A ;; kw - номер конечной точки B ;; l - список координат в формате : ;; '((x1 y1) (x2 y2) ... (xn yn)) ;; (defun long (l nw kw) (sqrt (float (+ (* (- (car (nth kw l)) (car (nth nw l))) (- (car (nth kw l)) (car (nth nw l))) ) (* (- (nth 0 (cdr (nth kw l))) (nth 0 (cdr (nth nw l)))) (- (nth 0 (cdr (nth kw l))) (nth 0 (cdr (nth nw l)))) ) ) ) ) )







5.РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ


XISP version 2.0, Copyright (c) 1988, by David Betz ; loading "fontan.lsp" > (fontan 7 '((2 0) (5 0) (6 3.5) (5 6) (4 2) (3 7) (0 5)) 3 7) 7.5 > (fontan 7 '((2 0) (5 0) (6 3.5) (5 6) (4 2) (3 7) (0 5)) 4 7) 10.09902