Tìm ước chung lớn nhất của 1 dãy số | Tìm USCLN của một dãy số

[tiennt]

Thuật toán mà ông thầy chỉ cho mình đó là tìm phần tử min của mảng rùi sẽ xét các ước của nó từ lớn nhất và kiểm tra xem nó có là ước của các phần tử của mảng ko, nếu không đúng sẽ xét tiếp đến ước nhỏ hơn tiếp theo, cứ xét như thế sẽ tìm đc UCLN của cả dãy. Đây là code mình viết, đã test và kq ok. Các bác chỉ bảo có j sai xót ko nhé.

    void divisor(int a[],int*n)    {        int i,j,min,flag;        min=abs(a[0]);        for(i=1;i<*n;i++)            if(min>abs(a[i]))            min=abs(a[i]);            printf("\nmin=%d",min);        for(i=min;i>0;i--)            {               if (min%i==0)                  {                    flag=0;                    for(j=0;j<*n;j++)                        if(a[j]%i)                            {                                flag=1;                                continue;                            }                    }               if(flag==0)                    break;             }        printf("\nUCLN cua mang la: %d",i);    }

[nh0xkool]

int ucln(int a,int b){        do    {        if(a>b)a=a-b;        else b=b-a;    }    while(a!=b);    return a;}void ucd(int a[],int &n){    int i,j;     do    {        for(i=0,j=-1;i<n-1;i+=2)        {            j++;            a[j]=ucln(a[i],a[i+1]);        }        if((n%2)!=0)        {            a[j+1]=a[n-1];            n=(n+1)/2;        }        else n=n/2;    }    while(n!=1); }

[boss14420]

Thuật toán mà ông thầy chỉ cho mình đó là tìm phần tử min của mảng rùi sẽ xét các ước của nó từ lớn nhất và kiểm tra xem nó có là ước của các phần tử của mảng ko, nếu không đúng sẽ xét tiếp đến ước nhỏ hơn tiếp theo, cứ xét như thế sẽ tìm đc UCLN của cả dãy. Đây là code mình viết, đã test và kq ok. Các bác chỉ bảo có j sai xót ko nhé.

    void divisor(int a[],int*n)    {        int i,j,min,flag;        min=abs(a[0]);        for(i=1;i<*n;i++)            if(min>abs(a[i]))            min=abs(a[i]);            printf("\nmin=%d",min);        for(i=min;i>0;i--)            {               if (min%i==0)                  {                    flag=0;                    for(j=0;j<*n;j++)                        if(a[j]%i)                            {                                flag=1;                                continue;                            }                    }               if(flag==0)                    break;             }        printf("\nUCLN cua mang la: %d",i);    }

Cách này cũng ổn nhưng mà nếu min(a) quá lớn thì sẽ phải chạy khá lâu.
độ phức tạp của cách này là O(sizeof(a)*min(a))

Tại sao không ai nghĩ đến cách làm dựa trên định nghĩa nhỉ ?
Phân tích ra thừa số nguyên tố, sau đó chọn các số mũ nhỏ nhất.

[Wazi Armstrong]

Cách này cũng ổn nhưng mà nếu min(a) quá lớn thì sẽ phải chạy khá lâu.
độ phức tạp của cách này là O(sizeof(a)*min(a))

Tại sao không ai nghĩ đến cách làm dựa trên định nghĩa nhỉ ?
Phân tích ra thừa số nguyên tố, sau đó chọn các số mũ nhỏ nhất.

Bạn nghĩ rằng phân tích ra thừa số nguyên tố của một số lớn là nhanh chăng?
Chưa kể đến bộ nhớ để lưu cái đám phân tích ra rồi đó. Rồi đến tổ chức bộ nhớ để tiện cho việc truy vấn.
Cứ đơn giản dễ hiểu như bài #2 của anh kevin mà làm

[boss14420]

Bạn nghĩ rằng phân tích ra thừa số nguyên tố của một số lớn là nhanh chăng?
Chưa kể đến bộ nhớ để lưu cái đám phân tích ra rồi đó. Rồi đến tổ chức bộ nhớ để tiện cho việc truy vấn.
Cứ đơn giản dễ hiểu như bài #2 của anh kevin mà làm

Trong trường hợp tệ nhất là O(n^1/2) khi n là số nguyên tố, nói chung là nhanh hơn việc duyệt từ n cho đến 1.
Lưu trữ thì dùng mảng để lưu thừa số nguyên tố và số mũ, 1 số int chỉ chứa tối đa là 28 thừa số nguyên tố trong phân tích nên chắc cũng không vấn đề gì.

[VoTichSu]

Thuật toán tìm các ước của số nhỏ nhất trong mảng là thuật toán chính thức tôi học trong sách dạy về Lập Trình và Thuật Toán (Programming and Algorithm) [lâu ngày quá quên mất tên tác giả].

Tuy độ phức tạp của con toán khá cao nhưng độ phức tạp code và giải thuật tương đối thấp.

[Wazi Armstrong]

Trong trường hợp tệ nhất là O(n^1/2) khi n là số nguyên tố, nói chung là nhanh hơn việc duyệt từ n cho đến 1.
Lưu trữ thì dùng mảng để lưu thừa số nguyên tố và số mũ, 1 số int chỉ chứa tối đa là 28 thừa số nguyên tố trong phân tích nên chắc cũng không vấn đề gì.

- Nhưng xác suất về 1 đề break trong vòng lặp là khá cao với những dãy nhiều số.
Với những dãy ít số thì thời gian chênh nhau không đáng kể
- Trong khi cách đó lại đơn giản hơn về coding, nghĩ phát có thể viết ngay được, không như phân tích ra thừa số nguyên tố còn phải nghĩ đến việc tổ chức bộ nhớ, rồi đến việc lấy số mũ nhỏ nhất của các thừa số nguyên tố trong loạt các mảng 28 phần tử kia nữa (nếu đầu vào có long thì chưa biết thế nào)
- Vấn đề thứ 3, để chọn một hướng giải quyết vđ tốt, độ phức tạp của thuật toán chỉ là 1 yếu tố, nó có ý nghĩa cho những bài toán có đầu vào lớn. Tuy bài của bạn có độ phức tạp thuật toán là O(n^1/2) nhưng xét những công đoạn nó làm thì đầu tiên phải tách mỗi số trong dãy cho vào một mảng 28 phần tử. Thứ 2, duyệt từ đầu mảng đến cuối mảng, với mỗi vòng lặp thì lại duyệt qua các mảng tại ví trí đó trên mỗi mảng để tìm phần tử có số mũ nhỏ nhất... Bạn nghĩ rằng 2 vòng for lồng nhau mỗi vòng lặp n với 1 triệu lệnh tuần tự cái nào chạy nhanh hơn với đầu vào n nhỏ hơn 1000? Ngoài việc đánh giá độ phức tạp còn nên để ý cả độ lớn của dữ liệu đầu vào nữa, cũng như xác suất xảy ra các trường hợp tốt nhất, tệ nhất...

[boss14420]

- Nhưng xác suất về 1 đề break trong vòng lặp là khá cao với những dãy nhiều số.
Với những dãy ít số thì thời gian chênh nhau không đáng kể
- Trong khi cách đó lại đơn giản hơn về coding, nghĩ phát có thể viết ngay được, không như phân tích ra thừa số nguyên tố còn phải nghĩ đến việc tổ chức bộ nhớ, rồi đến việc lấy số mũ nhỏ nhất của các thừa số nguyên tố trong loạt các mảng 28 phần tử kia nữa (nếu đầu vào có long thì chưa biết thế nào)
- Vấn đề thứ 3, để chọn một hướng giải quyết vđ tốt, độ phức tạp của thuật toán chỉ là 1 yếu tố, nó có ý nghĩa cho những bài toán có đầu vào lớn. Tuy bài của bạn có độ phức tạp thuật toán là O(n^1/2) nhưng xét những công đoạn nó làm thì đầu tiên phải tách mỗi số trong dãy cho vào một mảng 28 phần tử. Thứ 2, duyệt từ đầu mảng đến cuối mảng, với mỗi vòng lặp thì lại duyệt qua các mảng tại ví trí đó trên mỗi mảng để tìm phần tử có số mũ nhỏ nhất... Bạn nghĩ rằng 2 vòng for lồng nhau mỗi vòng lặp n với 1 triệu lệnh tuần tự cái nào chạy nhanh hơn với đầu vào n nhỏ hơn 1000? Ngoài việc đánh giá độ phức tạp còn nên để ý cả độ lớn của dữ liệu đầu vào nữa, cũng như xác suất xảy ra các trường hợp tốt nhất, tệ nhất...

Ừ. Nghĩ lại thì cách này cũng không hay lắm.
Cứ làm theo cách của huynguyen là đơn giản nhất.

[quoctuan.quoc]

Giả sử bạn có hàm int UCLN(int a,int b) trả về ước chung lớn nhất của 2 số a, b
giờ để tìm ưcln cho 1 mảng x với n phần tử bạn thêm đoạn code này:

d = ucln(x[0],x[1]);
for (int i = 2; i <n; i++)
d = ucln(d,x[i]);

ok?

Cám ơn code của bạn rất nhiều! Nếu tìm tất cả ước chung của 1 mảng thì làm sao vậy bạn bạn có thể hướng dẫn viết code luôn được không? Cám ơn bạn nhiều
Ví dụ: Mình có dẫy số 3,9,12,15 thì cho tất cả ước của các số này là 1,3

[khoaph]

Cám ơn code của bạn rất nhiều! Nếu tìm tất cả ước chung của 1 mảng thì làm sao vậy bạn bạn có thể hướng dẫn viết code luôn được không? Cám ơn bạn nhiều
Ví dụ: Mình có dẫy số 3,9,12,15 thì cho tất cả ước của các số này là 1,3

#include <iostream>#include <vector>#include <math.h>using namespace std;void lietKeUoc(int n){    vector<int> uocSo;    int i = 1;    while (i < sqrt(n)) {        if (n % i == 0) {            uocSo.push_back(i);            uocSo.push_back(n / i);        }        i++;    }    if (i * i == n) uocSo.push_back(i);    sort(uocSo.begin(), uocSo.end());    for (i = 0; i < uocSo.size(); i++) {        cout << uocSo[i] << " ";    }    cout << "\n";}int main(int argc, char *argv[]){    lietKeUoc(18);    lietKeUoc(225);}/*kết quả1 2 3 6 9 181 3 5 9 15 25 45 75 225 [Program finished]*/

Tìm ucln, sau đó gọi lietKeUoc(ucln)