Finding GCD is a good start to study algorithm due to its calculation simplicity.
What people commonly use for figuring out GCD is prime factorization.
Let's say we have two numbers, 720 and 12.
** image from - https://en.wikipedia.org/wiki/Greatest_common_divisor
It is a good method for human who can figure out common divisors without inputting numbers from 1 to increasingly. However, a computer should go through that process.
Thus, our task is to find a good algorithm for computer to calculate GCD.
Let's use some 'MATH' here. =_=
We have numbers A, B. These two numbers are not same and bigger than 1.
If they have a GCD, we can write as below.
** G = GCD
A = a * G
B = b * G
Let's subtract them.
A - B = a * G - b * G
= (a - b) G
So, we can know that A - B also have the same GCD. We can manipulate it.
The GCD of A or B and A - B is same. So that we can subtract a greater number to the rest number until one of these number is zero. When one of number is 0, the rest number is GCD.
GCD(X, 0) = X
** This is because zero is always zero with any number multiplied.
ex) 0 * 1 = 0, 0 * 24098209384 = 0
Let's prove with practical numbers.
GCD(54, 18) = GCD(36, 18)
= GCD(18, 18)
= GCD(18, 0)
Thus, GCD(54, 18) = 18
Examine the calculation. We can notice
-> Subtraction goes on until a greater number becomes less than a smaller number, which is same arithmetic of "%". YEAH!
GCD(54, 18) = GCD(18, 54%18)
= GCD(18, 0)
Now, we have prepared a GCD algorithm for computer.
Let's make functions when inputting numbers vary from 2 to 5.
What we should keep in mind.
1. Find smallest number as divisor
2. Loop should go on until input number -1 are zero
ex) 4 numbers input for GCD, loop should go on until 3 numbers are 0
3. If all input numbers become 0 by divisor, divisor should be GCD.
Below is code of GCD function for 5 arguments(numbers)
int GCD5(unsigned int uiNum1, unsigned int uiNum2, unsigned int uiNum3, unsigned int uiNum4, unsigned int uiNum5)
{
unsigned int uiCnt; //counter for loop
unsigned int uiDiv; //divisor for finding GCD
unsigned int uiNum[5];
unsigned int uiZero;
//putting numbers intto array
uiNum[0] = uiNum1;
uiNum[1] = uiNum2;
uiNum[2] = uiNum3;
uiNum[3] = uiNum4;
uiNum[4] = uiNum5;
//finding GCD(Greatest Common Divisor)
uiDiv = uiNum1;
while(1)
{
//finding divisor
for(uiCnt = 0; 5 > uiCnt; ++uiCnt)
{
if(uiDiv > uiNum[uiCnt] && uiNum[uiCnt] != 0)
{
uiDiv = uiNum[uiCnt];
}
}
printf("Divisor is [%d]\n", uiDiv);
uiZero = 0;
for(uiCnt = 0; 5 > uiCnt; ++uiCnt)
{
uiNum[uiCnt] = uiNum[uiCnt] % uiDiv;
if(0 == (uiNum[uiCnt] = uiNum[uiCnt] % uiDiv))
{
++uiZero;
}
}
if(4 <= uiZero)
{
break;
}
}
if(uiZero == 5)
{
return uiDiv;
}
return uiNum[0] + uiNum[1] + uiNum[2] + uiNum[3] + uiNum[4];
}
'Busan IT > Algorithm' 카테고리의 다른 글
| Sum of serial number(without loop and if state) (0) | 2016.01.01 |
|---|
