유클리드 기법을 활용하여 최대 공약수를 구하는법.

 

다음은 분수의 덧셈이다.

 

ex)

유리수 1의 분자 분모 :  1 / 2

유리수 2의 분자 분모 : 1 / 3

 

계산결과는 5/6  이 출력 되어야 한다.

 

 

 

 

#include <stdio.h>
#include <iostream>

int main() 
{
	int num1 =10;
	int num2 = 5;
	int c;

	int num_num1 = 1;
	int num_num2 = 2;


	int a = 10;
	int b = 5;
	int max;

	while (num2 != 0) 
	{
		c = (num1 % num2);
		num1 = num2;
		num2 = c ;

	}

	printf("%d\n", num1); //최대공약수
	max = (a*b) / num1;
	printf("%d\n", max); // 최소공배수


	num_num1 = max;
	num_num2 = max;

	printf("%d / %d \n", num_num1, a);
	printf("%d / %d \n", num_num2, b);

	system("pause");
	return 0;
}

 

 

 

유클리드(알고리즘) 기법.

 

유클리드 기법으로 최대 공약수를 구하는 과정을 설명 하겠습니다.

 

아래의 표를 잘 보시기 바랍니다.

 

a =10	%(나머지 연산자)	b =5	c =0
a=b --> 5 가 됨		b=c -->0이됨
이후 5는 0으로 더이상 나눌수 없게됨.

 

• 위의 표의 첫번째 행을 잘보시기 바랍니다. 10 과 5의 최대공약수를 구하려면 우선 나누기 연산자로 나머지 값을 구합니다.
• 즉. 나누고자 하는 값이 0 이 될때 까지 계속 계산 계산된 값은 c 는 b에 복사 원래 b는 a에 복사.
• 계산된 값이 0이 나오고 그값이 b에 들어 가게 될테니 b가 0이 될때까지 반복하면 될것입니다.

순서는 b의 값을 a에 먼저 대입하고 c에 값을 b에 넣어야 이상한 값이 출력 되지 않겠죠?

 

위의 상황이 이해가 안가신다면

 

순서를 반대로 해서 출력해보시면 알게 되실겁니다.