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

Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів в графі останнім часом інстенсівно розвивається і використовується в різних сферах діяльності, наприклад, для знаходження оптимального матршрута між двома об'єктами на місцевості (найкоротший шлях від будинку до університету), для знаходження оптимального матршрута при перевезеннях, в системах автопілота, в системах комутації інформаційних пакетів в мережі 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 з точністю до десятих.

Далее

Числа Фібоначчі: циклом і рекурсією

Числа Фібоначчі — лінійна послідовність натуральних чисел, де перше і друге дорівнюють нулю та одиниці, а кожне наступне — сумі двох попередніх: 0, 1, 1, 2, 3, 5, 8, 13, 21, 43, 55, ... Зазначимо, що ці числа були відомі в Індії ще у столітті. В Європі ж вони в такому вигляді вперше з'явилися в книзі Liber Abaci 1202 року (в перекладі з латинської — «Книга обчислень») за авторством Леонардо Пізанського, згодом прозваного Фібонначі. Значення цієї праці для європейської цивілізації переоцінити неможливо: він вперше знайомив західного читача з індо-арабськими цифрами і ставшими вже звичними для нас арифметичними методами. Одна з найвідоміших включених в неї задач — задача про розмноження кроликів.

Послідовність чисел Фібоначчі

Крім опису зростання приплоду тварин, числа Фібоначчі зустрічаються навіть в самій природі, і на подив доволі часто: це і пелюстки квітки, і спіралі соняшнику, ананаса або соснової шишки.

Далее

Обчислення факторіала великих чисел

В математиці факторіал числа — це добуток всіх натуральних чисел, менших або рівних даному числу. Іншими словами це результат множення всіх чисел від одного до заданого числа. Наприклад, факторіал числа 7 обчислюється як . Факторіал має багато застосувань, особливо в комбінаториці або в задачах підрахунку, тому для написання математичних програм може знадобитися спосіб його обчислення. Якщо Ви працюєте з мовою програмування Java, то матеріал даного параграфу може бути для Вас корисним. Адже сьогодні нами, використовуючи клас BigInteger, буде розроблена Java-програма для обчислення факторіала будь-якого розміру.

Далее

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