USCLN của a và b

[hungchng]

Các em đã học cách tìm USCLN của 2 số a,b trong chương trình toán nhưng chuyển qua Tin, các em chưa chuyển được nhưng tính chất của USCLN là hai số a,b phải chia hết cho USCLN
Khi chuyển qua học cấu trúc Lặp ở ngôn ngữ lập trình Pascal các em mô tả thuật Toán như sau

B1: tìm số nhỏ nhất trong 2 số a,b {lý do nếu số lớn chia hết cho số nhỏ thì số nhỏ là USCLN}
B2: i <-- 1;
B3: Nếu a và b chia hết cho i thì USCLN <-- i
B4: i <-- i+1; Nếu i<= Min trở lại B3
B5: In ra USCLN
B6: Kết thúc

Program USCLN;
uses crt;
var a,b,min,US,i:word;
begin
clrscr;
write('Moi nhap so a ');readln(a);
write('Moi nhap so b ');readln(b);
if a>b then min:=b else min:=a;
i:=1;
repeat
if (a mod i = 0) and (b mod i = 0)
then US:=i;
i:=i+1;
until i>min;
writeln('USCLN la ',US:4);
readln
end.

Thuật toán khác. Mời các bạn tham khảo: Gọi u là USCLN của a và b.

- Nhận thấy u không thế lớn hơn a và b.
- u phải là USC của a và b và là lớn nhất.

Vì thế mình đưa ra ý tưởng là u là ước chung đầu tiên của a và b xét từ trên xuống. Khi đó u chính là USCLN của a và b.

1. u <- a
2. Nếu u là USC của a và b thì chuyển đến bước 4.
3. u <- u - 1. Lặp lại bước 2.
4. Đưa ra màn hình giá trị của u

Chương trình như sau:
Mã lệnh:
Program USCLN;
Var a, b, u: Word;
Begin
Write("Nhap a, b: ");
Readln(a, b);
u := a;
While (a mod u <> 0) or (b mod u <> 0) do
u := u - 1;
Writeln("USCLN của a va b la: ", u);
End.


Nhận thấy nếu a lớn hơn b đáng kể thì sẽ bị thừa rất nhiều số bước lặp vì vậy sẽ cải tiến lần 1 bằng cách chọn giá trị nhỏ nhất của a và b.

1. u <- a
2. Nếu b < u thì u <- b
3. Nếu u là USC của a và b thì chuyển đến bước 5.
4. u <- u - 1. Lặp lại bước 3.
5. Đưa ra màn hình giá trị của u

Chương trình như sau:
Mã lệnh:
Program USCLN;
Var a, b, u: Word;
Begin
Write("Nhap a, b: ");
Readln(a, b);
u := a;
If (b < u) then
u := b;
While (a mod u <> 0) or (b mod u <> 0) do
u := u - 1;
Writeln("USCLN của a va b la: ", u);
End.

Khi dạy học sinh đến vòng lặp For chưa học While hay Repeat các em cũng có ý tưởng làm bài này với câu lệnh For.

Var a, b, i, uc, min :Word;
Begin
Write('Nhap 2 so:');Readln(a,b);
If a< b Then min:=a else min:=b;
For i:=1 to min do
If (a mod i =0) and (b mod i = 0) then uc:=i;
Write(' UCLN cua ', a,' va', b,' la', uc);
End.

Có thể dùng thuật toán trừ để giảng bài toán này cho hs vì thấy nó khá đơn giản và dễ hiểu.

Mã lệnh:
program USCLN;
var
gcd, a, b: word;
begin
write('nhap a, b: ');
readln(a, b);
while a <> b do
if a > b then a := a - b else b := b - a;
gcd := a; {hoặc b}
writeln('USCLN:',gcd);
end.
Đoạn code này được viết ngắn gọn nhằm mô tả thuật toán là chính, thuật toán kết thúc khi a = b, khi đó ước số chung lớn nhất có thể là a hoặc b. Nhược điểm của thuật toán này là nếu a, b chênh lệch lớn thì số lần lặp sẽ nhiều.