Trang 3 trên tổng số 3 Đầu tiênĐầu tiên 123
Từ 21 tới 30 trên tổng số 30 kết quả

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

  1. #21
    Ngày gia nhập
    08 2011
    Bài viết
    16

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

    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é.


    C Code:
    1.     void divisor(int a[],int*n)
    2.     {
    3.         int i,j,min,flag;
    4.         min=abs(a[0]);
    5.         for(i=1;i<*n;i++)
    6.             if(min>abs(a[i]))
    7.             min=abs(a[i]);
    8.             printf("\nmin=%d",min);
    9.         for(i=min;i>0;i--)
    10.             {
    11.                if (min%i==0)
    12.                   {
    13.                     flag=0;
    14.                     for(j=0;j<*n;j++)
    15.                         if(a[j]%i)
    16.                             {
    17.                                 flag=1;
    18.                                 continue;
    19.                             }
    20.                     }
    21.                if(flag==0)
    22.                     break;
    23.  
    24.             }
    25.         printf("\nUCLN cua mang la: %d",i);
    26.     }

  2. #22
    Ngày gia nhập
    11 2011
    Nơi ở
    C:\Windows
    Bài viết
    2

    Mặc định không biết tại sao em làm kiểu này máy chạy hoài không ra kết quả.

    C Code:
    1. int ucln(int a,int b)
    2. {
    3.    
    4.     do
    5.     {
    6.         if(a>b)a=a-b;
    7.         else b=b-a;
    8.     }
    9.     while(a!=b);
    10.     return a;
    11. }
    12. void ucd(int a[],int &n)
    13. {
    14.     int i,j;
    15.     do
    16.     {
    17.         for(i=0,j=-1;i<n-1;i+=2)
    18.         {
    19.             j++;
    20.             a[j]=ucln(a[i],a[i+1]);
    21.         }
    22.         if((n%2)!=0)
    23.         {
    24.             a[j+1]=a[n-1];
    25.             n=(n+1)/2;
    26.         }
    27.         else n=n/2;
    28.     }
    29.     while(n!=1);
    30.  
    31. }

  3. #23
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Trích dẫn Nguyên bản được gửi bởi tiennt Xem bài viết
    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é.


    C Code:
    1.     void divisor(int a[],int*n)
    2.     {
    3.         int i,j,min,flag;
    4.         min=abs(a[0]);
    5.         for(i=1;i<*n;i++)
    6.             if(min>abs(a[i]))
    7.             min=abs(a[i]);
    8.             printf("\nmin=%d",min);
    9.         for(i=min;i>0;i--)
    10.             {
    11.                if (min%i==0)
    12.                   {
    13.                     flag=0;
    14.                     for(j=0;j<*n;j++)
    15.                         if(a[j]%i)
    16.                             {
    17.                                 flag=1;
    18.                                 continue;
    19.                             }
    20.                     }
    21.                if(flag==0)
    22.                     break;
    23.  
    24.             }
    25.         printf("\nUCLN cua mang la: %d",i);
    26.     }
    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.

  4. #24
    Ngày gia nhập
    03 2009
    Nơi ở
    %appdata%\Temp
    Bài viết
    819

    Trích dẫn Nguyên bản được gửi bởi boss14420 Xem bài viết
    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
    .::[The best way to predict the future is to invent it]::.
    __________________________________________________ _ - Alan Kay -

  5. #25
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viế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
    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ì.

  6. #26
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

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

    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.

  7. #27
    Ngày gia nhập
    03 2009
    Nơi ở
    %appdata%\Temp
    Bài viết
    819

    Trích dẫn Nguyên bản được gửi bởi boss14420 Xem bài viết
    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...
    .::[The best way to predict the future is to invent it]::.
    __________________________________________________ _ - Alan Kay -

  8. #28
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    - 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.

  9. #29
    Ngày gia nhập
    03 2022
    Bài viết
    1

    Thumbs up Cám ơn Code của bạn nhiều!

    Trích dẫn Nguyên bản được gửi bởi metal_shield Xem bài viết
    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
    Đã được chỉnh sửa lần cuối bởi quoctuan.quoc : 28-03-2022 lúc 08:00 PM.

  10. #30
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    662

    Trích dẫn Nguyên bản được gửi bởi quoctuan.quoc Xem bài viết
    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
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <math.h>
    4. using namespace std;
    5. void lietKeUoc(int n)
    6. {
    7.     vector<int> uocSo;
    8.     int i = 1;
    9.     while (i < sqrt(n)) {
    10.         if (n % i == 0) {
    11.             uocSo.push_back(i);
    12.             uocSo.push_back(n / i);
    13.         }
    14.         i++;
    15.     }
    16.     if (i * i == n) uocSo.push_back(i);
    17.     sort(uocSo.begin(), uocSo.end());
    18.     for (i = 0; i < uocSo.size(); i++) {
    19.         cout << uocSo[i] << " ";
    20.     }
    21.     cout << "\n";
    22. }
    23. int main(int argc, char *argv[])
    24. {
    25.     lietKeUoc(18);
    26.     lietKeUoc(225);
    27. }
    28. /*kết quả
    29. 1 2 3 6 9 18
    30. 1 3 5 9 15 25 45 75 225
    31.  
    32. [Program finished]
    33. */
    Tìm ucln, sau đó gọi lietKeUoc(ucln)

Các đề tài tương tự

  1. Lập trình C | Tính USCLN và BSCNN?
    Gửi bởi grubkhukho trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 19-08-2015, 10:29 AM
  2. Ước số chung lớn nhất(USCLN) của 3 số! Lỗi segment fault, sửa thế nào?
    Gửi bởi fuji13 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 4
    Bài viết cuối: 15-01-2010, 02:19 PM
  3. Tính USCLN và BSCNN
    Gửi bởi ximachaos trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 2
    Bài viết cuối: 19-08-2009, 07:49 AM
  4. Vấn đề nhỏ về thuật USCLN
    Gửi bởi gachip trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 04-08-2009, 11:57 AM
  5. Dùng đệ quy tìm USCLN
    Gửi bởi co7seo trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 23-06-2009, 03:59 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn