THUẬT TOÁN BỘI CHUNG NHỎ NHẤT

     
Thuật toán tra cứu bội chung nhỏ tuổi nhất

Tìm bội chung bé dại nhất của 2 số công tác tìm BCNN của 2 số là 1 trong bài tập cơ bản giúp chúng ta sinh viên rèn luyện tư duy lập trình. Trong bài viết này, Nguyễn Văn Hiếu sẽ cùng chúng ta đi kiếm tìm các phương thức khác nhau nhằm giải bài bác tập search bội chung nhỏ nhất của 2 số nguyên dương. Mỗi cách làm đều sẽ có ý tưởng rõ ràng, cách thực thi và code tra cứu bcnn minh họa theo phong cách đó.

Bạn đang xem: Thuật toán bội chung nhỏ nhất

*

Liên quan: thuật toán kiếm tìm bội chung nhỏ nhất

1. Bội chung nhỏ dại nhất là gì?

Theo Wikipedia,

Trong số học, bội số chung bé dại nhất (hay còn được gọi tắt là bội chung nhỏ dại nhất, viết tắt là BCNN, giờ đồng hồ Anh: least common multiple hoặc lowest common multiple (LCM) hoặc smallest common multiple) của nhị số nguyên a cùng b là số nguyên dương nhỏ nhất phân chia hết cho cả a và b.<1> có nghĩa là nó có thể chia mang đến a với b nhưng không vướng lại số dư. Nếu như a hoặc b là 0, thì ko tồn tại số nguyên dương phân chia hết cho a và b, lúc đó quy mong rằng LCM(a, b) là 0.

Định nghĩa trên nhiều lúc được tổng quát hoá đến hơn nhị số nguyên dương: Bội chung nhỏ tuổi nhất của a1,…, an là số nguyên dương bé dại nhất là bội số của a1,…, an.

2. Các thuật toán tìm bội chung nhỏ dại nhất của 2 số

Ta có một số trong những nhận xét như sau: Theo định nghĩa, BCNN của 2 số a và là số nhỏ nhất chia hết cho cả 2 số a cùng b. Như vậy, Nếu hotline lcm = BCNN(a, b); lúc đó, ta có thể biết chắc hẳn rằng rằng max(a, b) C1. Lặp tăng dần tính đến khi tìm kiếm được BCNN

Cách này phát minh khá là đối chọi giản, ta chỉ việc tiến hành lặp từ nhỏ tới lớn những số trong khúc từ (bao gồm cả hai đầu mút). Số trước tiên chia hết cho tất cả a cùng b sẽ là BCNN của a cùng b.

Đánh giá: biện pháp này vào trường phù hợp xấu duy nhất sẽ đề xuất a*b max(a, b) lần lặp. Vẫn với ý tưởng phát minh này nhưng sẽ được tối ưu nghỉ ngơi C2

Chạy demo xem sao:

C2. Buổi tối ưu lặp của giải pháp 1

BCNN của 2 số a với b phải chia hết cho cả 2 số này. Bởi đó, ta có thể chỉ việc duyệt qua những số phân chia hết cho một số(hoặc a, hoặc b). Tuy vậy để tối ưu, các bạn hãy duyệt qua những số phân chia hết mang đến max(a, b).

Xem thêm: Đại Hội Ix Của Đảng (Tháng 4, Đại Hội Đảng Cộng Sản Việt Nam Lần Thứ Ix

Ví dụ: a = 5, b = 7. Vậy các số chúng ta nên chăm bẵm qua các số phân chia hết mang đến 7 là 7, 14, 21, 28, 35. Như vậy, bọn họ giảm được không ít số lần lặp rồi.

Đánh giá: bí quyết này số lần lặp trong trường hợp xấu duy nhất là a*b / max(a, b).

Chạy test chương trình:

C3. So với thừa số nguyên tố

Sử dụng phương pháp tìm bcnn sẽ học vào toán cấp cho 2:

Bước 1: so với mỗi số ra quá số nguyên tố.Bước 2: lựa chọn ra những thừa số nguyên tố tầm thường và riêng.Bước 3: Lập tích những thừa số vẫn chọn, từng thừa số lấy với số mũ lớn nhất của nó. Tích chính là BCNN cần tìm.

Cách này mình reviews chỉ thuận tiện cho giám sát và đo lường trên giấy, việc triển khai code phức tạp hơn và tốc độ cũng không thực sự tốt.

Xem thêm: Hướng Dẫn Cách Ghép Các Video Lại Với Nhau Trên Điện Thoại Iphone

Lưu ý: Để code gọn ghẽ nhất, bản thân sẽ áp dụng các kết cấu STL của C++ và anh tài for tự động của C++11

Cách này các bạn cũng có thể tham khảo và bạn cũng có thể tối ưu thêm. Mình vẫn không phân tích và lý giải sâu vị thực tế, thuật toán kiếm tìm bcnn này xúc tiến khá lướt thướt và không tối ưu.

C4. Tra cứu BCNN của 2 số phụ thuộc vào UCLN

Dưới đấy là sơ trang bị khối kiếm tìm bội chung nhỏ tuổi nhất của 2 số:

*
Sơ vật khối tìm kiếm BCNN của 2 số

Khi đó, ta bao gồm công thức: BCNN(a, b) = a*b / UCLN(a,b)

Các chúng ta cũng có thể xem các thuật toán tra cứu UCLN của 2 số, dưới đó là code xem thêm tìm bội chung nhỏ nhất theo UCLN tương tự sơ đồ khối phía trên:

C5. Thực hiện hàm lcm có sẵn sinh hoạt C++17

Hàm này chỉ tất cả ở C++17, và cách thực hiện rất đối chọi giản:


Các nội dung bài viết trong khóa họcBài trước: bài xích 24. Tra cứu số đảo ngược vào C/C++Bài sau: bài 26. Thư viện math.h vào C