Программа для поиска GCD или HCF двух чисел

GCD (наибольший общий делитель) или HCF (наибольший общий делитель) двух чисел — это наибольшее число, которое делит их оба.

Например, НОД 20 и 28 равен 4, а НОД 98 и 56 равен 14.

Простой и старый подход — это алгоритм Евклида путем вычитания.

Это процесс повторного вычитания, при котором результат каждый раз переносится вперед, пока результат не станет равным любому вычитаемому числу. Если ответ больше 1, есть НОД (помимо 1). Если ответ равен 1, то общего делителя нет (кроме 1), а значит, оба числа взаимно просты.

псевдокод для вышеуказанного подхода:

def gcd(a, b):
  if a == b:
    return a
  if a > b:
    gcd(a – b, b)
  else:
    gcd(a, b – a)

В какой-то момент одно число становится множителем другого, поэтому вместо многократного вычитания, пока оба не станут равными, мы проверяем, является ли оно множителем другого.

Например, предположим, что a=98 и b=56 a>b, поэтому поместите a=ab, а b останется прежним. Итак, a=98-56=42 & b= 56. Поскольку b>a, мы проверяем, является ли b%a==0. поскольку ответ отрицательный, мы идем дальше. Теперь b>a, поэтому b=ba и a остаются прежними. Итак, b= 56-42 = 14 и a= 42. Поскольку a>b, мы проверяем, является ли a%b==0 . Теперь да. Поэтому мы печатаем меньший среди a и b как HCF . т.е. 42 в 3 раза больше 14, поэтому HCF равно 14.

аналогично, когда a=36 и b=60, здесь b>a, поэтому b = 24 и a= 36, но a%b!=0. Теперь a>b, поэтому a= 12 & b= 24. и б%а==0. меньшее из a и b равно 12, что становится HCF 36 и 60.

Простое решение:

Подход: для нахождения НОД двух чисел мы сначала найдем минимум двух чисел, а затем найдем наибольший общий множитель этого минимума, который также является множителем другого числа.

Сложность времени: О (мин (а, б))
Вспомогательное пространство: O(1) или постоянная

Эффективным решением является использование алгоритма Евклида, который является основным алгоритмом, используемым для этой цели. Идея в том, что НОД двух чисел не меняется, если меньшее число вычитается из большего числа.

Временная сложность: O(мин(а,б))
Вспомогательное пространство: O(min(a,b))

Динамический подход к программированию ( сверху вниз с использованием мемоизации ):

Временная сложность: O(мин(а,б))
Вспомогательное пространство: O(1)

Вместо алгоритма Евклида методом вычитания присутствует лучший подход. Здесь мы не выполняем вычитание. мы непрерывно делим большее число на меньшее число. Подробнее об этом эффективном решении можно узнать, используя оператор по модулю в алгоритме Евклида.

Временная сложность: O (log (мин (a, b)) |
Вспомогательное пространство: O(log(min(a,b))

Временная сложность для приведенного выше алгоритма составляет O (log (min (a, b))) вывод для этого получен из анализа сценария наихудшего случая. Что мы делаем, так это спрашиваем, каковы 2 наименьших числа, которые делают 1 шаг, это будут (1,1). Если мы хотим увеличить количество шагов до 2, сохраняя числа как можно меньшими, мы можем взять числа равными (1,2). Точно так же для 3 шагов числа будут (2,3), 4 будут (3,5), 5 будут (5,8). Таким образом, мы можем заметить здесь закономерность, для n-го шага числа будут (fib(n), fib(n+1)). Таким образом, временная сложность в наихудшем случае будет равна O(n), где a>= fib(n) и b>= fib(n+1).

Теперь ряд Фибоначчи представляет собой экспоненциально растущий ряд, в котором отношение n-го / (n-1)-го члена приближается к (sqrt (5) + 1) / 2, что также называется золотым сечением. Таким образом, мы видим, что временная сложность алгоритма увеличивается линейно по мере экспоненциального роста членов, поэтому временная сложность будет равна log (min (a, b)).

Пожалуйста, обратитесь к GCD из более чем двух (или массива) чисел, чтобы найти HCF из более чем двух чисел.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.