Greatest Common Divisor
วันนี้กลับไปอ่านหนังสือ discrete math สมัยเรียนมหาลัย ไปเจอบทนึงพูดถึงเรื่อง GCD หรือ Great Common Divisor หรือในไทยก็ ห.ร.ม. หรือ หารร่วมมาก
วิธีการหาหารร่วมมากโดยปรกติ ก็ คือ แยก factor ของตัวเลข 2 ตัวที่ต้องการหา GCD แล้วก็นำมาหารกันจนเหลือตัวที่ไม่สามารถหารกันลงแล้ว
เช่น
GCD(14, 56) = 2x7 and 2x2x2x7 = 1 and 2x7 = 14
วิธีเขียน Program ก็อาจจะทำได้โดย
int GCD(int a, int b) { int temp = a; int temp2 = b;
int gcd = 1; while((temp % 2 == 0) && (temp2 % 2 == 0)) { temp /= 2; temp2 /= 2; gcd *= 2; } for(int i = 3; i <= a && i <= b; i+=2) { while((temp % i == 0) && (temp2 % i == 0)) { temp /= i; temp2 /= i; gcd *= i; } } return gcd; }
แต่มีอีกหลายวิธีที่ทำได้รวดเร็วกว่าวิธีที่เสนอมานี้เยอะมาก วิธีนึงก็คือ วิธี Euclidean วิธีให้ความคิดไว้ว่า GCD ของ a กับ b เท่ากับ GCD ของ b กับ abs(a-b) หรือสามารถเขียนเป็น program ได้ดังนี้
int GCD(int a, int b) { if(a % b == 0) { return b; } else { return GCD(b, abs(a - b)); } }
จะเห็นได้ว่า วิธี Euclidean ทำให้ program ง่ายขึ้นและรวดเร็วขึ้นด้วย
Create Date : 22 ธันวาคม 2548 |
Last Update : 22 ธันวาคม 2548 21:38:22 น. |
|
1 comments
|
Counter : 537 Pageviews. |
|
|
|