Python에서 최대 공약수를 찾는 방법

이번에는 Python최대 공약수를 찾는 방법과 Python이 최대 공약수를 찾는 데 필요한 노트가 무엇인지 알려드리겠습니다. 실제 사례를 살펴보겠습니다.

이전에 Knuth TAOCP에서 최대공약수 풀이를 정리한 적이 있습니다. 사실 방과후 문제의 알고리즘 수정에는 유클리드 나눗셈에 의한 최대공약수 풀이의 구현이 필요합니다.

이 질문에 대한 나의 초기 이해가 잘못되어 당연히 표준적인 답변이 없었습니다. 이제 표준 답변에 따라 해당 코드 구현을 작성합니다.

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(55,120))

프로그램 실행 결과:

두 숫자의 위치를 ​​바꾸면 코드는 다음과 같습니다.

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(120,55))

프로그램 실행 결과 :

위의 코드로 판단하면 효율성의 손실은 분할과 판단에 있다고 질문 프롬프트에서 언급했습니다. 여기에서 이전 알고리즘의 코드를 가져와 비교해 보세요.

def CommDevisor(m,n):
  r = m % n
  while r != 0:
    m = n
    n = r
    r = m % n
  return n
print(CommDevisor(120,25))

실행 결과:

새 알고리즘에는 loop에 추가 나누기 및 비교 연산이 있습니다. 실제로 비교 효율성은 여전히 ​​좋지만, 분할 연산으로 인해 효율성이 떨어지게 됩니다.

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

추천 도서:

Python Numpy가 배열과 행렬을 작동하는 방법

Python을 작동하여 numpy 배열을 탐색하는 방법

위 내용은 Python에서 최대 공약수를 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!