집 > 기사 > 백엔드 개발 > Python은 최대 공약수를 푸는 방법을 구현합니다.

Python은 최대 공약수를 푸는 방법을 구현합니다.

php中世界最好的语言원래의: 2018-04-09 15:50:255961검색

이번에는 최대 공약수를 푸는 Python방법을 가져왔습니다. Python의 최대 공약수를 푸는 노트는 무엇인가요? 실제 사례를 살펴보겠습니다.

먼저 인터넷에서 알고리즘에 대한 설명을 다음과 같이 발췌했습니다.

추가 위상 빼기 방법: 업데이트 위상 빼기 방법이라고도 하며, "9장 산수"에서 최대 공약수를 찾는 알고리즘입니다. 원래는 환원을 위해 사용되었던 것인데, 최대공약수가 요구되는 어떤 경우에도 적합합니다.

"산수 구장"은 고대 중국 수학 논문으로, 여기에 나오는 "추가 뺄셈 기법"을 사용하여 두 숫자의 최대 공약수, 즉 "반은 반이 될 수 있다면 반은 반이 될 수 있습니다. 반이고, 반이 반이 될 수 없으면 그 반대도 마찬가지다." 분모와 뺄셈의 수를 정하고, 뺄셈의 수를 줄여서 뺄셈의 수를 줄인다. "

를 현대어로 번역하면 다음과 같습니다.

1단계: 두 개의 양수 정수 가 주어지면 모두 짝수인지 확인합니다. 그렇다면 2를 사용하여 줄이세요. 그렇지 않으면 두 번째 단계를 수행하세요.

2단계: 큰 숫자에서 작은 숫자를 뺀 다음 그 차이를 더 작은 숫자와 비교하고 큰 숫자에서 숫자를 줄입니다. 결과 감산과 차이가 같아질 때까지 이 작업을 계속합니다.

위 설명을 읽은 후 나의 첫 반응은 '이 설명에 문제가 있는 걸까요?'였습니다. 보편성 측면에서는 문제가 있을 수밖에 없습니다. 예를 들어, 4와 4의 최대공약수를 찾았지만 반과 반 후에 결과는 잘못된 것임이 틀림없습니다! 다음 알고리즘도 수행할 수 없습니다!

어쨌든 먼저 위의 알고리즘 설명을 구현해 보겠습니다.

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  # even process
  while m % 2 == 0 and n % 2 == 0:
    m = m / 2
    n = n / 2
  # exchange order when needed
  if m < n:
    m,n = n,m
  # calculate the max comm pisor
  while m - n != n:
    diff = m - n
    if diff > n:
      m = diff
    else:
      m = n
      n = diff
  return n
print(MaxCommpisor(55,120))
print(MaxCommpisor(55,77))
print(MaxCommpisor(32,64))
print(MaxCommpisor(16,128))

실행 결과:

말할 필요도 없이 위 프로그램의 실행에는 오류가 가득합니다. 그렇다면 어떻게 수정해야 할까요?

우선 2로 나눈 모든 것은 결국 다시 계산되어야 합니다! 이렇게 프로그램을 다음과 같이 수정합니다.

def MaxCommpisor(m,n):
  com_factor = 1
  if m == n:
    return n
  else:
    # process for even number
    while m % 2 == 0 and n % 2 == 0:
      m = int(m / 2)
      n = int(n / 2)
      com_factor *= 2
    if m < n:
      m,n = n,m
    diff = m - n
    while n != diff:
      m = diff
      if m < n:
        m,n = n,m
      diff = m - n
    return n * com_factor
print(MaxCommpisor(55,120))
print(MaxCommpisor(55,77))
print(MaxCommpisor(32,64))
print(MaxCommpisor(16,128))

수정 후 위 프로그램의 실행 결과는 다음과 같습니다

이 프로그램을 작성해 보면 조금 이상해 보이지만 전체적인 알고리즘은 그대로 구현되어 있습니다. 유클리드 나눗셈과 같은 알고리즘과 비교하면 이 확률은 loop 수준에서 어느 정도 줄어들 것입니다. 특히 마지막 두 쌍의 테스트 번호의 경우 이 경우 효과가 더 좋습니다. 그러나 아직까지 알고리즘의 전반적인 효율성을 정확하게 측정할 수는 없습니다.

이 기사의 사례를 읽으신 후 방법을 마스터하셨다고 믿습니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!