Gửi bn:

-Xác định bài toán

+In: 2 số nguyen dương a và b

+Out: ucln(a,b);

-Xây dựng thuật toán

+Bước 1: nhập 2 số nguyen dương a và b

+Bước 2: nếu a>b thì a:=a-b

+Bước 3: ngược lại thì b:=b-a

+Bước 4: Nếu a<>b thì quay lại bước 2

+Bước 5: ucln:=a;

+Bước 6: Xuất ucln

+Bước 7: Kết thúc

chúc bn học tốt

XIn hay nhất

ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố. Nhưng có 1 phương pháp tối ưu nhất là sử dụng thuật toán Euclid dựa trên dãy liên tiếp các phép chia có dư.

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 & 14 sẽ được dùng cho vòng lặp kế)

Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(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 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)
Cuối cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).