Знаходження головного центру графа (реалізація в середовищі Delphi)
В параграфі розглядається delphi-програма, основним призначенням якої є знаходження головного центру для побудованого користувачем графа. Для того, щоб запустити програму необхідно перейти в каталог де він збережений, знайти файл Project.exe і запустити його. Після запуску програми на екрані відображатиметься вікно наступного вигляду:
Головне вікно проекту "Знаходження головного центру графа"
У верхній частині форми міститься панель інструментів (компонент типу TPanel). На панелі розташовується чотири кнопки (дві типу TSpeedButton та дві — TButton) зліва направо: «Додати вершину», «Додати ребро», «Видалити граф», «Знайти головний центр графа». Праворуч від кнопки «Додати ребро» міститься перемикач типу TCheckBox, який відповідає за тип створюваного ребра (якщо перемикач не включений, то програма пряцює в режимі «Розміщення орієнтованого ребра», і навпаки, якщо перемикач включений — в режмрі «Розміщення неорієнтованого ребра». Біла область (компонент типу TImage) називається робочою областю і використовується для візуалізації графа та відображення вершини, яка являється головним центром. Нижня частина форми (компонент типу TMemo) призначена для виводу результатів роботи програми.
Збережено в категорії: Програми на Delphi (Дослідження операцій) · Мітки: Delphi програма, Delphi проект, головний центр графа delphi, центр графа delphi
(Кількість голочів: 1, середній бал: 5.00 із 5)
Загрузка ...Знаходження головного центру графа
Головний центр грфа - це будь-яка його вершина, відстань від якої до найвіддаленішої точки на ребрах графа є мінімально. Зазначимо, що знаходження головного центру може бути корисно для задач розміщення підприємств, метою яких є мінімізація максимальної відстані яку повинен здолати їх праціник. Наприклад, розміщення станції обслуговування у вершині, яка являється головним центром побудованого для задачі графа, дає змого мінімізувати максимальну відстань, яку повинен здолати ремонтник до можливого місця поломки.
Розглянемо далі один із способів рішення задач на знаходження головного центру. Але, для початку, введемо деякі визначення, необхідні для опису точок на ребрах та деяких відстаней в графі.
Отже, припустимо, що розглядається деякий граф 
, множина 
якого містить вершини з номерами від одиниці до 
. Розглянемо довільне ребро 
даного графа, довжина якого дорівнює 
. Нехай 
позначає точку на ребрі , яка для всіх 
віддалена на 
одиниць від вершини 
та на 
одиниць від вершини 
. Зазначимо, що дана точка називається -точкою.
Розміщення точки на ребрі графа
Таким чином, чверть-точкою ребра є точка, віддалена від вершини на 
довжини ребра . Нуль-точкою ребра являється вершина , а одиничною - вершина . Отже, вершини графа також можуть розглядатися як точки його ребер. Точки ребер, які не є вершинами, називаються внутрішніми. Будь-яка точка ребра повинна бути або внутрішньою, або вершиною. Нехай через 
позначається множина всіх точок графа . Таким чином, різниця 
являється множиною всіх його внутрішніх точок.
Збережено в категорії: Дослідження операцій · Мітки: f-точка ребра, відстань вершина - ребро, головний центр графа, матриця відстаней, центр графа
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Розкладання натуральних чисел на прості множники
Основна теорема арифметики стверджує, що будь-яке натуральне число, більше одиниці, можна представити у вигляді добутку простих чисел, причому єдиним способом (якщо не враховувати їх порядок). Наприклад число 125 можна представити як 
де 5 — просте число. Нагадаємо, що розкладання чисел на добуток простих множників, називається їх факторизацією.
У цьому параграфі, для розкладання чисел на множники, ми скористаємось методом, який базується на повному переборі всіх простих чисел від двох до заданого числа. Зазначимо, що навіть попри такий недостаток, як необхідність у побудові таблиці простих чисел, даний метод досить швидко справляється із завданням, навіть для дуже великих чисел.
import java.util.Scanner;
class Decomposition_by_factors {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// ВВвід числа, розкладання якого необхідно отримати
System.out.print("Enter a number to decompose: ");
int num = scann.nextInt();
int c_num = num;
int n = 0;
int i = 2;
int table[] = new int[num + 1];
int dec[] = new int[num + 1];
// Побудова таблиці простих чисел
table = Sieve_of_eratosthenes(num);
// Знаходження розкладання заданого числа на прості множники
while (num > 1) {
if (table[i] != 0) {
while (num % table[i] == 0) {
num = num / table[i];
dec[n] = table[i];
n++;
}
}
i++;
}
// Вивід результатів роботи програми
System.out.print(c_num + " = "+ dec[0]);
for (int j = 1; i <= n - 1; j++) {
System.out.print(" * " + dec[j]);
}
System.out.print(";");
}
Для побудови таблиці простих чисел, що не перевищують заданого числа, в програмі визначено додатковий методу Sieve_of_eratosthenes — повертає необхідний нам результат у вигляді масиву.
Збережено в категорії: Реалізація відомих алгоритмів на Java · Мітки: java програма, прості множники, просте число, розкладання на множники java, таблиця простих чисел java, факторизація чисел java
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Решето Ератосфена — метод пошуку простих чисел
Як ми вже встигли переконатись, не всі числа важко ідентифікувати як прості або складені. Наприклад, будь-яке парне число більше 2 є складеним. Однак, хоча деякі числа можуть бути легко класифіковані, для інших дана процедура може бути надзвичайно складною. На щастя, є деякі прийоми, які дозволяють значно спростити процес відшукання простих чисел. Одним з таких прийомів є сито Ератосфена — математичний інструмент, який використовується для виявлення всіх можливих простих чисел між будь-якими двома числами. Метою цього параграфу є максимально ефективна реалізація даного алгоритму засобами Java, не вдаючись до імпорту будь-яких стандартних бібліотек.
Виходячи з того, що пошук, в даному випадку, завжди буде починатись з двійки, то для здійснення задуманого, від користувача, нам знадобиться лише кінець діапазону. Отже, на першому кроці, реалізуємо процес його введення.
import java.util.Scanner;
class Sieve_of_eratosthenes {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// Ввід кінця діапазону
System.out.print("Enter end of range: ");
int end = scann.nextInt();
Далі, оголошуємо та виділяємо пам'ять під масив з числами цілого типу і, простим присвоюванням в циклі (починаючи з двійки і закінчуючи кінцем діапазону) виконуємо запис значень в його комірки.
Збережено в категорії: Реалізація відомих алгоритмів на Java · Мітки: java програма, прості числа, прості числа java, решето Ератосфена java, сито Ератосфена java
(Кількість голочів: 3, середній бал: 5.00 із 5) Загрузка ...Знаходження найменшого спільного кратного двох чисел
У параграфі розглядається покроковий процес написання нескладної java-програми, яка обчислює найменше спільне кратне (НСК) двох цілих додатних чисел. Зазначимо, що для реалізації задуваного використовується відомий зв'язок між НСК і НСД (найбільший спільний дільник), за яким найменше спільне кратне двох чисел обчислюється як добуток даних чисел, поділений на їх найбільший спільний дільник.
Отже, почнемо написання програми і для початку створимо «Java Project». Потім, в ньому, створимо «Java Class» і назвемо його Least_common_multiple. На наступному кроці, за допомогою методу print, виведемо в консоль запит на введення числа number1 без переходу на наступний рядок. Далі, скориставшись методом nextInt класу Scanner, читаємо введене користувачем ціле число з консолі. Після цього, скопіювавши останні дві інструкції, змінемо їх для зчитування значення числа number2.
Після того, як з вхіднимим даними розібрались, обчислюємо добуток чисел number1 і number2 та реалізуємо процес знаходження НСД за алгоритмом Евкліда.
Збережено в категорії: Реалізація відомих алгоритмів на Java · Мітки: ava програма, алгоритм Евкліда java, найбільший спільний дільник java, найменше спільне кратне java, НСД java, НСК java
(Кількість голочів: 2, середній бал: 5.00 із 5) Загрузка ...Алгоритм Евкліда — знаходження найбільшого спільного дільника
Нагадаємо, що у параграфі найбільший спільний дільник (НСД), нами було сформульовано означення та розглянуто основні методи знаходження НСД. На продовження даної теми, сьогодні буде створена 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();
Зазначимо, що для того, щоб не обтяжувати користувача зайвими турботами, ми дозволимо йому вводити числа в довільному порядку, хоча для алгоритму важливо, щоб перше число було більше другого. Тобто, будемо виправляти цю ситуацію програмно, якщо в цьому винекне необхідність.
Збережено в категорії: Реалізація відомих алгоритмів на Java · Мітки: java програма, алгоритм Евкліда java, найбільший спільний дільник, найбільший спільний дільник java, НСД java
(Кількість голочів: 2, середній бал: 5.00 із 5) Загрузка ...Найменше спільне кратне двох натуральних чисел
Кратним числа 
називається таке число, яке саме ділиться на без залишку. Спільне кратне чисел і 
— це число, що є кратним для кожного з них.
До прикладу, числа 10 і 15 мають спільне кратне 180. Числа 150, 120, 90 — також є спільними кратними цих чисел. Серед всіх спільних кратних завжди є найменше, в даному випадку таким являється число 30. Це число називають найменшим спільним кратним (НОК) і позначають 
.
Щоб знайти найменше спільне кратне двох чисел, потрібно розкласти їх на прості множники. Після цього, необхідно вибрати всі прості множник що входять в обидві множини та перемножити їх між собою. На наступному кроці, отриманий результат необхідно також помножити на прості множники, числа , які не являються множниками числа та прості множникик числа , що не являються простими множниками числа . До прикладу, для чисел 441 та 350 даний процес виглядатиме наступним чином:
Збережено в категорії: Математика · Мітки: алгоритм Евкліда, метод знаходження НСК, найбільший спільний дільник, НСД, приклад знаходження НСК
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...
Загрузка ...