Cách tìm bội chung nhỏ nhất của chu kỳ

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 các bạn 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 các bạn đi tìm các phương pháp 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 đó.

Cách tìm bội chung nhỏ nhất của chu kỳ

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 cả a và b.[1] 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 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ố 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 và b. Như vậy, Nếu gọi lcm = BCNN(a, b); Khi đó, ta có thể biết chắc chắn rằng max(a, b) <= lcm <= a*b.

Nắm rõ tính chất này, ta có thể đi vào một số 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ỉ cần tiến hành lặp từ nhỏ tới lớn các số trong đoạn từ [max(a, b),a*b](bao gồm cả 2 đầu mút). Số đầu tiên chia hết cho 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<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 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 cả 2 số này. Do đó, ta có thể chỉ cần duyệt qua các số chia hết cho 1 số(hoặc a, hoặc b). Nhưng để tối ưu, bạn hãy duyệt qua các số chia hết cho max(a, b).

Ví dụ: a = 5, b = 7. Vậy các số chúng ta nên duyệt qua các số chia hết cho 7 là 7, 14, 21, 28, 35. Như vậy, 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<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 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 các thừa số nguyên tố chung và riêng.
  • Bước 3: Lập tích các thừa số đã chọn, mỗi thừa số lấy với số mũ lớn nhất 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 quá tốt.

Lưu ý: Để code ngắn gọn nhất, mình sẽ sử dụng các 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<iostream>

#include <map>

#include <set>

#include <math.h>

using namespace std;

int main(){

    int a = 5, b = 7, lcm;

    map<int, int> ma, 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 các bạn có thể tham khảo và bạn có thể tối ưu thêm. Mình sẽ không giải thích 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ố dựa vào UCLN

Dưới đây là sơ đồ khối tìm bội chung nhỏ nhất của 2 số:

Cách tìm bội chung nhỏ nhất của chu kỳ
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 có thể xem các 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<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ì lúc này 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<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);

}