NumRangeGcd
ФОРМУЛИРОВКА ЗАДАЧИ:
Найти наибольший общий делитель всех чисел в заданном диапазоне [L, R].
ПРОГРАММНЫЙ КОД:
Исходный программный код содержится в файле src\NumRangeGcd.java.
НАЗНАЧЕНИЕ:
Класс NumRangeGcd реализует:
- метод SearchGcd поиска наибольшего общего делителя (НОД) всех целых положительных чисел из указанного диапазона [L, R];
- метод Gcd вычисления НОД двух натуральных чисел по алгоритму Евклида с использованием рекурсии;
- метод main, обеспечивающий консольный интерфейс взаимодействия с пользователем.
АЛГОРИТМ:
Если в указанном диапазоне [L, R] верно, что L = R или L * 2 < R, то решение поиска максимального НОД тривиальное и выполняется без перебора границ L, R и вычисления НОД, иначе запускается следующий алгоритм:
Начальный диапазон [L, R] пошагово сужается путём целочисленного округления левой границы до ближайшего большего целого, кратного i, где i = (1, 2, ...), и правой границы до ближайшего меньшего целого, кратного i. Сужение диапазона завершается, если границы [L', R'] совпадут. На каждом шаге алгоритма проверяется НОД(R', L') на максимальное значение. Функция НОД реализована по алгоритму Евклида с использованием рекурсии.
СЛОЖНОСТЬ:
В приложении реализован алгоритм с линейной временной сложностью не менее O((R-L)*log2(R)), определяемой длиной отрезка целых положительных чисел из указанного диапазона [L, R]. Здесь log2 означает логарифм по основанию 2.
РЕАЛИЗАЦИЯ:
Java version "11.0.1", использованы стандартные возможности JDK.
ОГРАНИЧЕНИЯ:
Приложение допускает обработку только целых положительных чисел диапазона типа Integer.
ТЕСТИРОВАНИЕ:
Тестирование корректности получаемых результатов работы приложения выполнялось полуавтоматизированным способом, без их проверки альтернативным (другим) автоматизированным алгоритмом.
КОНТРОЛЬНЫЙ ПРИМЕР выполнения приложения:
<Наибольший общий делитель диапазона чисел> NesioIV, 2022
Введите начало диапазона A (целое число 1 < A <= 2147483647): 123
Введите конец диапазона B (целое число 123 <= B <= 2147483647): 245
Выполняется поиск наибольшего общего делителя (НОД) диапазона чисел...
Начало диапазона А: 123
Конец диапазона B: 245
Найденный НОД диапазона: 81
Первый аргумент НОД: 162
Второй аргумент НОД: 243
Время выполнения, мс
0
= Выполнение завершено =
Process finished with exit code 0