최대공약수를 계산하는 C++ 프로그램

최대 공약수 또는 최대 공약수는 둘 이상의 값을 나머지를 생성하지 않고 동시에 나눌 수 있는 인수입니다. 이 기사에서는 C++에서 두 숫자의 HCF/GCD를 수행하는 여러 가지 방법에 대해 설명합니다.

이것은 단지 수학적 해법일 뿐이며, 최대 공약수를 찾는 여러 알고리즘이 있습니다. 유클리드 방법은 최대 공약수를 찾는 일반적인 방법입니다. 반복 및 재귀 모드에서 동일한 알고리즘을 사용합니다.

반복적인 방법을 사용하세요

최대 공약수를 찾는 유클리드 반복 솔루션은 알고리즘 섹션에 나와 있습니다.

알고리즘

• 두 개의 숫자 a와 b를 입력으로 사용합니다.
• a가 0이면 b를 반환합니다.
• b가 0이면 a를 반환합니다.
• a와 b가 동일하지 않으면 작업을 수행합니다.
  • a > b이면 a := a – b입니다.
  • 그렇지 않으면 b := b - a.
• 루프를 종료합니다.
• 최대공약수를 변수 a로 반환합니다.

예

으아아아

출력

으아아아

반복적인 방법을 사용하세요

재귀적 방법을 사용하여 동일한 유클리드 방법을 구현할 수 있습니다. 아래에서는 재귀적 방법의 정의, 즉 아래에 표시된 알고리즘을 설명합니다.

알고리즘

• 두 숫자 a와 b를 받아들이는 HCF라는 함수를 정의하세요.
• a가 0이면 b를 반환합니다
• 그렇지 않으면 HCF( b mod a, a)를 반환

예

으아아아

출력

으아아아

결론

최대 공약수 또는 최대 공약수를 찾는 것은 다양한 수학 문제를 해결할 때 매우 유용합니다. 유클리드 방법을 사용하여 계산할 수 있습니다. 이 방법은 반복적으로 또는 재귀적으로 적용될 수 있습니다. 여기서는 두 가지 방법을 보여줍니다. 반면, 최소공배수(LCM)를 통해 GCD/HCF를 계산할 수 있습니다. 두 숫자의 GCD와 LCM은 두 숫자의 곱과 같습니다. 따라서 이 원리에 따라 이 두 숫자의 LCM과 곱을 알면 GCD를 쉽게 계산할 수 있습니다.

위 내용은 최대공약수를 계산하는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!