Алгоритм Шімбелла (реалізація в середовищі Delphi)

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

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

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

schimbels_method_delphi1

Створення вершин орієнтованого графа

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

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

Означення вектора. Напрям і модуль вектора

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

Кожну векторну величину геометрично можна зобразити напрямленим прямолінійним відрізком — вектором, довжина якого дорівнює числовому значенню векторної величини (у вибраному масштабі) і напрям співпадає з напрямом цієї величини.

Нульовий вектор, колінеарні вектори, рівні вектори

Ілюстрація до визначення вектора

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

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

Знаходження найкоротших шляхів в графі методом Шімбелла

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

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

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

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

Площа круга та кругового сектора

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

Знаходження площі круга з допомогою багатокутників

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

Будемо тепер необмежено збільшувати число сторін -кутника. Зазначимо, що в такому випадку збільшуватиметься і радіус  вписаного в багатокутник кола і при , величина буде як завгодно мало відрізнятися від , а отже, наближатиметься до одиниці, тому . Іншими словами, при необмеженому збільшенні числа сторін багатокутника, вписане в нього коло збігатиметься до описаного кола, тому при . Звідси і з нерівності (1) випливає, що при .

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

Довжина кола і дуги кола

У своєму повсякденному житті ми часто стикаємося з завданнями, які пов'язані з обчисленням периметра, тобто суми довжин сторін різних геометричних фігур. У разі, якщо геометрична фігура — багатокутник, знаходження його периметра не складає особливих труднощів: для цього достатньо визначити довжину кожної зі сторін і скласти отримані результати. Що ж робити, якщо необхідно знайти довжину кола? Відповіді на це питання і присвячений даний параграф.

Отже, як відомо, периметр будь-якого правильного вписаного в коло багатокутника є наближеним значенням довжини цього кола. Чим більше число сторін такого багатокутника, тим точніше це наближене значення, так як багатокутник при збільшенні числа сторін все ближче і ближче прилягає до кола. Точне значення довжини кола — це границя, до якої збігається периметр правильного вписаного в коло багатокутника при необмеженому збільшенні числа його сторін.

Довжина кола

Знаходження довжини кола з допомогою багатокутників

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

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

Ознаки подільності на 2, 3, 4, 5, 8, 9, 10 і 11

Правила подільності або тести подільності мають широкий спектр застосувань в математиці. До прикладу, скориставшись даними правилами при розкладанні чисел на прості множники чи визначенні, чи є число простим чи складеним, можна значно спростити обчислювальний процес задач такого типу. Зазначимо, що опанувавши матеріал цього параграфа, Ви дізнаєтесь, як, не виконуючи операцію ділення, визначити, чи ділиться дане натуральне число націло на 2, 3, 4, 5, 8910 і 11.

  1. ознака подільності на 2: число ділиться на 2 тоді і тільки тоді, коли воно закінчується парною цифрою, тобто однією з цифр 0, 2, 4, 6, 8.

    Доведення покажемо на прикладі чотиризначного числа. Отже, нехай  — десяткова запис деякого числа , тобто  — цифра тисяч,  — цифра сотень,  — цифра десятків і  — цифра одиниць даного числа. Значить, . Нехай  ділиться на 2. Так як 1000, 100 і 10 діляться на 2, то за властивістю 4 подільності (міститься нижче) числа , і  також діляться на 2. Тоді за властивістю 2 подільності сума ділиться на 2 і за тією ж властивістю, число теж ділиться на 2. І навпаки, якщо  ділиться на 2, то з огляду на подільність на 2 доданків  і  маємо:  ділиться на 2 (по властивості подільності). Наприклад, число 2300574 діляться на 2, а 100001 не діляться. Абсолютно аналогічно доводяться наступні дві ознаки подільності;

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

Наближене обчислення квадратних коренів

З уроків алгебри ми знаємо, що квадратним коренем із заданого числа називають таке число, квадрат якого дорівнює заданому числу. Наприклад, числа -5 і 5 є коренем з 25. Арифметичним квадратним коренем із заданого невід'ємного числа називають таке невід'ємне число, квадрат якого дорівнює заданому числу. Для нашого прикладу це буде число 5. Процес знаходження арифметичного квадратного кореня низивається визначенням або добуванням квадратного кореня.

Назва «корінь» і позначення кореня виникли ще в давнину. Так, в Індії його називали «мула» — корінь (дерева), початок, основа; араби — «джузр» — корінь, основа квадрата. В Європі використовували латинський аналог даного слова. Так з'явилася назва radix (по-латині «корінь»), звідси — радикал. Спочатку позначення кореня скоротили до , потім до букви . Вперше таке позначення використовував німецький математик Томас Рудольф. Далі буква  видозмінилася в знак . В подальшому, завдяки Рене Декарту, з'явився сучасний знак .

В математиці існує велика кількість методів для усного та письмового визначення квадратних коренів із чисела. Розглянемо декілька з них, і для початку зупинемося на способі що полягає у застосуванні таблиці квадратів двозначних чисел. Зазначимо, що з цим способом ми познайомилися ще на шкільних уроках математики. Спосіб дуже простий в застосуванні і дає миттєвий результат для квадратного кореня з будь-яких цілих чисел від 1 до 100 з точністю до десятих.

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

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