การแยก อัลกอริทึม

Division Algorithm

ทฤษฎี (Division Algorithm) ถ้า a และ d  เป็นจำนวน ซึ่ง d  > 0 แล้ว แล้วมีจำนวนเต็ม q และ r คู่หนึ่งและคู่เดียวเท่านั้น  ซึ่งมีคุณสมบัติว่า

                                a =  dq + r       ,    0 ≤ r < d

                      (ในที่นี้การพิสูจน์จะเว้นไว้)

หมายเหตุ  จากทฤษฎี  ซึ่งได้กล่าวว่า สำหรับทุกๆ a,d € Z , d > 0 จะมี q,r € Z  ซึ่งมีคุณสมบัติว่า 

 a = dq + r   , 0≤ r < d

                เราเรียก  a  ว่า ตัวตั้ง(dividend)

                เรียก  d ว่า  ตัวหาร(divisor) ในการหาร a ด้วย d

                เรียก  q ว่า  ผลตัวหาร(quotient) ในการหาร a ด้วย d

                และเรียก r  ว่า เศษ (remainder)    ในการหาร a ด้วย d

         เราจะเห็นได้ชัดว่า  d เป็นตัวหารที่ลงตัว  ของ a  ก็ต่อเมื่อเศษในการหาร  a  ด้วย  d เท่ากับ 0

                ถ้าทั้ง a และ d เป็นจำนวนเต็มบวกทั้งคู่  แล้วผลหาร และเศษในการหาร a ด้วย  d  อาจจะหาได้โดยวิธีการหารยาวในทางเลขคณิต

ตัวอย่าง  จงหาผลหารและเศษจาการหาร 101 ด้วย 11

วิธีทำ

                101= 11. 9  + 2

                ดังนั้นเศษคือ 2 และผลหารคือ 9

ตัวอย่าง  จงหาผลหารและเศษจาการหาร -11 ด้วย 3

วิธีทำ

                -11= 3(-4)  + 1

                ดังนั้นเศษคือ 1 และผลหารคือ -4

 ข้อสังเกตุ เศษที่เหลือจากการหารจะไม่เป็นจำนนวนลบ จากตัวอย่างข้างต้น เศษที่เเหลือจากการหารจะไม่เป็น -2 ถึงแม้ว่า -11 = 3(-3) - 2 เนื่องจาก r = -2 จะไม่สอดคล้องกับเงื่อนไขที่กล่าวว่า

 0≤ r < 3

ขอขอบคุณ staff.buu.ac.th/~seree/310213/chap05.doc