Алгоритм Евкліда — знаходження найбільшого спільного дільника
Нагадаємо, що у параграфі найбільший спільний дільник (НСД), нами було сформульовано означення та розглянуто основні методи знаходження НСД. На продовження даної теми, сьогодні буде створена java-програма, яка допоможе швидко визначити найбільший спільний дільник двох додатних цілих чисел використовуючи алгоритм Евкліда. Зазначимо, що наша сьогоднішня програма не буде мати інтерфейсу. Всі дані передаватимуться через консоль.
Отже, для початку створимо «Java Project», потім в ньому створимо «Java Class» і назвемо його, наприклад, Greatest_common_divisor. На наступному кроці, виходячи з того, що для знаходження НCД , від користувача, нам знадобляться два числа number1 і number2, то для їх введення скористаємось класом Scanner з бібліотеки пакетів Java.
import java.util.Scanner;
class Greatest_common_divisor {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// Ввід вхідних даних
System.out.print("Enter number1:");
int number1 = scann.nextInt();
System.out.print("Enter number2:");
int number2 = scann.nextInt();
Зазначимо, що для того, щоб не обтяжувати користувача зайвими турботами, ми дозволимо йому вводити числа в довільному порядку, хоча для алгоритму важливо, щоб перше число було більше другого. Тобто, будемо виправляти цю ситуацію програмно, якщо в цьому винекне необхідність.
Найменше спільне кратне двох натуральних чисел
Кратним числа 
називається таке число, яке саме ділиться на без залишку. Спільне кратне чисел і 
— це число, що є кратним для кожного з них.
До прикладу, числа 10 і 15 мають спільне кратне 180. Числа 150, 120, 90 — також є спільними кратними цих чисел. Серед всіх спільних кратних завжди є найменше, в даному випадку таким являється число 30. Це число називають найменшим спільним кратним (НОК) і позначають 
.
Щоб знайти найменше спільне кратне двох чисел, потрібно розкласти їх на прості множники. Після цього, необхідно вибрати всі прості множник що входять в обидві множини та перемножити їх між собою. На наступному кроці, отриманий результат необхідно також помножити на прості множники, числа , які не являються множниками числа та прості множникик числа , що не являються простими множниками числа . До прикладу, для чисел 441 та 350 даний процес виглядатиме наступним чином:
Розкладання чисел на прості множники
Нагадаємо, що цілі додатні числа більші за одиницю діляться на прості та складені. Різниця між ними полягає в числі дільників. Просте число має два натуральних дільники — одиницю та самого себе. Наприклад, 2, 3, 5, 7, 11,... (одиниця не є простим числом). Число, яке має більше ніж два натуральних дільники, називається складеним. Зазначимо, що будь-яке складене число можливо представити як добуток простих чисел. Наприклад, число 20 можна представити як 
, де 2 та 5 — прості числа. Саме таке представлення і називається розкладанням чисел на прості множники.
Зазначимо, що складене число розкладається на прості множники єдиним чином. Це означає, що якщо, наприклад, число 20 розклалося на дві двійки і одну п'ятірку, то воно завжди буде так розкладатися незалежно від того, почнемо ми розкладання з малих множників чи з великих. Прийнято починати розкладання з малих множників, тобто з двійок, трійок і так далі. Це зручніше тому, що про подільність числа на 2, на 3, на 5 легше судити, ніж про його подільність, наприклад, на число 59 чи 67.
Два способи отримання одного розкладання
Знову-таки повертаючись до нашого прикладу, бачимо, що для невеликих чисел здогадатися яким буде їх розкладання доволі легко. Виникає питання, яким же чином виконується розкладання на множники великих чисел? Зазначимо, що тут нам допоможуть ознаки подільності та таблиця простих чисел. Покажемо, як за їх допомогою отримати розкладання деякого натурального складеного числа 
.
Знаходження простих чисел використовуючи решето Ератосфена
Просте число — натуральне ціле додатне число, що має рівно два різних натуральних дільники — одиницю і самого себе. Іншими словами, число 
є простим, якщо воно більше одиниці і при цьому ділиться без залишку тільки на 1 та на . Наприклад, 3 — просте число, а число 6 ні — крім 1 та 6, також ділиться на 2 і на 3.
Таблиця простих чисел до 1000
Натуральні числа, які являються більшими одиниці і не є простими, називаються складеними. Таким чином, всі натуральні числа розбиваються на три класи: одиницю (має один натуральний дільник), прості числа (мають два натуральних дільники) і складені числа (мають більше двох натуральних дільників).
Знаходження центру графа (реалізація в середовищі Delphi)
Програма створена в середовищі програмування Delphi і реалізує процес знаходження однієї з основних числових характеристик графа, а саме його центр. Зазначимо, що безсумнівною перевагою цієї програми перед іншими є те, що вона може застосовуватися не тільки в якості прикладного пакета, але і з великим успіхом використовуватися в якості навчальної програми. Також хочеться зауважити, що delphi-програмі притаманний досить зручний і інтуїтивно зрозумілий користувацький інтерфейс, який виявиться доступним навіть для користувачів, що не знайомі з основами програмування. Крім того є поетапна візуалізація, як самої побудови графа, так і процесу знаходження його центру.
Для того, щоб запустити програму необхідно перейти в каталог де він збережений, знайти файл Project.exe і запустити його. Після запуску програми на екрані буде відображено вікно наступного вигляду:
Головне вікно проекту "Знаходження центру графа"
У верхній частині форми розташовується панель інструментів. На панелі розташовується чотири кнопки (дві типу TSpeedButton та дві — TButton) зліва направо: «Додати вершину», «Додати ребро», «Видалити граф», «Знайти центр графа». Праворуч від кнопки «Додати ребро» міститься перемикач типу TCheckBox, який відповідає за тип створюваного ребра (якщо перемикач не включений, то програма пряцює в режимі «Розміщення орієнтованого ребра», і навпаки, якщо перемикач включений — в режмрі «Розміщення неорієнтованого ребра». Біла область (компонент типу TImage) називається робочою областю і використовується для візуалізації графа та відображення вершини, яка являється центральною. Нижня частина форми (компонент типу TMemo) призначена для виводу результатів роботи програми.
Знаходження найбільшого спільного дільника за алгоритмом Евкліда
Кожен дільник натурального числа 
не може бути більшим самого числа , тому число має скінченне число дільників, які не перевищують .
Серед дільників чисел і 
можуть бути однакові, тобто спільні дільники. Очевидно, їх кількість так само є скінченною. Наприклад, числа 30 і 70 мають чотири спільних дільники: 1, 2, 5 і 10. Серед цих дільників є найбільший (в даному випадку 10), його називають найбільшим спільним дільником (НСД) і позначають 
.
Отже, найбільшим спільним дільником двох натуральних чисел називається найбільше натуральне число, на яке ділиться кожне з цих чисел без залишку. З даного означення випливає, що для того, щоб знайти НСД двох чисел і , на першому кроці, необхідно знайти всі додатні дільники числа і всі додатні дільники числа . Далі, необхідно вибрати всі числа, що входять в обидві множини, та визначити найбільше серед них. Воно і буде найбільшим спільним дільником.
Застосування елементів теорії графів для рішення задачі розміщення пунктів обслуговування
Задачі розміщення пов'язані з вирішенням проблем оптимального розташування у певних регіонах пунктів обслуговування, таких як: торговельні центри, станції техобслуговування, автозаправні станції, пости пожежної охорони, лікарні, туристичні центри, склади, пошти, готелі і тому подібне. Математична структура таких задач визначається конфігурацією області припустимих точок розміщення і способом оцінки якості розміщення. Внаслідок цього існує багато різноманітних задач розміщення, що стосуються різних сфер знань і у технічній літературі пропонується чимало методів їх розв'язання.
Для того, щоб формулювати і розв'язувати задачі про розміщення, необхідно ввести нові поняття теорії графів:
- центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої від неї вершини є мінімальною.
- головним центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої точки на ребрах графа є мінімальною.
- абсолютним центром графа називається будь-яка точка на ребрі, відстань від якої до найвіддаленішої вершини графа є мінімальною.
- головним абсолютним центром графа називається будь-яка точка, відстань від якої до найвіддаленішої точки є мінімальною.
- медіаною графа називається точка, в якій сума відстаней до усіх вершин графа є мінімальною (аналогічно центрам можна ввести поняття головної, абсолютної і головної абсолютної медіани).
При розв'язанні задач на знаходження розміщення центрів обслуговування слід домовитися про область, у якій їх можна розміщувати. Обмежимося тільки тими задачами, для яких областю припустимих точок розміщення центрів обслуговування є деякий граф. Центри, в даному випадку, можуть розташовуватися тільки у вершинах та ребрах графа і ніде більше.
Загрузка ...