Програмна реалізація першої інтерполяційної формули Ньютона

Програму було розроблено з метою надання можливості за допомогою ЕОМ обчислслювати наближені значення функції у випадку, коли вона задана таблично і використовуючи для цього інтерполяційну формулу Ньютона першого порядку для рівновіддалених вузлів.

Після запуску програми на екраны з'явиться форма виду:

Перша інтерполяційна формула Ньютона на Delphi

Головне вікно програми "Перша інтерполяційна формула Ньютона"

Далі, використовуючи поле «Розміри таблиці», вибираємо необхідну кількість рядків для таблиці яку будемо заповнювати  даними фіксованих значень функції. Після того, як таблиця заповнена, натискаємо кнопку «Інтерполювати». В результаті програма виконає необхідні обчислення і видасть результат у вигляді графіка.

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

Перша інтерполяційна формула Ньютона для рівновіддалених вузлів інтерполяції

Нехай для функції Перша інтерполяційна формула Нютона задані значення i_interpolacijna_formyla_nytona2 для рівновіддалених вузлів, тобто i_interpolacijna_formyla_nytona31, де h крок інтерполяції. Потрібно знайти поліном i_interpolacijna_formyla_nytona4, степінь якого не перевищує n, і який в точках i_interpolacijna_formyla_nytona5 набуває значень i_interpolacijna_formyla_nytona61.

Даний поліном будемо шукати у наступному вигляді:

i_interpolacijna_formyla_nytona71

Використовуючи узагальнену степінь числа, вираз (2) запишемо у наступному вигляді:

i_interpolacijna_formyla_nytona8

Задача полягає у знаходженні коефіцієнтів i_interpolacijna_formyla_nytona91. У виразі (2') покладемо i_interpolacijna_formyla_nytona10. В результаті отримаємо i_interpolacijna_formyla_nytona11.

Для того, щоб знайти коефіцієнт i_interpolacijna_formyla_nytona12 запишемо скінченну різницю першого порядку (скінченною різницею першого порядку називають різницю між значеннями функції у сусідніх вузлах інтерполяції, тобто, i_interpolacijna_formyla_nytona26):

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

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Дейкстри

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

Алгоритм Дейкстри

Слідуючи алгоритму, початковій вершині (вершина під номером 1) присвоюємо постійну мітку Алгоритм Дейкстри після чого переходимо до першого етапу.

Етап 1: з вершини 1 існує орієнтоване ребро до вершин 2, 4 і 5. Обчислимо для даних вершин відповідні мітки. В результаті отримаємо наступну таблицю.

Алгоритм Дейкстри

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

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

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

Позначемо через Алгоритм Дейкстри найкоротша відстань від початкової вершини 1 до вершини i, через Алгоритм Дейкстри — довжину ребра (i, j). Тоді для вершини j мітка Алгоритм Дейкстри визначається наступним чином:

Алгоритм Дейкстри

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

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

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Флойда

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

Алгоритм Флойда

Для рішення даної проблеми використаємо алгоритм Флойда, з допомогою якого, за n етапів (n — кількість вершин графа),  можна відшукати найкоротший маршрут між будь-якими двома вершинами графа.

Перш ніж приступити до розв'язку, запишемо початкову матрицю відстаней Алгоритм Флойда та початкову матрицю вершин Алгоритм Флойда.

Алгоритм Флойда

Переходимо до 1-го  етапу: в матриці Алгоритм Флойда виділимо синім кольором ведучий рядок і колонку під номеромАлгоритм Флойда. Також, червоним кольором виділимо ті елементи матриці Алгоритм Флойда, значення яких можна покращити з допомогою трикутного оператора.

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

Визначення найкоротшого шляху за алгоритмом Флойда

Основна ідея алгоритму Флойда полягає в наступному: нехай є три вершини графа i, j і k, які поєднані між собою ребрами заданої довжини.

Алгоритм Флойда

Трикутний оператор Флойда

Якщо виконується нерівність Алгоритм Флойда, то доцільно замінити маршрут від вершини i до  вершини k (Алгоритм Флойда) маршрутом Алгоритм Флойда. Така заміна (іншими словами трикутний оператор) виконується в процесі виконання алгоритму Флойда.

Алгоритм Флойда складається з n етапів (де n кількість вершин графа).

Етап 0: на даному етапі визначаємо початкову матрицю відстаней Алгоритм Флойда і матрицю послідовності вершин Алгоритм Флойда. Діагональні елементи обох матриць в обчисленні не беруть участь, тому позначаємо їх символом «-». Також на даному етапі покладають Алгоритм Флойда.

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

Метод осереднених коефіцієнтів на Delphi

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

Головне вікно програми містить одне поле вводу, чотири кнопки та статусний рядок, в який виводяться результати виконання програми, тобто оптимальний маршрут.

Головне вікно програми

Головне вікно програми методу осереднених коефіцієнтів

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

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

Наступна сторінка »