c언어 함수 주요예제 3. (유클리드 호제법)

유클리드 호제법을 이용하여 최대공약수를 구하는 함수.

#include <stdio.h>

int gcd(int a, int b);

int main(void) {

	int i, k;

	printf("최대 공약수를 구할 수를 입력받습니다. \n");
	printf("첫번째 수를 입력하세요 : "); scanf_s("%d", &i);
	printf("두번째 수를 입력하세요 : "); scanf_s("%d", &k);

	printf("%d와 %d의 최대공약수는 %d입니다.", i, k, gcd(i, k));

}

//유클리드 호제법을 이용해서 최대공약수를 계산하는 함수
int gcd(int a, int b)
{
	int abs_a = (a > 0) ? a : -a;
	int abs_b = (b > 0) ? b : -b;

	//gcd(0,0) = 0
	if (a == 0 && b == 0) {
		return 0;
	}
	//gcd(a,0) = a , gcd(0,b) = b
	else if (a == 0 || b == 0) {
		return a == 0 ? b : a;
	}

	if (abs_a > abs_b) {
		return abs_a % abs_b ? gcd(b, a%b) : b;
	}
	else {
		return abs_b % abs_a ? gcd(a, b%a) : a;
	}
}

//원래는 함수내에서 지역변수를 쓰지 않는 예제인데 음수처리 때문에 변경함.

유클리드 호제법

내용

A와 B의 최대공약수를 GCD(A,B)라 하자.

A>B일 때, A = Bq+R (0 <= R < A)라 하면,

CGD(A,B) = GCD(B,R)이다.

풀어쓰면 A와 B의 최대공약수는

B와 A를 B로 나눈 나머지 R의 최대공약수와 같다.

증명

m과 n가 서로소일 때 A= mk, B = nk라고 할 수 있다.

A를 B로 나눈 것을 A=Bq+R로 표현하면 

mk = nkq+R이라 할 수 있고 이를 R에 대해서 정리하면 R = (m-nq)k 라 할 수 있다.

B와 R 모두 k로 나눠지므로 두 수의 공약수는 k이다. 

이때 n과 (m-nq)가 서로소이면 k는 B와 R의 최대공약수이다.

일단 n과 (m-nq)가 서로소가 아니라고 가정하자.

그러면 o와 p가 서로소이고 l != 1이면 n = ol, m-nq = pl이라 할 수 있다.

m-nq=pl을 m에 대해서 정리하면 m = pl+nq이고 n=ol이므로 m= (p+oq)l로 정리할 수 있다.

이때 l != 1이면 m과 n이 서로소가 아니라는 뜻이므로 맨 처음 가정에 모순되므로 

n과 (m-nq)는 서로소이다. 

그러므로 A와 B의 최대공약수는 k이고, B와 R의 최대공약수도 K이다.

//수학 오랜만에 하니까 증명이 깔끔하지 않다...

지역변수와 정적변수의 차이점을 보여주는 예제

#include <stdio.h>

void demo(void);

int main(void) {

	for (int i = 0; i < 5; i++) {
		demo();
	}

}

void demo(void) {
	int avar = 0;
	static int svar; 
	// static 변수는 초기값을 주지 않으면 0으로 자동 초기화된다.
	// 하지만 굳이 이렇게 쓰는 걸 추천하지는 않는다.
	
	printf("int avar = %d, static int svar = %d \n", avar, svar);
	avar++;
	svar++;
}