BT7: Bội số chung nhỏ nhất
1. Yêu cầu
Bội số chung nhỏ nhất (BSCNN) của hai số nguyên dương a và b là số nguyên nhỏ nhất chia hết cho cả a và b (tiếng Anh: least common multiple hoặc lowest common multiple (LCM) hoặc smallest common multiple). Tức là nó có thể chia cho a và b mà không để lại số dư. Nếu a hoặc b là 0, thì không tồn tại số nguyên dương chia hết cho a và b, khi đó quy ước rằng BSCNN(a, b) là 0.
Viết chương trình C# đọc hai số nguyên và gọi hàm BSCNN(a, b) nhận hai đối số nguyên và trả về Bội số chung nhỏ nhất của chúng.
Thuật toán tính BSCNN(a, b) được tính thông qua ước số chung lớn nhất, ước số chung lớn nhất (USCLN) của hai hay nhiều số nguyên là số nguyên dương lớn nhất mà các số đó cùng chia hết. Ví dụ, ước chung lớn nhất của 6 và 15 là 3 vì cả hai số đều chia hết cho số nguyên lớn nhất là 3. Trong tiếng anh, ước chung lớn nhất gọi là greatest common divisor (gcd), greatest common factor (gcf), highest common factor (hcf), greatest common measure (gcm), hay highest common divisor.
Hàm BSCNN(a, b) sẽ tính bội số chung nhỏ nhất bằng cách gọi hàm UCLN(a, b) và sử dụng công thức sau:
BSCNN(a, b) = a*b / UCLN(a, b)
2. Thuật toán
/*Chương trình chính*/
Bước 1: Start
Bước 2: Khai báo các biến integer a, b
Bước 3: Read a, b
Bước 4: Call function BSCNN(a,b)
Bước 5: Stop
/*Thuật toán cho hàm BSCNN*/
Bước 1: Start
Bước 2: return (a*b)/USCLN(a, b)
Bước 3: Stop
/*Thuật toán cho hàm USCLN*/
Bước 1: Start
Bước 2: if a==0 goto Bước 3 else goto Bước 5
Bước 3: return b
Bước 4: goto Bước 12
Bước 5: if b!=0 goto Bước 6 else goto Bước 11
Bước 6: if (a > b) goto Bước 7 else goto Bước 9
Bước 7: a = a - b;
Bước 8: goto Bước 5
Bước 9: b = b-a
Bước 10: goto Bước 5
Bước 11: return a
Bước 12: Stop
3. Lưu đồ thuật giải
