ю «Очистити» можна скористатися в будь-який момент процесу виконання алгоритму, що найбільш зручно для користувача в разі будь-якої помилки. Але очищається повністю все поле в будь-якому з режимів.
2.6 Математичне обгрунтування
Для математичного обгрунтування даного завдання мені потрібно вивчення теми «Вектора» і відповідно основні формули: «Довжина вектора» або «Відстань між 2 точками».
Завдання (умовно): Дано N точок синього кольору і N точок червоного кольору, координати їх відомі. Потрібно з'єднати їх так, щоб відстань від точки одного кольору до точки іншого кольору було мінімальним з можливих варіантів. Далі розрахувати суму їх довжин.
Примітка: Якщо ми з'єднаємо точки вищеописаним чином, то при додаванні довжин одержані відрізків у нас вже виходить мінімальна сума довжин цих відрізків.
Рішення :. Потрібно з'єднати точки різних кольорів так, щоб з усіх можливих варіантів вийшла довжина була мінімальною.
Для розрахунку довжини використовуємо формулу довжини вектора:
A? B =? (x2 - x1) 2 + (y2 - y1) 2 (1)
. Після того, як обрані потрібні (мінімальні) варіанти довжин відрізків, потрібно просто підсумовувати ці довжини, в результаті, задача вирішена, отриманий потрібну відповідь.
3. Практична частина
. 1 Структура програми
Аналізуючи завдання, ми розробляємо структурну схему програми, яка буде містити основні блоки, опис виконуваних ними функцій і їх місце розташування в програмі. Для програми вирішення задачі про червоних і синіх точках отримаємо таку структурну схему:
Розглянемо деякі блоки, що зустрічаються в програмі.
Інтерфейс - цей блок здійснює взаємодію користувача і програми. Взаємодія здійснюється за допомогою монітора, клавіатури і миші.
Введення синіх і червоних точок- в цьому блоці запам'ятовуються дані про синіх і червоних крапок і розміщуються на поле користувачем.
Побудова відрізків - блок, який виробляє побудова відрізків з червоних і синіх точок.
Відображення ходу роботи алгоритму - у таблиці відображаються відрізки і їх сумарна довжина.
Візуалізація результатів - відображення змін відбуваються в програмі.
Довідка - похідна інтерфейсу, служить для отримання відомостей з експлуатації програми.
. 2 Опис використовуваних типів даних
У ході реалізації програми використовувалися як стандартні структури даних, так і власні, створені безпосередньо при проектуванні алгоритму.
Для зберігання даних про червоних і синіх точках використовується спіcок pList типу TList. Кількість точок зберігається у змінній tCount, число червоних крапок - в redCount, число синіх точок - в blueCount.
Також був створений тип даних TPnt для зберігання структури даних про точку має наступний вигляд:
PPnt=^ TPnt;=record, Y: integer ;: byte ;: integer ;: boolean;
end;
Як видно він заснований на покажчиках (PPnt посилається на адресний простір типу TPnt), і використання цього типу має на увазі зберігання наступної інформації про точці:
· Координати X і Y
· Колір точки (1 - червоний, 2 - синій)
· Чи пов'язана точка (Linked=true/false)
· Номер точки, з якою пов'язана дана точка, якщо вона пов'язана (num)
. 3 Опис основних алгоритмів
У програмі реалізований автоматичний алгоритм пошуку відрізків, складових мінімальну сумарну довжину, і подальший розгляд роботи програми заснована на цьому основному алгоритмі. Решта алгоритми, у тому числі і ручний є допоміжними і необхідні лише для відображення результатів і реалізації інтерфейсу користувача.
Детальний опис автоматичного і ручного алгоритмів було приведено раніше, у пункті 2.4.
Пошук мінімальної суми довжин відрізків
Дане завдання є класичним прикладом динамічного програмування. Повний перебір, як легко довести, вимагає експоненціального часу, що для алгоритму не є добре, застосування ж динамічного програмування спрощує цю задачу і як далі буде видно складність цього алгоритму є O (x ^ 3).
Зобразимо роботу алгоритму графічно:
Рис. 1
Код процедури, реалізує даний алгоритм:
procedure FindLines;, j, start: integer;, P2, PMin, Pz: PPnt;, Sum: double; start:=0 to pList.Count - 1 do:=0; .Clear; i:=0 to pList.Count - 1 do:=pList.Items [i]; (P...
