//
// EUCLID1.C : Implementation of Euclid's Algorithm
//
// Programmed By Clipper
// Copyright ⓒ 2007 LaLuna All Rights Reserved.
//
#include <stdio.h>
#include "timer.h"
int get_gcd(int u, int v); //뻴셈만을 이용한 유클리드 : 최대공약수
int gcd_modulus(int u, int v); //나머지연산을 이용한 유클리드 : 최대공약수
int gcd_recursion(int u, int v); //재귀호출을 이용한 유클리드 : 최대공약수
#define LOOF 10000000 //함수의 성능 테스트를 위한 반복 횟수
int main(int argc, char *argv[])
{
int u, v, temp;
clock_t t1, t2; //함수 측정시간을 정하기 위한 변수
float result1 = 0, result2 = 0, result3 = 0;//함수 측정시간을 저장하기 위한 변수
int i;
puts("\n EUCLID1 : 두 양수의 최대 공약수 찾기 ");
puts("\n 0을 입력하면 종료");
while(1)
{
puts("\n\n 두 양수를 입력하세요 -> ");
scanf("%d %d", &u, &v);
if(u < 0 || v < 0)//음수의 입력은 무효로 한다.
{
puts("음수를 입력하셨습니다. 양수를 입력하세요\n");
continue;
}
if(u == 0 || v == 0)//0이 입력되면 종료한다.
{
puts("0을 입력하셨습니다. 프로그램을 종료하겠습니다.\n");
break;
}
t1 = clock();
for(i=0;i<LOOF;i++)
{
temp = get_gcd(u,v);
}
t2 = clock();
result1 = diff_clock(t1,t2);//빼기, 교환 함수 시간 측정
t1 = clock();
for(i=0;i<:LOOF;i++)
{
temp = gcd_modulus(u,v);
}
t2 = clock();
result2 = diff_clock(t1,t2);//나머지 함수 시간 측정
t1 = clock();
for(i=0;i<LOOF;i++)
{
temp = gcd_recursion(u,v);
}
t2 = clock();
result3 = diff_clock(t1,t2);//재귀호출 시간측정
printf("두 양수 %d와 %d의 최대 공약수는 %d입니다.(뺄셈과 교환)\n", u, v, get_gcd(u,v));
printf("두 양수 %d와 %d의 최대 공약수는 %d입니다.(나머지연산)\n", u, v, gcd_modulus(u,v));
printf("두 양수 %d와 %d의 최대 공약수는 %d입니다.(재귀호출)\n", u, v, gcd_recursion(u,v));
printf("빼기연산 : %5.2f 나머지 연산 : %5.2f 재귀호출 연산 : %5.2f", result1, result2, result3);
}
system("pause");
return 0;
}
int get_gcd(int u, int v)
{
int temp;
while(u)//u가 0이면 v를 리턴, 아니면 루프를 돈다.
{
if(u < v)//u가 v보다 작으면 교환한다.
{
temp = u;
u = v;
v = temp;
}
u = u - v;
}
return v;
}
int gcd_modulus(int u, int v)
{
int t;
while(v)//v가 0이면 u를 리턴, 아니면 루프를 돈다.
{
t = u % v;
u = v;
v = t;
}
return u;
}
int gcd_recursion(int u, int v)
{
if(v == 0)
{
return u;
}
else
{
return gcd_recursion(v, u%v);//재귀호출을 이용하여 나머지 연산
}
}
