Знаходження найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі

Delphi-програма реалізує процес відшукання найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі, використовуючи для цього алгоритм Дейкстри.

Після запуску проекту на екран виводиться форма, в якій, на першому кроці, необхідно задати граф. Для цього достатньо, у компоненті типу TEdit, вказати кількість вершин графа, що розглядається, та скористатись кнопкою «Створити матрицю». В результаті, на головній формі появиться відповідна таблиця типу TStringGrid (матриця суміжності). Далі, необхідно заповнити її даними, які відповідатимуть за відстані між вершинами. Також відмітимо, що не існуючі ребра позначаються символом «-».

Після того, як матрицю заповнено, пошук найкоротших маршрутів здійснюється за допомогою кнопки «Знайти мінімальні маршрути». В результаті виконання даного кроку, в нижній частині форми, а саме в компоненті TMemo, здійснюється вивід списку вершин, через які проходять мінімальні маршрути, а також вивід їх довжин.

Читати повністю

Попадання точки в заштриховану область: Приклад 1

Нехай в декартові системі координат, міститься набір наступних геометричних фігур: коло радіус якого дорінює десять; пряма, яка паралельна осі ординат і проходить через точку ; пряма, проведена під кутом до осі абсцис.

Складемо delphi-програму, основним завданням якої буде визначення того, чи попадає задана користувачем точка з координатами в заштриховану область, включаючи її межі.

Ілюстрація графічної області

Для цього запустимо середовище програмування Delphi, створимо новий проект, та на головній формі розмістимо компоненти наступним чином:

Читати повністю

Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри

Delphi-проект розроблено за проханням користувача на ім'я andrey_khorolskiy («...Бажано передбачити можливість пошуку найкоротшого маршруту не тільки між початковою та кінцевою вершинами, але і між початковою і проміжною без пошуку маршруту до кінцевої...») і реалізує процес знаходження найкоротшого шляху між двома вершинами в орієнтованому графі, використовуючи для цього алгоритм Дейкстри.

Виходячи з того, що інтерфейс головної форми розглядуваного delphi-проекту аналогічний проектам, які реалізують інші алгоритми на графах, лише з однією відмінністю (панель інструментів міститься додаткове поле типу TEdit, в яке, способом введення з клавіатури, необхідно вказати номер вершини, для якої будується маршрут), то основні її елементи та процес побудови орієнтованого графа розглядати не будемо. Це все детально можна почитати перейшовши, наприклад, за посиланням Знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин в середовищі програмування delphi. А перейдемо до практики, тобто провіримо його роботу на конкретному прикладі.

Для цього, розглянемо деякий орієнтований граф, і припустимо, що для нього необхідно знайти мінімальний маршрут від вершини номер один, до вершини номер три.

Читати повністю

Рівняння кривої другого порядку що описує коло

Кривою другого порядку називається лінія, що визначається рівнянням другої степені щодо поточних декартових координат. У загальному випадку це рівняння записується в наступному вигляді:

де коефіцієнти  — дійсні числа і, крім того, принаймі одне із чисел або відмінне від нуля. В залежності від того, які значення приймають дані коефіцієнти, рівняння (1) визначає на площині коло, еліпс, гіперболу або параболу. Сьогодні покажемо, якими вони повинні бути для кола. Для цього, запишемо рівняння, яке описує коло радіуса  з центром в точці :

Розкривши дужки в рівнянні такого виду та виконавши деякі тотожні перетворення, перепишемо його в наступному вигляді:

Порівнюючи далі рівняння (3) із загальним рівнянням кривої другого порядку бачимо, що для того, щоб  рівняння (1) описувало коло необхідно, щоб для нього виконувались наступні дві умови: коефіцієнти при  та  повинні бути рівні між собою і член що містить добуток координат  повинен бути відсутнім.

Читати повністю

Відстань від точки до прямої на площині

Нехай на площині міститься пряма задана своїм рівнянням у загальному вигляді і деяка точка , що не лежить на даній прямій. Через точку  проведемо перпендикуляр до заданої прямої і позначимо точку їх перетину через . Тоді відстань від точки  до прямої буде дорівнювати відстані між точками  та .

Відстань від точки до прямої

Графічне представлення алгоритму знаходження відстані від точки до прямої

Виведемо формулу для обчислення відстані від точки до прямої. Для цього приведемо рівняння заданої прямої до виду рівняння прямої з кутовим коефіцієнтом:

Читати повністю

Точка перетину двох прямих на площині

Нехай дано дві прямі, задані своїми рівняннями в загальному вигляді і . Знайдемо точку перетину цих прямих.

Графічне представлення алгоритму знаходження точки перетину двох прямих

Так як ця точка належить кожній з двох даних прямих, то її координати повинні задовольняти як рівняння першої, так і рівняння другої прямої. Таким чином, для того щоб знайти координати точки перетину двох прямих, слід розв'язати систему рівнянь виду:

Читати повністю

Рівняння прямої яка проходить через дві задані точки

Нехай задані дві точки та через які проходить пряма і для якої, використовуючи їх координати, необхідно знайти її рівняння. Для цього припустимо, що . Відмітимо, що в такому випадку пряма не паралельна осі ординат. А, як нам уже відомо, рівняння будь-якої прямої яка проходить через точку і не паралельна осі  є рівняння виду:

Так як пряма проходить також і через точку , то координати даної точки повинні задовільняти цьому рівнянню. Підставляючи в рівняння (1), замість поточних координат, координати і , отримаємо . Звідси знаходимо:

Тобто кутовий коефіцієнт прямої дорівнює різниці ординат будь-яких двох її точок, розділеної на різницю абсцис цих точок. Підставивши знайдене значення в рівняння (1), отримаємо рівняння прямої, яка проходить через дві задані точки і :

Читати повністю

« Попередня сторінкаНаступна сторінка »