확장 유클리드 알고리즘을 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 두 개의 숫자가 주어지면 이 두 숫자의 gcd를 계산하여 표시해야 합니다.

두 숫자의 GCD 최대 공약수는 두 숫자를 모두 나눌 수 있는 가장 큰 숫자입니다. 여기서 우리는 gcd를 계산하기 위해 유클리드 접근 방식을 따릅니다. 즉, 숫자를 반복적으로 나누고 나머지가 0이 되면 중지합니다. 여기서 우리는 재귀에서 얻은 이전 값을 기반으로 알고리즘을 확장합니다.

이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -

예시

# extended Euclidean Algorithm
def gcdExtended(a, b, x, y):
   # Base Case
   if a == 0 :
      x = 0
      y = 1
      return b
   x1 = 1
   y1 = 1 # storing the result
   gcd = gcdExtended(b%a, a, x1, y1)
   # Update x and y with previous calculated values
   x = y1 - (b/a) * x1
   y = x1
   return gcd
x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of ", a , "&" , b, " is = ", g)

출력

gcd of 11 & 15 is = 1

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서는 확장 유클리드 알고리즘을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.