Just Like That .. (^-^)v

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 : 417 Pageviews.  

 
ขอบคุณครับ


โดย: oattie IP: 202.44.14.194 วันที่: 15 พฤศจิกายน 2550 เวลา:0:57:06 น.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิกช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 

Forsberg
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed

ผู้ติดตามบล็อก : 1 คน [?]




[Add Forsberg's blog to your web]