Thuật toán tìm ƯCLN – BCNN là thuật toán số học hết sức cơ bản mà bất kì một lập trình viên nào cũng phải nắm vững, các bạn học Pascal hay C cũng thế thôi, trong bài viết này mình sẽ đưa ra một số bài tập liên quan đến ƯCLN – BCNN để giúp các bạn luyện tập.
Bài tập 1: Viết chương trình nhập vào hai số nguyên a, b (từ file hay bàn phím) sau đó tìm ƯCLN (a,b)
Đây là bài tập cơ bản bạn nào cũng cần nắm vững thuật toán tìm ƯCLN (a,b). Sau đây là code mẫu bằng Pascal để các bạn tham khảo
Các bạn chú ý phần đầu chương trình có cặp lệnh a:=abs(a); b:=abs(b) để thay thế a, b bằng giá trị tuyệt đối của nó, nếu đề bài cho a, b là số tự nhiên thì có thể bỏ cặp lệnh này đi.
Bài tập 2: Viết chương trình nhập vào hai số nguyên a, b (từ file hay bàn phím) sau đó tìm BCNN (a,b)
Có nhiều thuật toán tìm BCNN của hai số sau đây mình dưa ra thuật toán đơn giản nhất để các bạn tham khảo
Ý tưởng của thuật toán như sau: Làm dương hai số, lấy số lớn nhất trong hai số đem nhân lần lượt với 1, 2, 3, … rồi chia cho số nhỏ, khi chia hết thì dừng lại tích đó chính là BCNN.
Đây là thuật toán đơn giản giống như cách tìm BCNN của các em học sinh lớp 6. Ngoài ra các bạn cũng có thể tìm dựa vào kiến thức a.b = UCLN(a,b).BCNN(a,b) để tìm UCLN thông qua BCNN.
Bài tập 3: Viết chương trình tìm ƯCLN (a,b,c) hay BCNN (a,b,c)
Hướng dẫn: Bạn viết chương trình con tìm ƯCLN (a,b) sau đó cho tìm ƯCLN (ƯCLN (a,b) ,c)
Hoàn toàn tương tự với BCNN (a,b,c)
Bài tập 4: Viết chương trình kiểm tra xem hai số a, b có nguyên tố cùng nhau hay không?
Gợi ý: bạn hãy nhớ lại “Hai số nguyên tố cùng nhau là hai số có ước chung lớn nhất bằng 1” vậy bạn có thể dùng ngay chương trình con tìm ƯCLN (a,b) để giải quyết bài toán rồi nhé.
Bài tập 5: Cho một số nguyên a và một dãy gồm n số nguyên, viết chương trình loại bỏ hết các số nguyên tố cùng nhau với a trong dãy.
Dữ liệu vào: File input.inp có hai dòng
Dòng 1: chứa số a
Dòng 2: chứa n số nguyên
Dữ liệu ra: File output.out có một dòng chứa dãy số đã loại bỏ.
Gợi ý: Để giải quyết bài toán bạn hãy sử dụng chương trình con tìm UCLN của hai số, sau đó dùng kỹ thuật đánh dấu mảng để đánh dấu những số mà nếu kết hợp với a thì có UCLN bằng 1.
Bài tập 6. Cũng với dữ kiện như bài 5 nhưng có thể hỏi khác đi chẳng hạn đếm xem có bao nhiêu số nguyên tố cùng nhau với a trong dãy số.
Với cách hỏi này thì một lần nữa ta lại thấy tầm quan trong của thuật toán cộng dồn vận dụng để đếm đúng không nào
Các bạn nào còn bài tập nào hay về chủ để này hãy chia sẻ để các bạn cùng học hỏi nào!
