FANDOM


                                  == อัลกอริทึมของยูคลิด สำหรับการหา ห.ร.ม. ==

'''เนื้อหา'''

         ยูคลิด เป็นนักคณิตศาสตร์สมัย 2 พันกว่าปีที่แล้ว ยูคลิดได้ให้วิธีการหา ห.ร.ม. จึงจัดว่าเป็นวิธีที่มีประสิทธิภาพสูงสุด และยอมรับกันมาจนปัจจุบัน 

การหา ห.ร.ม. โดยวิธีการหากำลังของเลขจำนวนเฉพาะ ดังที่กล่างมาแล้วเป็นวิธีที่ยาก ยูคลิดได้ให้หลักการเป็นทฤษฎีง่าย ๆ ว่า "ตัวหารร่วมมากที่สุดของ a และ b ก็จะเป็นตัวหารร่วมมากที่สุดของ a + kb และ b เมื่อ k เป็นเลขจำนวนเต็มใด ๆ"

                                            34209

'''วิธีการหา หรม.ของยูคลิด'''

1.จากตัวเลข  8 12 
             (8,12)12 = 8 x 1 + 4 
             (8, 4)8 = 4 x 2 
             ตอบ    4 คือตัวหารร่วมมากที่สุดของ 8 กับ 12 
2.ตัวเลข   330, 140 
             (330, 140)           330 = 140 x 2 + 50 
             (140, 50)             140 = 50 x 2 + 40 
             (50,40)                50 = 40 x 1 + 10 
             (40,10)                40 = 10 x 
              ตอบ       10 เป็นตัวหารร่วมมากที่สุดของ 340, 140 
อีกตัวอย่างจากโจรย์ข้อ 2 เป็นอีกวิธี ดังนี้
2.1การหา ห.ร.ม. ของ 330 กับ 140 
  
               a = bq1+r2, 0 < r2 < b  ; 330 = 140.2 + 50;  
               b = r2q2+r3,0 < r3 < r2 ; 180 = 50. 2 + 40;  
              r2 = r3q3+r4,0 < r4 < r3 ; 50  = 40. 1 + 10;  
              
                   40 = 10 . 4  
              rn-2 = rn-1qn-1 + rn ,0  <  rn  <  rn-1 ;  
              rn-1 = rnqn  
              ห.ร.ม.ของ(330,140)คือ 10
       จากหลักการของยูคลิดสรุปได้ว่า  ตัวหารร่วมมากของ 40, 10 ก็จะเป็นตัวหารร่วมมากของ 50, 40 ด้วย และไล่เรียงขึ้นไปถึง 330, 140 นั่นเอง 
                                                                                  Kapook 43496

คำที่เกี่ยวข้อง Edit

            1.การหา หรม.
   เอกสารอ้างอิง
            http://blog.spu.ac.th/malee/2007/12/06/entry-2


                                          Kapook 43007