Kiến thức

Dùng hàm đệ quy và thuật toán Euclid để tìm ước chung lớn nhất (Using recursive function and Euclidean algorithm to find GCD of 2 numbers) – BunnyBear

Dùng hàm đệ quy và thuật toán Euclid để tìm ước chung lớn nhất (Using recursive function and Euclidean algorithm to find GCD of 2 numbers)

https://en.wikipedia.org/wiki/Euclidean_algorithm#Procedure

Các bạn nên đọc bài viết về hàm đệ quy trước khi đọc bài này. Tuy nhiên nếu chỉ cần hiều về thuật toán của Euclid thì đọc tiếp cũng không sao. Bài viết gồm 2 phần.

  • Phần 1: Giải thích thuật toán.
  • Phần 2: Xây dựng hàm đệ quy

Phần 1: Thuật toán tìm ước chung lớn nhất (GCD: Greatest Common Divisor) của Euclid
Chúng ta đều biết cách tìm ước chung lớn nhất (GCD) của 2 số bằng phương pháp phân tích thừa số.

 Vd: GCD(10, 45)= ? 10 = 2 * 5 45 = 9 * 5 => GCD(10, 45) = 5 
 GCD(1701, 3768) = ? 

gcd_1701_3768

Thuật toán của Euclid được sử dụng cách đây 300 năm trước công nguyên bởi nhà toán học Euclid và có thể còn được dùng trước cả thời của Euclid nữa.

Trước khi giới thiệu thuật toán của Euclid, chúng ta cần phải làm quen với phép chia lấy phần dư ( ký hiệu % )

 vd: 7 % 4 = 3 vì 7 = 4 * 1 + 3 23 % 10 = 3 vì 23 = 10 * 2 + 3 30 % 5 = 0 vì 30 = 5 * 6 + 0 3 % 4 = 3 vì 3 = 4 * 0 + 3 

Euclid bảo chúng ta rằng:
Với 2 số A và B, A > B.
Lấy A % B = R. Nếu R != 0 (A là số bị chia. B là số chia. R là số dư)
Lấy B % R = Q. Nếu Q != 0 (B là số bị chia. R là số chia. Q là số dư)
Lấy R % Q = T. Nếu T = 0 (R là số bị chia. Q là số chia. T là số dư)
Thì Q là GCD

Tóm lại sau khi lấy số lớn % số bé, chúng ta liên tiếp lấy số chia % số dư (của phép tính trước). Nếu kết quả bằng 0 thì số chia trong phép tính này chính là ước chung lớn nhất. Nghe có chút ‘loạn loạn’. Hãy xem một vài ví dụ sẽ dễ hiểu hơn


GCD(10, 45) = ?
45 % 10 = 5 (45 là số bị chia. 10 là số chia. 5 là số dư)
10 % 5 = 0 (10 là số chia của phép tính trước. 5 là là số dư của phép tính trước)
-> GCD(10, 45) = 5

GCD(1701, 3768) = ?
3768 %  1701 = 366
1701 %  366   = 237
366   %  237   = 129
237   %  129   = 108
129   %  108   = 21
108   %  21     = 3
21     %  3       = 0

-> GCD(1701, 3768) = 3

Vậy thuật toán này hoạt động như thế nào ???

Có thể minh họa thuật toán của Euclid bằng việc lát gạch sàn nhà. Hãy tưởng tượng bạn là một người thợ xây và khách hàng yêu cầu bạn lát sàn nhà của họ chỉ dùng gạch hình vuông, kích thước thế nào cũng được nhưng phải là hình vuông, không dùng hình chữ nhật, hình thang, hình tam giác v.v…

square

Đây là đơn hàng số 1:
Kích thước sàn nhà là 10 * 50 (m)
Đơn hàng này thì dễ rồi bạn chỉ việc lấy 50 / 10 = 5 viên gạch 10 * 10(m)
1050
Đơn hàng số 2:
Kích thước sàn nhà 35 * 15 (m)
01
Dĩ nhiên nếu bạn lấy kích thước mỗi viên gạch là 1 * 1 (m) thì sẽ giải quyết được vấn đề ngay không phải nghĩ tuy nhiên như thế sẽ phải lát 35 * 15 = 525 viên gạch. Mà tôi thì quá lười để lát nhiều gạch như vậy. Dù sao thì yêu cầu là dùng gạch hình vuông kích thước nào cũng được. Vậy nên tôi sẽ tìm kích thước của viên gạch hình vuông sao cho số lần lát gạch ít nhất.
And tadaaa GCD come to rescue !!!
Đầu tiên lấy cạnh lớn chia cho cạnh nhỏ
02
ta được 2 “viên gạch” lớn 15 * 15 (m) và một phần thừa ra 15 * 5(m). Phần thừa này chính là kết quả của phép chia lấy phần dư 35 % 15 = 5. Giá mà cạnh lớn là 30m thì chúng ta đã xong việc (30 % 15 = 0) chỉ cần 2 viên 15 x 15.

Ta lại tiếp tục làm việc với phần dư này. Lại lấy cạnh lớn chia cạnh nhỏ
03
Lần này chúng ta gặp may mắn vì không còn dư chút nào 15/5 = 3 dư 0 ( 15 % 5 = 0). Vậy chúng ta có thể lấy viên gạch 5 * 5 làm template cho sàn nhà và chỉ phải lát 21 lần thay vì 525 lần!!!
04

Và kết thúc việc lát gạch. 5 cũng chính là ước chung lớn nhất(GCD) của 35 và 15

Bây giờ chúng ta đã hiểu thuật toán của Euclid hoạt động như thế nào. Hãy viết vài dòng code để không phải vẽ hình mỗi khi có khách mới thuê lát sàn nhà nữa.
Phần 2: Hàm đệ quy

 def gcd(a, b): """Returns the greatest common divisor of a and b using recursion. >>> gcd(34, 19) 1 >>> gcd(39, 91) 13 >>> gcd(20, 30) 10 >>> gcd(40, 40) 40 """ if a < b: a, b = b, a def find_gcd(a, b): if a == b or a % b == 0: return b return find_gcd(b, a % b) return find_gcd(a, b) 

[to be continue]

Posted on

August 18, 2018August 18, 2018

Bunny Bear

Categories

Computer Science

,

Recursion

Tags

Recursion

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button