Алгоритм Форда-Беллмана (реалізація в середовищі Delphi)
У математиці та інформатиці існує окремий розділ, який називається теорія графів. Основним предметом вивчення даного розділу є математичний об'єкт, який називається графом (об'єкт, який представляє собою множину вершин і набір ребер, які виступають в якості з'єднань між парами вершин). В рамках даного розділу ставляться і вирішуються різні задачі пов'язані з цим об'єктом. Найпоширенішшою серед них є задача про знаходження найкоротшого шляху між будь-якими двома вершинами графа. Зазначимо, що одним з найбільш використовуваних методів рішення задач такого типу являється метод Дейкстри.
Проте, виходячи з того, що delphi-проект який реалізує алгоритм методу Дейкстри нами вже неодноразово в розділі Програми на Delphi (Дослідження операцій) було розглянуто, сьогодні зосередимо свою увагу на delphi-проекті, що реалізує дещо інший алгоритм рішення задач такого типу, а саме алгоритм Беллмана-Форда.
Головне вікно проекту "Знаходження дерева мінімальної вартості за алгоритмом Беллмана-Форда"
Отже, головна форма розглядуваного проекту складається з панелі інструментів (містить кнопки «Додати вершину», «Видалити вершину», «Додати ребро», «Видалити ребро», «Видалити граф» і «Знайти дерево мінімальної вартості»), області графічного представлення, області представлення графа у вигляді матриці та області виводу результатів (компонент типу TStatusBar, призначений для виводу розв'язку у вигляді списку ребер).
Розв'язок задачі про найкоротший шлях використовуючи алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда — це алгоритм, який обчислює найкоротші шляхи від однієї вихідної вершини до всіх інших вершин в зваженому орієнтованому графі. Безумовно, він являється повільнішим, ніж алгоритм Дейкстри для тієї ж задачі, але більш універсальний, оскільки здатний обробляти графи, в яких вага деяких ребер приймає від'ємного значення. Алгоритм зазвичай називають на честь двох його розробників, Річарда Беллмана і Лестера Форда, які опублікували його у 1958 та 1956 роках відповідно. Тим не менш, Едвард Форест Мур також опублікував даний алгоритм у 1957 році, і з цієї причини його також іноді називають алгоритмом Беллмана-Форда-Мура.
Різниця в кінцеваому результаті між алгоритмом Беллмана Форда та алгоритмом Дейкстри
Як уже зазначалося вище, алгоритм Беллмана-Форда підходить для роботи з графами, що мають ребра з від'ємною вагою. Однак, якщо граф містить «від'ємний цикл», тобто цикл, сума ваги ребер якого дорівнює від'ємному значенню, тоді, для даного графа, не існує дерева найкоротших шляхів (будь-який шлях такого типу може бути покращений ще одним проходом через ребра, що утворюють від'ємний цикл). В такому випадку алгоритм Беллмана-Форда може виявити цикли від'ємної довжини і повідомити про їх існування, але він не може дати правильну відповідь, тобто знайти найкоротший шлях, якщо від'ємний цикл досяжний з вершини джерела.
Перетворення цілого десяткового числа в двійкове
Під системою числення розуміють спосіб представлення будь-якого числа за допомогою деякого алфавіту символів, які називаються цифрами. Існують різні системи числення, і від їх особливостей залежать наочність представлення числа за допомогою цифр і складність виконання арифметичних операцій.
В інформатиці, крім звичної нам десяткової системи числення, існують різні варіанти цілочисельних позиційних систем. Однією з основних серед них є двійкова система. Її простота дозволяє комп'ютеру здійснювати складні обчислення в кілька разів швидше, ніж в десятковій системі. Для запису чисел в двійковій системі числення використовуються лише дві цифри — 0 і 1. При цьому, в залежності від положення нуля або одиниці в числі, його значення буде змінюватися. Спочатку, саме за допомогою двійкового коду комп'ютери отримували всю необхідну інформацію. При цьому, одиниця означала наявність сигналу, що передається за допомогою напруги, а нуль — його відсутність.
Представлення десяткового числа в двійковій системі числення
Для перетворення цілого десяткового числа в двійкове необхідно розділити його на основу нової системи числення (в даному випадку основою являється число два). Отримана частка знову ділиться на основу нової системи числення, і робиться це до тих пір поки частка, отримана в результаті чергового поділу, не стане меншою за основу нової системи числення. Остання частка (що є старшим значущим розрядом) і всі отримані залишки від ділення складають число в новій системі числення.
Відшукання меж дійсних коренів алгебраїчного многочлена в середовищі програмування delphi
Основним призначенням розглядуваної в параграфі Delphi-програми є відшукання меж дійсних коренів алгебраїчного многочлена з дійсними коефіцієнтами.
Delphi-проект «Межі дійсних коренів многочлена з дійсними коефіцієнтами»
Як видно з рисунка вище, інтерфейс програми простий та зрозумілий у використанні. Ліва частина форми містить область вхідних даних, яка складається з таблиці TStringGrid, у комірки якої, способом введення з клавіатури, записуються значення коефіцієнтів при невідомих многочлена. Праву частину форми займає компонент типу TChart, який відображає графік многочлена що досліджується. І, нарешті, в нижній частині форми розташована панель інструментів (складається з одного поля вибору типу TSpinEdit та двох кнопок типу TButton), за якою слідує область виводу результатів (компонент типу TMemo). Розглянемо призначення кожного з елементів панелі задач більш детально:
Межі дійсних коренів многочлена з дійсними коефіцієнтами
Наближене обчислення кореня, будь-якого алгебраїчного рівняння, як правило, розпадається на дві задачі: відокремлення коренів, тобто визначення інтервалів, в кожному з яких міститься тільки один корінь рівняння; уточнення коренів, тобто обчислення його з заданим степенем точності. Прте, перш ніж відокремлювати корені, природно визначити межі області, в якій розташовані всі корені рівняння.
Межі дійсних коренів многочлена
В даному параграфі розглянемо один із способів відшукання цих меж, для випадку, коли алгебраїчне рівняння являється многочленом 
-ї степені:
Покажемо, спочатку, що для рівняння такого виду, достатньо вміти знаходити лише верхню межу його додатних коренів. Отже, нехай 
— верхня межа додатних коренів рівняння (1). Тоді, якщо числа 
будуть верхіми межами додатних коренів многочленів 
відповідно, то 
буде нижньою межею додатних коренів многочлена (1), а числа 
і 
служать нижньою і верхньою межами від'ємних коренів многочлена 
відповідно. Таким чином, всі додатні корені задовольняють нерівність 
, а від'ємні — нерівність 
.
Правильне розфарбування вершин графа в середовищі програмування delphi
Під розфарбуванням графа розуміють окремий випадком розмітки його елементів. При цьому, елементам графа ставляться у відповідність мітки з урахуванням певних обмежень, де в якості міток, найчастіше, використовуються натуральні числа або кольори. В даному параграфі зосередимо увагу на delphi-програмні, що реалізує процесу розмальовки вершин графа, а якщо бути більш точним, то процесу розмальовки вершин, при якому будь-яким двом суміжним вершинам відповідають різні кольори. Відмітимо, що в теорії графів, саме таку операцію над вершинами графа і називають правильною розмальовкою вершин.
Отже, головна форма розробленого delphi-проекту складається з панелі інструментів, графічного редактора та області виводу резільтатів.
Головне вікно проекту "Розфарбування вершин графа"
- Панель інструментів (компонент типу TPanel): містить чотири кнопки: «Додати вершину» (типу TSpeedButton), «Додати ребро» (типу TSpeedButton), «Видалити граф» (типу TButton) та «Знайти правильне розфарбування графа» (типу TButton). Відмітимо, що серед зазначених кнопок, три відповідають за процес побудови та видалення графа і четверта — реалізує процес розфарбування його вершин (відмітимо, що для реалізації задуманого використовується переборний алгоритм).
- Графічний редактор (компонент типу TImage): призначений для побудови та візуалізації неорієнтованого графа, а також візуалізації правильного розфарбування його вершин.
- Область виводу результатів (компонент типу TMemo): призначена для виводу мінімального числа кольорів, необхідних для правильного розфарбування графа.
Периметр і площа трикутника
Трикутник — це одна з базових фігур, утворена трьома відрізками прямих, що перетинаються. Точки перетину називаються вершинами, а самі відрізки сторонами трикутника. У найпростішому випадку, для того щоб знайти периметр трикутника, необхідно знати довжини всіх його стороін. В такому випадку, периметр трикутника обчислюється як сума довжин його сторін: 
.
В окремому випадку, для рівностороннього трикутника, дана формула прийме наступного вигляду: 
. Тобто, довжина сторони, помножена на три. Якщо трикутник буде рівнобедренним, то формула може бути записана у вигляді: 
, де 
— бічні сторони трикутника і 
— основа.
Зауваження: якщо скористатись позначеннями 
, то формули для обчислення периметра різносторонноього, рівнобедренного та рівностороннього трикутників перепишуться як 
відповідно.
Площа трикутника дорівнює половині добутку його сторони та проведеної до неї висоти. Для доведення даного твердження, розглянемо трикутник 
і його висоту 
. Покажемо, що 
.
Площа трикутника дорівнює половині добутку його сторони та проведеної до неї висоти
Для цього, через вершини 
і 
трикутника проведемо прямі, паралельні сторонам і 
відповідно. Нехай ці прямі перетинаються в точці 
. Чотирикутник 
— паралелограм за означенням. Трикутники і 
рівні (
та 
, як протилежні сторони паралелограма і 
— спільна). Отже, їх площі також рівні. Тоді, площа трикутника дорівнює половині площі паралелограма . Висота трикутника є також висотою паралелограма . Звідси, .
Загрузка ...