THUẬT TOÁN EUCLID TRONG VIỆC TÍNH NHANH ƯCLN VÀ BCNN “THUẬT TOÁN EU...
4) Thuật toán Euclid trong việc tính nhanh ƯCLN và BCNN
“Thuật toán Euclid” là một trong những thuật toán cổ nhất được biết đến, từ thời Hy Lạp
cổ đại, sau đó được Euclid (ơ –clit) hệ thống và phát triển nên thuật
toán mang tên ông. Về số học, “Thuật toán Euclid” là một thuật toán
để
xác định ước số chung lớn nhất (GCD
–
Greatest Common
Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên). Khi
có ƯCLN ta cũng tính nhanh được BCNN. Thuật toán này không
yêu cầu việc phân tích thành thừa số 2 số nguyên.
Thuật toán Oclit – dùng để tìm ƯCLN của 2 số nguyên bất kỳ.
Để tìm ƯCLN của hai số nguyên a và b bất kỳ ta dùng cách chia liên
tiếp hay còn gọi là “vòng lặp” như sau:
•
Bước 1: Lấy a chia cho b:
Nếu a chia hết cho b thì ƯCLN(a, b) = b.
Nếu a không chia hết cho b (dư r) thì làm tiếp bước 2.
•
Bước 2: Lấy b chia cho số dư r:
Nếu b chia hết cho r thì ƯCLN(a, b) = r
a
b
Nếu b chia r dư
r
1
(
r
1
≠
0
) thì làm tiếp bước 3.
b
r
1
q
•
Bước 3: Lấy r chia cho số dư
r
1
:
r
1
r
2
q
1
Nếu r chia cho
r
1
dư 0 thì ƯCLN(a, b) =
r
1
Nếu r chia
r
1
dư
r
2
(
r
1
≠
0
) thì làm tiếp bước 4.
r
3
q
2
……..
Bước 4: Lấy
r
1
chia cho số dư
r
2
:
Nếu
r
1
chia hết cho
r
2
thì ƯCLN(a, b) =
r
2
.
r
n
1
r
n
−
(a, b)
Nếu
r
1
cho cho
r
2
dư
r
3
(
r
3
≠
0
) thì làm tiếp
0
q
n
như trên đến khi số dư bằng 0.
Số dư cuối cùng khác 0 trong dãy chia liên tiếp
như trên là ƯCLN (a,b).
Ví dụ: Tính ước số chung lớn nhất của 91 và 287.
•
Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
287 = 91.3 + 14 (91 và 14 sẽ được dùng cho vòng lặp kế)
Theo thuật toán Euclid, ta có ƯCLN(91,287) = ƯCLN(91,14).
Suy ra bài toán trở thành tìm ƯCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia
không còn số dư như sau:
91 = 14.6 + 7 (14 và 7 sẽ được dùng cho vòng lặp kế)
14 = 7.2 (không còn số dư suy ra kết thúc, nhận 7 làm kết quả)
Thật vậy: 7 = ƯCLN(14,7) = ƯCLN(91,14) = ƯCLN(287,91)
Cuối cùng ƯCLN(287, 91) = 7
Tính BCNN nhanh nhất
CH
IN
H
P
H
Ụ
C
K
Ỳ
T
H
I H
Ọ
C S
IN
H
GI
Ỏ
I C
ẤP
H
AI
Để việc giải toán về BCNN và ƯCLN được nhanh, Nếu biết áp dụng “Thuật toán Euclid” :
Biết rằng: hai số nguyên a, b có BCNN là [ a,b] và ƯCLN là (a,b) thì
a b
a b
[ ]
(
)
[ ]
(
.
) (
)
[ ]
.
=
⇒
=
=
a b
a b
a b
a b
a b
.
,
.
,
,
,
,
,
,
Nghĩa là: Tích 2 số nguyên
a b
.
=
ƯCLN (a,b) x BCNN (a,b)
Ví dụ: có a = 12; b = 18 suy ra ƯCLN (12,18) = 6 thì:
BCNN (12,18) = (12 x 18) : 6 = 36
Nếu làm theo cách phân tich thừa số nguyên tố thì phải tính:
12 = 2
2
x 3; 18 = 2 x 3
2
suy ra BCNN (12,18) = 2
2
x 3
2
= 36
Nhận xét: Với cặp số nguyên có nhiều chữ số thì việc phân tích ra thừa số nguyên tố mất
nhiều thời gian; trong khi lấy tích số có thể bấm máy tính cầm tay khá nhanh và dễ hơn.