Thuật toán tìm UCLN của 2 số

 THUẬT TOÁN TÌM ƯỚC CHUNG LỚN NHẤT CỦA 2 SỐ A, B

1. Kết quả sau bài học này, học sinh:

• Trình bày được ƯCLN là gì; biết định nghĩa và thuật toán Euclid.
• Giải thích được vì sao thuật toán Euclid đúng và dừng.
• Áp dụng thuật toán để tìm ƯCLN của hai số bất kỳ.
• So sánh thuật toán Euclid với phương pháp phép trừ dần
• Viết lại thuật toán dưới dạng mô hình, sơ đồ, hoặc chương trình.
• Nhận xét tính hiệu quả, tối ưu của thuật toán Euclid trong bài toán thực tế.

2. Kiến thức về ước chung lớn nhất 2 số

• Euclid (Ê-clít) là một nhà toán học nổi tiếng người Hy Lạp cổ đại.
• Ông được xem là “cha đẻ của hình học”, sống khoảng năm 300 trước Công nguyên.
• Ông là tác giả của bộ sách “Cơ sở” (Elements) – một trong những tác phẩm toán học có ảnh hưởng lớn nhất trong lịch sử.

2.1 Thuật toán Euclid là gì?

• Là một phương pháp đơn giản và hiệu quả để tìm Ước chung lớn nhất (ƯCLN) của hai số nguyên dương.

2.2 Thuật toán dựa trên quy tắc:

• Nếu a chia cho b dư r, thì ƯCLN(a, b) = ƯCLN(b, r)
• (vì các ước chung của a và b cũng là ước của r)
• Lặp lại quá trình chia lấy dư cho đến khi phần dư bằng 0, khi đó ƯCLN chính là số chia cuối cùng.

2.3 Mô hình lượt đồ thuật toán

Lượt đồ theo phương pháp trừ

Lượt đồ thuật toán tìm UCLN 2 số theo Euclid

2.4 Giải thích thuật toán bằng lời dễ hiểu:

• Bước 1: Lấy 2 số nguyên dương a và b (a ≥ b).
• Bước 2: Chia a cho b, lấy phần dư r (r = a % b).
• Bước 3: Nếu r = 0, thì ƯCLN chính là b.
• Bước 4: Nếu r ≠ 0, gán lại:
• a = b
• b = r
• và lặp lại bước 2.
• Lặp lại quá trình cho đến khi dư bằng 0.

3. Hướng dẫn sử dụng mô hình

📘 Hướng dẫn sử dụng mô hình Euclid tìm Ước chung lớn nhất

✅ Bước 1: Nhập dữ liệu

• Tại mục "Số thứ nhất (a)", nhập số nguyên dương thứ nhất.
• Tại mục "Số thứ hai (b)", nhập số nguyên dương thứ hai.
• Ví dụ:
• Số thứ nhất (a): 48
• Số thứ hai (b): 18

🚀 Bước 2: Nhấn nút "Bắt đầu tính toán"

• Mô hình sẽ hiển thị từng bước tính ƯCLN theo thuật toán Euclid.
• Các phép chia – lấy dư sẽ được hiển thị trong mục “Trạng thái hiện tại”.

🔁 Bước 3: Quan sát quá trình lặp

• Mỗi vòng lặp sẽ cho biết:
• Số chia và số bị chia
• Số dư (nếu còn)
• Khi nào dừng lại

Kết quả là số Ước chung lớn nhất (ƯCLN) của hai số đã nhập.

🔄 Bước 4: Đặt lại dữ liệu

• Nhấn nút "Đặt lại" để thử với hai số mới.

🧮 Mô phỏng thuật toán GCD

Tìm ước chung lớn nhất bằng thuật toán Euclid

📝 Nhập dữ liệu

Số thứ nhất (a):

Số thứ hai (b):

⚙️ Trạng thái hiện tại

Bước hiện tại:

🎉 Kết quả cuối cùng

📋 Nhật ký các bước thực hiện

Nhập hai số và nhấn "Bắt đầu tính toán" để xem quá trình thực hiện thuật toán

💡 Giải thích thuật toán Euclid

Nguyên lý: GCD(a, b) = GCD(b, a mod b). Thuật toán lặp lại cho đến khi một trong hai số bằng 0.

Các bước:

1. Nếu b = 0, thì GCD(a, b) = a

2. Nếu b ≠ 0, thì tính a mod b (phần dư khi chia a cho b)

3. Gán a = b, b = a mod b

4. Lặp lại từ bước 1

Ví dụ: GCD(48, 18) = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6