Tìm bội chung nhỏ nhất của tất cả các phần tử trong mảng
Bài toán: Cho mảng một chiều các số nguyên dương. Hãy viết chương trình tìm bội chung nhỏ nhất của một mảng các số nguyên đã cho.
- Bội chung nhỏ nhất là số nguyên x nhỏ nhất sao cho x chia hết cho tất cả các các phần tử trong mảng.
Ví dụ:
- Input:
|
1 |
1 2 3 6 |
- Output:
|
1 |
BCNN la : 6 |
Ý tưởng tìm bội chung nhỏ nhất của một mảng
- Để tìm bội chung nhỏ nhất của một mảng thì ta thực hiện tìm bội chung nhỏ nhất của hai số đầu tiên của mảng là
a[0] và a[1]sau đó lưu giá trị vào một biếntemp. - Việc tiếp theo là ta tìm BCNN của
tempvàa[2]rồi lại tiến hành lưu BCNN vào biếntemp. - Ta cứ thực hiện lần lượt tìm BCNN của
tempvà các phần tử tiếp theo của mảng. - Sau khi tìm BCNN của
tempvới tất cả các số nguyên trong mảng rồi thìtempchính là bội chung nhỏ nhất của một mảng.
Xây dựng hàm tính bội chung nhỏ nhất:
- Để tính bội chung nhỏ nhất của hai số a, b thì ta tiến hành phân tích a, b thành các thừa số nguyên tố.
- Nếu a và b là các số nguyên tố thì BCNN là a*b.
- Tiến hành lấy các thừa số nguyên tố chung và riêng của a và b.
- 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.
Ví dụ:
|
1 2 3 |
12 = 2*2*3 16 = 2*2*2*2 Suy ra BCNN = 2*2*2*2*3 = 48. |
Tuy nhiên có một cách khác tính BCNN nhanh hơn mà không cần phải phân tích ra thành các thừa số nguyên tố.
- BCNN( a, b ) = a*b / UCLN( a, b );
- Nếu các bạn chưa biết cách tính UCLN thì có thể xem tại đây.
Code tham khảo
|
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 |
#include<iostream> using namespace std; int UCLN(int a, int b){ if(a==b) return a; if(a>b) UCLN(a-b,b); else UCLN(a,b-a); } int BCNN(int a, int b){ return (a*b/UCLN(a,b) ); } void NhapMang(int a[],int n){ for(int i=0;i<n;i++){ cout<<"Nhap a["<<i<<"]: "; cin>>a[i]; } } int BCNN_Mang(int a[],int n){ int temp = BCNN(a[0], a[1] ); for(int i=2;i<n;i++){ temp = BCNN(temp, a[i]); } return temp; } int main(){ int a[1000]; int n; cout<<"Nhap vao n: "; cin>>n; NhapMang(a,n); cout<<"BCNN la: "<<BCNN_Mang(a,n); return 0; } |
Sau khi chạy chương trình trên ta nhận được kết quả:
|
1 2 3 4 5 |
Nhap vao n: 3 Nhap a[0]: 1 Nhap a[1]: 2 Nhap a[2]: 3 BCNN la: 6 |
Bài viết của mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !
