|
|
#1 (permalink) |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: USA
Posts: 508
![]() |
Let's see how good your cerebral hash functions are...
What's the name of that famous math algorithm where you take two numbers x and y, mod one by the other to get z, and then discard max(x,y) so now you're left with x' = min(x,y) and z. Repeat process with x' and z until one of the numbers in your hand is 1. The other is X. What number X do you end up with? What is the running time? |
|
|
|
|
|
#3 (permalink) | |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: Albania
Posts: 534
![]() |
Quote:
|
|
|
|
|
|
|
#4 (permalink) |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: USA
Posts: 508
![]() |
Let's see, AlbaLed. I think I did have a typo, but here's a link that should clear it up:
http://www.cut-the-knot.org/blue/binary.shtml The algorithm is called Euclid's algorithm, andt can be used to find the GCD of two positive integers. It is a "classic numerical algorithm" in the sense of CS AGRE IV.B.2. The examples below demonstrate the algorithm: Find the gcd of 10 and 8. Well, 10 % 8 (per Alba's correction, not 8 % 10) is 2. So now you have 8 and 2. 8 % 2 is 2. So now you have 2 and 2. And 2 % 2 = 1. And 2 % 1 = 0. 2 must be the GCD. Find the gcd of 144 and 282. Well, 282 % 144 = 138. 144 % 138 = 6. 138 % 6 = 0. So the GCD must be 6. [As an aside, the product of 144 and 282 is 40608, which is 6768. Since gcd(a,b) * lcd(a,b) = a*b, the lcd(144,282) must be 6768. SO Euclid's algorithm indirectly gives you a handy way of computing LCDs, also.] As for the run-time of the algorithm, the key is to notice that if you iterate the algorithm twice, then the larger of the two numbers must have been cut by half. For example, if one is 100 and the other is 75, then 100%75 gives you 25; now you have 75 % 25, which is smaller than half of 100. The smaller number is bounded above by the larger number, and we stop when the smaller number hits 0/1. If you know that the larger of the two numbers is N and it goes down by a factor of two every other iteration, then you know that the number of iterations must be logarithmic in N. SO the runtime is O(lg N). |
|
|
|
|
|
#5 (permalink) |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: USA
Posts: 508
![]() |
BTW, somebody asked me to post more code snippet problems. SO let me augment this topic with the following:
int gcd( int num1, int num2 ) { int remainder = num2 % num1; if ( remainder != 0 ) return gcd( remainder,num1 ); return num1; } Suppose that when gcd(M,N) is called (M < N), the resulting execution results in the worst possible runtime. The resulting sequence of num1 values is a famous sequence. What is its name? (ie: what sequence of numbers is "traversed" in the worst case?) |
|
|
|
|
|
#6 (permalink) |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: Albania
Posts: 534
![]() |
Find the gcd of 10 and 8. Well, 10 % 8 (per Alba's correction, not 8 % 10) is 2. So now you have 8 and 2. 8 % 2 is 2. So now you have 2 and 2. And 2 % 2 = 1. And 2 % 1 = 0. 2 must be the GCD.
Nonevent, anything wrong there (the red part)? |
|
|
|
|
|
#7 (permalink) | |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: USA
Posts: 508
![]() |
Quote:
Thanks, Alba.Do you know what sequence numbers happens in the worst case? |
|
|
|
|
|
|
#9 (permalink) | |
|
TestMagic Guru-in-Training
![]() ![]() ![]() Join Date: Oct 2003
Location: USA
Posts: 508
![]() |
Quote:
It's a sequence where the larger number just doesn't seem to want to die. But still, every other iteration, you still have to lose at least half of what you've got, so the big-O constraint still holds. |
|
|
|
|
Contact TestMagic TestMagic Forums Archive Privacy Statement
TestMagic Locations
Legal
Privacy
SEO by vBSEO 3.2.0
Copyright © 2009 TestMagic
Ad Management by RedTyger