[Tìm Hiểu] Sơ đồ khối tìm ước chung lớn nhất và thuật toán tìm ƯCLN

Ước chung lớn nhất (ƯCLN) là một khái niệm cơ bản trong toán học. Nó được sử dụng trong nhiều thuật toán và ứng dụng, đặc biệt là trong mật mã học. Bài viết này giới thiệu cách vẽ sơ đồ khối tìm ước chung lớn nhất và các thuật toán tìm ƯCLN phổ biến.

Sơ đồ khối tìm ước chung lớn nhất

Sơ đồ khối là cách biểu diễn đồ họa một thuật toán, giúp hiểu rõ cấu trúc và các bước thực hiện của thuật toán.

Để vẽ sơ đồ khối tìm ƯCLN của hai số a và b, ta thực hiện các bước sau:

• Bắt đầu bằng hình vuông đầu tiên, đại diện cho bước khởi tạo giá trị ban đầu của a và b.
• Hình thứ 2 là hình thoi, kiểm tra xem a có bằng 0 không. Nếu có, trả về giá trị b và kết thúc.
• Nếu a khác 0, đi tiếp sang hình thứ 3, một hình chữ nhật, gán b cho biến tạm r.
• Hình 4 là hình thoi, kiểm tra xem b có bằng 0 không. Nếu có, trả về giá trị a và kết thúc.
• Nếu b khác 0, tính a%b và gán giá trị đó cho a. Sau đó quay lại hình thứ 2.
• Quá trình lặp lại cho đến khi một trong hai giá trị a hoặc b bằng 0. Lúc đó, giá trị còn lại chính là ƯCLN của hai số ban đầu.

Dưới đây là ví dụ về sơ đồ khối tìm ƯCLN của hai số 24 và 18:

Bước	Kiểm tra		Giá trị		Đầu ra
	a = b	a > b	a mới	b mới
1	Sai	Sai	18	6
2	Sai	Đúng	12	6
3	Sai	Đúng	6	6
4	Đúng				ƯCLN là 6

Như vậy, ta có thể dễ dàng hình dung quá trình tìm ƯCLN thông qua sơ đồ khối. Giờ ta sẽ đi sâu vào các thuật toán tìm ƯCLN phổ biến.

Các thuật toán tìm ước chung lớn nhất

Có nhiều cách để tìm ƯCLN của hai hoặc nhiều số nguyên. Dưới đây là một số thuật toán phổ biến:

Thuật toán Euclid

Đây là thuật toán cổ điển được đặt theo tên nhà toán học Hy Lạp Euclid. Thuật toán sử dụng phép chia dư liên tục cho đến khi tìm được ước chung lớn nhất.

Giải thuật:

• Nhập hai số nguyên dương a và b
• Lặp đến khi b == 0:
  • Thay b bằng a%b, a bằng b
• Trả về giá trị a

Thuật toán Euclid rất đơn giản và dễ hiểu. Tuy nhiên, nó yêu cầu nhiều phép chia dư, nên tốn khá nhiều thời gian khi số lớn. Do đó người ta đã cải tiến thuật toán này.

Thuật toán Euclid được cải tiến

Để giảm số lần chia, ta áp dụng phép toán logic như sau:

• Nếu a == b, ta có GCD(a,b) = a
• Nếu a > b, GCD(a,b) = GCD(a-b,b)
• Nếu b > a, GCD(a,b) = GCD(a, b-a)

Như vậy, thay vì chia liên tục, ta chỉ cần trừ cho đến khi tìm được GCD.

Giải thuật:

• Nhập a, b
• Nếu (a == b) trả về a
• Nếu (a > b)
  • a = a – b
  • quay lại bước 2
• Nếu (b > a)
  • b = b – a
  • quay lại bước 2
• Trả về a

Thuật toán này nhanh hơn rất nhiều so với Euclid ban đầu, nhờ giảm bớt các phép chia tốn kém.

Thuật toán tìm GCD bằng phép AND bit

Ta có tính chất: GCD(a,b) == GCD(b, a mod b)

Với phép AND bit, ta có: a mod b = a & (b-1)

Do đó, thay vì dùng phép chia dư thông thường, ta có thể dùng phép & bit để tìm dư nhanh hơn.

Giải thuật:

• Nhập a, b
• Nếu (b == 0) trả về a
• a = a & (b-1)
• b = tạm
• quay lại bước 2

Thuật toán này giúp tìm GCD rất nhanh với số lớn nhờ tận dụng phép toán bit. Tuy nhiên nó chỉ áp dụng được cho kiểu số nguyên.

Thuật toán Stein

Thuật toán Stein sử dụng công thức sau để tìm GCD:

GCD(a,b) = GCD(b,a mod b) 
        = GCD(a mod b, b mod (a mod b))

Như vậy, thay vì phải tính a%b nhiều lần, ta chỉ tính một lần duy nhất rồi dùng luôn kết quả đó. Điều này giúp giảm thời gian tính toán đáng kể.

Giải thuật:

• Nhập a, b
• Nếu (b == 0) trả về a
• Tạm = a % b
• a = b
• b = Tạm
• Quay lại bước 2

Thuật toán Stein nhanh hơn Euclid cải tiến một chút, nhờ tránh tính lại phép chia dư nhiều lần.

Thuật toán tìm ƯCLN trong Python

Trong Python, ta có thể tìm GCD của hai số rất đơn giản bằng hàm math.gcd():

import math

a = 24
b = 18

print(math.gcd(a, b))

Kết quả:

6

Như vậy, thay vì tự code các thuật toán phức tạp, ta có thể dùng luôn hàm có sẵn trong thư viện chuẩn của Python. Điều này giúp giảm thiểu sai sót và tiết kiệm thời gian.

Tóm tắt

• Sơ đồ khối giúp minh họa trực quan quá trình tìm ước chung lớn nhất của hai số.
• Có nhiều thuật toán khác nhau để tìm GCD, từ đơn giản đến phức tạp hơn như Euclid, Euclid cải tiến, Stein,… mỗi cách đều có ưu nhược điểm riêng.
• Trong thực tế, nếu có sẵn thư viện, ta nên sử dụng luôn hàm có sẵn để đơn giản hóa vấn đề. Ví dụ như hàm math.gcd() trong Python.
• Hi vọng bài viết này giúp bạn nắm được cách vẽ sơ đồ khối và ý tưởng của các thuật toán tìm ước chung lớn nhất. Đừng quên ghé thăm website của chúng tôi để cập nhật nhiều kiến thức hữu ích hơn về lập trình và khoa học máy tính nhé.