Video Output của bài toán tìm bội số chung nhỏ nhất của 2 số nguyên dương a và b là ?
Kinh Nghiệm về Output của bài toán tìm bội số chung nhỏ nhất của 2 số nguyên dương a và b là 2022
Bùi Xuân Trường đang tìm kiếm từ khóa Output của bài toán tìm bội số chung nhỏ nhất của 2 số nguyên dương a và b là được Update vào lúc : 2022-05-07 17:39:06 . Với phương châm chia sẻ Thủ Thuật về trong nội dung bài viết một cách Chi Tiết Mới Nhất. Nếu sau khi tham khảo nội dung bài viết vẫn ko hiểu thì hoàn toàn có thể lại Comment ở cuối bài để Admin lý giải và hướng dẫn lại nha.
Nội dung chính
- Example2 Input: 2 20 Output: 14 Example3 Input: 3 5 Output: -1 Giải thích ví dụ: - Ở ví dụ thứ nhất: Chỉ có cặp (2, 10) thỏa mãn ƯCLN(2,10) = 2, BCNN(2,10) = 10. Nên tổng là 12. - Ở ví dụ thứ hai: Có hai cặp (2, 20) và (4, 10) thỏa mãn, tổng nhỏ nhất là 14. - Ở ví dụ thứ ba: Không tìm được cặp nào thỏa mãn ƯCLN là 3 và BCNN là 5. 1. Bội chung nhỏ nhất là gì?2. Các thuật toán tìm bội chung nhỏ nhất của 2 sốC1. Lặp tăng dần cho tới khi tìm được BCNNC2. Tối ưu lặp của cách 1C3. Phân tích thừa số nguyên tốC4. Tìm BCNN của 2 số nhờ vào UCLNC5. Sử dụng hàm lcm có sẵn ở C++17Video liên quan
Với hai số nguyên dương A, B cho trước. Ta thuận tiện và đơn giản tìm được ước chung lớn số 1 G và bội chung nhỏ nhất L của hai số A và B.
Bây giờ tất cả chúng ta hãy xét bài toán ngược của bài toán trên:
“Cho biết trước ước chung lớn số 1 G và bội chung nhỏ nhất L của hai số nguyên dương A và B.
Rõ ràng, sẽ có rất nhiều cặp (A, B) nguyên dương có ước chung lớn số 1 là G và bội chung nhỏ nhất là L, tuy nhiên cũng luôn có thể có trường hợp tất cả chúng ta không thể tìm được giá trị A, B thỏa mãn. Hãy xác định giá trị nhỏ nhất của tổng A + B, hoặc đưa ra -1 nếu không tìm được cặp (A, B)”.
Input
- Hai số nguyên dương G và L (1 ≤ G ≤ L ≤ 109).
Output
- Số nguyên dương là tổng nhỏ nhất hoàn toàn có thể. Trong trường hợp không tìm được hai số A và B thì đưa ra kết quả là -1.
Example1
Input: 2 10 Output: 12Example2 Input: 2 20 Output: 14
Example3 Input: 3 5 Output: -1 Giải thích ví dụ: - Ở ví dụ thứ nhất: Chỉ có cặp (2, 10) thỏa mãn ƯCLN(2,10) = 2, BCNN(2,10) = 10. Nên tổng là 12. - Ở ví dụ thứ hai: Có hai cặp (2, 20) và (4, 10) thỏa mãn, tổng nhỏ nhất là 14. - Ở ví dụ thứ ba: Không tìm được cặp nào thỏa mãn ƯCLN là 3 và BCNN là 5.
- lý thuyết trắc nghiệm hỏi đáp bài tập sgk
xác định bài toán và xây dựng thuật toán
1. tìm ước chung lớn số 1 của hai số a, b
2. tìm bội chung nhỏ nhất của 2 số nguyên dương a,b
Các thắc mắc tương tự
giúpmìnhviết thuật toán tìm bội số chung nhỏ nhất của 2 số A và B , biết A và B nguyên dương . Mình cảm ơn ạ
This entry is part 23 of 69 in the series Học C Không Khó
84 / 100
Tìm bội chung nhỏ nhất của 2 số – Chương trình tìm BCNN của 2 số là một bài tập cơ bản giúp những bạn sinh viên rèn luyện tư duy lập trình. Trong nội dung bài viết này, Nguyễn Văn Hiếu sẽ cùng những bạn đi tìm những phương pháp rất khác nhau để giải bài tập tìm 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 triển khai và code tìm bcnn minh họa theo cách đó.
1. Bội chung nhỏ nhất là gì?
Theo Wikipedia,
Trong số học, bội số chung nhỏ nhất (hay còn gọi tắt là bội chung nhỏ nhất, viết tắt là BCNN, tiếng Anh: least common multiple hoặc lowest common multiple (LCM) hoặc smallest common multiple) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho tất cả a và b.[1] Tức là nó hoàn toà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 LCM(a, b) là 0.
Định nghĩa trên đôi khi được tổng quát hoá cho hơn hai số nguyên dương: Bội chung nhỏ nhất của a1,…, an là số nguyên dương nhỏ nhất là bội số của a1,…, an.
2. Các thuật toán tìm bội chung nhỏ 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 tất cả hai số a và b. Như vậy, Nếu gọi lcm = BCNN(a, b); Khi đó, ta hoàn toàn có thể biết chắc như đinh rằng max(a, b) <= lcm <= a*b.
Nắm rõ tính chất này, ta hoàn toàn có thể đi vào một số trong những thuật toán tìm BCNN như sau:
C1. Lặp tăng dần cho tới khi tìm được BCNN
Cách này ý tưởng khá là đơn giản, ta chỉ việc tiến hành lặp từ nhỏ tới lớn những số trong đoạn từ [max(a, b),a*b](gồm có cả hai đầu mút). Số đầu tiên chia hết cho tất cả a và b sẽ là BCNN của a và b.
Đánh giá: Cách này trong trường hợp xấu nhất sẽ cần a*b – max(a, b) lần lặp. Vẫn với ý tưởng này nhưng sẽ được tối ưu ở C2
#include
#include
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 thử xem sao:
C2. Tối ưu lặp của cách 1
BCNN của 2 số a và b phải chia hết cho tất cả hai số này. Do đó, ta hoàn toàn có thể chỉ việc duyệt qua những số chia hết cho một số trong những(hoặc a, hoặc b). Nhưng để tối ưu, bạn hãy duyệt qua những số chia hết cho 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 những số chia hết cho 7 là 7, 14, 21, 28, 35. Như vậy, tất cả chúng ta giảm được rất nhiều số lần lặp rồi.
Đánh giá: Cách này số lần lặp trong trường hợp xấu nhất là a*b / max(a, b).
#include
#include
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 thử chương trình:
C3. Phân tích thừa số nguyên tố
Sử dụng cách tìm bcnn đã học trong toán cấp 2:
- Bước 1: Phân tích mỗi số ra thừa số nguyên tố.
Bước 2: Chọn ra những thừa số nguyên tố chung và riêng.
Bước 3: Lập tích những thừa số đã chọn, mỗi thừa số lấy với số mũ lớn số 1 của nó. Tích đó là BCNN cần tìm.
Cách này mình đánh giá chỉ thuận tiện cho tính toán trên giấy, việc thực hiện code phức tạp hơn và tốc độ cũng không thật tốt.
Lưu ý: Để code ngắn gọn nhất, mình sẽ sử dụng những cấu trúc STL của C++ và tính năng for auto của C++11
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include
#include
#include
#include
using namespace std;
int main()
int a = 5, b = 7, lcm;
map
set
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 hoàn toàn có thể tham khảo và bạn hoàn toàn có thể tối ưu thêm. Mình sẽ không lý giải sâu vì thực tế, thuật toán tìm bcnn này triển khai khá rườm rà và không tối ưu.
C4. Tìm BCNN của 2 số nhờ vào UCLN
Dưới đây là sơ đồ khối tìm bội chung nhỏ nhất của 2 số:
Sơ đồ khối tìm BCNN của 2 số
Khi đó, ta có công thức: BCNN(a, b) = a*b / UCLN(a,b)
Các bạn hoàn toàn có thể xem những thuật toán tìm UCLN của 2 số, dưới đây là code tham khảo tìm bội chung nhỏ nhất theo UCLN giống sơ đồ khối phía trên:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include
#include
#include
#include
using namespace std;
int gcd(int a, int b) 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ờ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 ở C++17
Hàm này chỉ có ở C++17, và cách sử dụng rất đơn giản:
#include
#include
#include
using namespace std;
int main()
int a = 5, b = 7;
int ans = lcm(a, b);
printf("BCNN(%d, %d) = %d", a, b, ans);
