cách tìm bội chung nhỏ nhất

Tìm bội cộng đồng nhỏ nhất của 2 số – Chương trình lần BCNN của 2 số là một trong bài bác luyện cơ bạn dạng chung chúng ta SV tập luyện trí tuệ thiết kế. Trong nội dung bài viết này, Nguyễn Văn Hiếu tiếp tục nằm trong chúng ta đi tìm kiếm những cách thức không giống nhau nhằm giải bài bác luyện lần bội cộng đồng nhỏ nhất của 2 số vẹn toàn dương. Mỗi thủ tục đều sẽ có được ý tưởng phát minh rõ nét, cơ hội xây dựng và code lần bcnn minh họa Theo phong cách bại liệt.

Bạn đang xem: cách tìm bội chung nhỏ nhất

Theo Wikipedia,

Trong số học tập, bội số cộng đồng nhỏ nhất (hay còn gọi tắt là bội cộng đồng nhỏ nhất, viết lách 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ố vẹn toàn a và b là số vẹn toàn dương nhỏ nhất phân chia không còn cho tất cả a và b.[1] Tức là nó hoàn toàn có thể phân chia mang đến a và b nhưng mà ko nhằm lại số dư. Nếu a hoặc b là 0, thì ko tồn bên trên số vẹn toàn dương phân chia không còn mang đến a và b, Lúc bại liệt quy ước rằng LCM(a, b) là 0.

Định nghĩa bên trên nhiều lúc được tổng quát mắng hoá mang đến rộng lớn nhị số vẹn toàn dương: Bội cộng đồng nhỏ nhất của a1,…, an là số vẹn toàn dương nhỏ nhất là bội số của a1,…, an.

2. Các thuật toán lần bội cộng đồng nhỏ nhất của 2 số

Ta đem một vài phán xét như sau: Theo khái niệm, BCNN của 2 số a và là số nhỏ nhất phân chia không còn cho tất cả 2 số a và b. Như vậy, Nếu gọi lcm = BCNN(a, b); Khi bại liệt, tớ hoàn toàn có thể biết chắc chắn là rằng `max(a, b) <= lcm <= a*b`.

Nắm rõ rệt đặc thù này, tớ hoàn toàn có thể lên đường vô một vài thuật toán lần BCNN như sau:

C1. Lặp tăng dần dần cho đến Lúc tìm kiếm ra BCNN

Cách này ý tưởng phát minh khá là đơn giản và giản dị, tớ chỉ việc tổ chức lặp kể từ nhỏ cho tới rộng lớn những số trong khúc kể từ [max(a, b),a*b](bao bao gồm cả hai đầu mút). Số thứ nhất phân chia không còn cho tất cả a và b được xem là BCNN của a và b.

Đánh giá: Cách này vô tình huống xấu xí nhất tiếp tục cần thiết a*b – max(a, b) phiên lặp. Vẫn với ý tưởng phát minh này tuy nhiên sẽ tiến hành tối ưu ở C2

#include<stdio.h> #include <algorithm> int main(){ int a = 5, b = 7, lcm; int maxV = a*b; for(int i = std::max(a, b); i <= maxV; i++){ if(i % a == 0 && i % b == 0){ lcm = i; break; } } printf("BCNN(%d, %d) = %d", a, b, lcm); }

Chạy test coi sao:

BCNN(5, 7) = 35

C2. Tối ưu lặp của cơ hội 1

BCNN của 2 số a và b cần phân chia không còn cho tất cả 2 số này. Do bại liệt, tớ hoàn toàn có thể chỉ việc duyệt qua loa những số phân chia không còn cho một số(hoặc a, hoặc b). Nhưng nhằm tối ưu, các bạn hãy duyệt qua loa những số phân chia không còn mang đến max(a, b).

Ví dụ: a = 5, b = 7. Vậy những số tất cả chúng ta nên duyệt qua loa những số phân chia không còn mang đến 7 là 7, 14, 21, 28, 35. Như vậy, tất cả chúng ta hạn chế được thật nhiều số phiên lặp rồi.

Xem thêm: phân tích bài chị em thúy kiều

Đánh giá: Cách này số phiên lặp vô tình huống xấu xí nhất là `a*b / max(a, b)`.

#include<stdio.h> #include <algorithm> int main(){ int a = 5, b = 7, lcm; int maxV = a*b; int step = std::max(a, b); for(int i = step; i <= maxV; i+= step){ if(i % a == 0 && i % b == 0){ lcm = i; break; } } printf("BCNN(%d, %d) = %d", a, b, lcm); }

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

BCNN(5, 7) = 35

C3. Phân tích quá số vẹn toàn tố

Sử dụng cơ hội lần bcnn vẫn học tập vô toán cấp cho 2:

• Bước 1: Phân tích từng số rời khỏi quá số yếu tố.
• Bước 2: Chọn rời khỏi những quá số yếu tố cộng đồng và riêng rẽ.
• Bước 3: Lập tích những quá số vẫn lựa chọn, từng quá số lấy với số nón lớn số 1 của chính nó. Tích này là BCNN cần thiết lần.

Cách này bản thân review chỉ thuận tiện mang đến đo lường trong giấy, việc triển khai code phức tạp rộng lớn và vận tốc cũng không thực sự chất lượng tốt.

Lưu ý: Để code cụt gọn gàng nhất, bản thân tiếp tục dùng những cấu hình STL của C++ và tác dụng for tự động của C++11

#include<iostream> #include <map> #include <set> #include <math.h> using namespace std; int main(){ int a = 5, b = 7, lcm; map<int, int> ma mãnh, mb; set<int> s; for(int i = 2; a < i; ++i){ while(a % i == 0){ ma[i]++; a /= i; s.insert(i); } } if(a > 1) { ma[a]++; s.insert(a); } for(int i = 2; b < i; ++i){ while(b % i == 0){ mb[i]++; b /= i; s.insert(i); } } if(b > 1) { mb[b]++; s.insert(b); } lcm = 1; for(auto it : s){ lcm *= pow(it, max(ma[it], mb[it])); } printf("BCNN(%d, %d) = %d", a, b, lcm); }

Cách này những bạn cũng có thể tìm hiểu thêm và bạn cũng có thể tối ưu tăng. Mình sẽ không còn lý giải thâm thúy vì thế thực tiễn, thuật toán lần bcnn này xây dựng khá rườm thẩm tra và ko tối ưu.

C4. Tìm BCNN của 2 số phụ thuộc vào UCLN

Dưới đó là sơ vật khối lần bội cộng đồng nhỏ nhất của 2 số:

Khi bại liệt, tớ đem công thức: `BCNN(a, b) = a*b / UCLN(a,b)`

Các bạn cũng có thể coi những thuật toán lần UCLN của 2 số, bên dưới đó là code tìm hiểu thêm lần bội cộng đồng nhỏ nhất theo đuổi UCLN tương tự sơ vật khối phía trên:

#include<iostream> #include <map> #include <set> #include <math.h> using namespace std; int gcd(int a, int b){ // N?u a = 0 => ucln(a,b) = b // N?u b = 0 => ucln(a,b) = a if (a == 0 || b == 0){ return a + b; } while (a != b){ if (a > b){ a -= b; // a = a - b }else{ b -= a; } } return a; // return a or b, b?i vì thế thời điểm hiện nay a và b b?ng nhau } int main(){ int a = 5, b = 7; int lcm = a * b / gcd(a, b); printf("BCNN(%d, %d) = %d", a, b, lcm); }

C5. Sử dụng hàm lcm đã có sẵn trước ở C++17

Hàm này chỉ mất ở C++17, và cơ hội dùng vô cùng đơn giản:

Xem thêm: mẫu hợp đồng thuê nhà ở đơn giản nhất

#include<stdio.h> #include <iostream> #include <algorithm> using namespace std; int main(){ int a = 5, b = 7; int ans = lcm(a, b); printf("BCNN(%d, %d) = %d", a, b, ans); }