Если у вас возник вопрос, как найти наибольший общий делитель двух чисел (НОД), то эта статья именно для вас. Для решения этой задачи рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя.
Задача на самом деле очень простая, нужно только разобраться в этом алгоритме. Этим мы и займемся.
Рассмотрим главный метод программы:
public static void main(String[] args) throws IOException
{
BufferedReader temp = new BufferedReader( new InputStreamReader(System.in));
System.out.print("Введите первое число: ");
int n1 = Integer.decode(temp.readLine());
System.out.print("Введите второе число: ");
int n2 = Integer.decode(temp.readLine());
int n = 1;
NOD(n1, n2, n);
}
Что же в нем мы делаем? Создали буферную переменную “temp”, которая используется для ввода данных с клавиатуры. Используя объект “Integer.decode()”, декодируем строку в число и заносим эти данные в переменные “n1” и “n2” соответственно. Первая переменная это наше первое число, а вторая – второе число.
Дальше вызываем объект “NOD(n1, n2, n)”, куда передаем первое и второе число, а также переменную “n”, об этой переменной я расскажу чуть позже, а сначала программный код объекта “NOD(n1, n2, n)”:
static void NOD(int num1, int num2, int n) {
n = num1 % num2;
num1 = num2;
num2 = n;
if (n > 0)
NOD(num1, num2, n);
else
System.out.println("НОД равен " + num1);
}
Здесь и происходит поиск НОД’а. Вычисление наибольшего общего делителя реализовано рекурсивно, т.е. объект вызывает сам себя такое количество раз, которое необходимо для поиска НОД’а. Для этого и нужна переменная “n”, которая принимает значение путем деления 1-го числа на 2-е с остатком, т.е. равна остатку от деления двух чисел. А эти числа в свою очередь тоже изменяет свое значение, 1-му числу присваивается значение 2-го числа, а 2-е – принимает значение остатка от деления 1-го числа на 2-е.
Выполнение поиска максимального числа, на которое делятся и первое и второе числа, заканчивается, когда остаток от деления двух чисел равен 0 или меньше 0.
Я уверен, что эта статья поможет при вычислении наибольшего общего делителя двух чисел на языке Java.
Автор: Евтеев Евгений Александрович
