Алгоритм Евкліда – знаходження найбільшого спільного дільника

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

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

// Якщо перше число менше другого, то міняємо їх значення
if (number1 < number2) {
int number = number1;
number1 = number2;
number2 = number;
}

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

int res;
// Знаходження НСД
do {
res = number1 % number2;
number1 = number2;
number2 = res;
} while (res != 0);
// Виводимо результати роботи програми
System.out.print(“Greatest common divisor:” + number1);
}
}

Далі, скомпілювавши, запустивши та задавши в якості чисел для яких відшукується найбільший спільний дільник значення 1432 і 41, на екрані відобразиться наступний результат:

Алгоритм Евкліда java
Знаходження найбільшого спільного дільника двох додатних цілих чисел

Залишити коментар

Your email address will not be published. Required fields are marked *

*