Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 28 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. #1
    Ngày gia nhập
    12 2007
    Bài viết
    12

    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ố

    Thầy mình mới ra 1 bài thế này.
    Cho 1 dãy số tự nhiên bất kì.Tìm ước chung lớn nhất của dãy đó.
    Bình thường chỉ tìm UCLN của 2 số.Bây giờ làm với nhiều số thực sự cảm thấy bối rối,chưa tìm được hướng đi.Ai biết có thể chia sẻ hướng giải bài này với.Mình đang học C nên các bạn chỉ dẫn trong C nhé.Thanks

  2. #2
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Theo Dr nghĩ thì như thế này.

    Giả sử dãy số ban đầu là A.
    Bạn tìm USCLN của từng cặp 2 số trong dãy số A. Ta thu được dãy số U1. U1 là dãy lưu giữ các giá trị USCLN đã vừa tính.

    Nếu một trong các giá trị của U1 == 1. Suy ra USCLN của cả dãy cũng là 1.

    Nếu tất cả các USCLN này là khác 1:
    Lặp lại việc tính USCLN từng cặp 2 số trong dãy U1. Nếu xuất hiện một giá trị = 1 thì kết luận.

    Ngược lại thì cứ tiến hành như thế cho đến khi dãy chỉ còn một phần tử. Đó chính là USCLN của dãy.

    Không biết Dr nghĩ vậy có đúng không nữa. Mọi người góp ý thêm nhé!
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    47

    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?

  4. #4
    Ngày gia nhập
    12 2007
    Bài viết
    224

    em thấy 2 hay nhiều phần tử thì có khác nhau gì đâu chứ . nếu theo cái cách gà nhất em biết được thì ta cứ lấy đại 1 phần tử nào đó trong mảng cho nó làm usc , sau đó giảm nó đi một đơn vị và xét xem cả mảng có chia hết cho nó không thôi .

  5. #5
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Khẳng định: ước chung nhỏ nhất của cả một dãy phải nhỏ hơn hoặc bằng số nhỏ nhất của dãy
    Tìm ra số nhỏ nhất của dãy. Tìm ước chung nhỏ nhất của số này với từng số trong dãy kết hợp kiểm tra các ước đó có giống nhau không.

  6. #6
    Ngày gia nhập
    01 2008
    Bài viết
    3

    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ố

    theo mình thế này có được không ví dụ: 24,6,9
    ta sắp xếp 24,9,6 sau đó lấy 24-6 sau đó lại sắp xếp 18,9,6 sau đó tiếp tục lấy 18-6 và sắp xếp là 12,9,6 làm tiếp 9,6 tiếp 9-6 =3 kết quả là 3

    ví dụ 24,9,6,4 làm 20,9,6,4 ;16,9,6,4 ;12,9,6,4 ;9,8,6,4; 8,6,5,4; 6,5,4 ;5,4,2;4,3,2; 3,2; 1 ket qua la 1 .không biết làm thế này có được không

  7. #7
    Ngày gia nhập
    11 2006
    Bài viết
    633

    hix, chi đâu mà rắc rối rứa. Đơn giản vầy là được rồi
    Code:
    d = gcd(a[0],a[1]);
    for(int i = 2; i < n; ++i)
        if (d == 1) break;
        else d = gcd(d,a[i]);
    Khả năng ucln là 1 là rất cao do đó nên có thêm điều kiện để văng ra khỏi vòng lặp, tránh chuyện lập tốn công.

  8. #8
    Ngày gia nhập
    12 2007
    Bài viết
    12

    uhm.Cách làm của ath có vẻ từ hợp lý nhất.
    Tạm thời mình viết thử một vài bước như sau ,các bác xem thử đúng không
    -
    Code:
    tạo một hàm sắp xếp theo thứ tự giảm dần
    -nhập mảng gồm n số
    -gọi hàm sắp xếp
    do
    {
    -a[1]=a[1]-a[n]
    -goi hàm sắp xếp
    }
    while(a[1]!=a[n])
    -xuất UCLN = a[i] bất kỳ vì lúc này các a[i] bằng nhau
    Lấy ví dụ của ath luôn UCLN(9,24,6)
    -Nhập
    -Sắp xếp a[1]=24;a[2]=9;a[3]=6
    Lặp:
    Lần 1 :
    +24-6=18 ,lấy a[1]=18
    +dãy mới sau khi sắp xếp 18 ,9,6
    Lần 2 :
    +18-6=12 lấy a[1]=12
    +dãy mới sau khi sắp xếp 12,9,6
    Lần 3:
    +12-6=6 a[1]=6
    +dãy mới sau khi sắp xếp 9,6,6 (lúc này a[1]#a[n] tiếp tục lặp)
    Lần 4:
    +9-6=3 a[1]=3
    +dãy mới sau khi sắp xếp 6,6,3
    Lần 5:
    +6-3=3 ;a[1]=3
    +6,3,3
    Lần 6:
    +6-3=3;a[1]=3
    +3,3,3
    a[1]=a[n] .Thoát khỏi do while

    Tạm thơi chưa có thời gian viết các bước sơ lược,chưa thử nên không biết đúng sai.Có thời gian mình sẽ viết thử và nếu đúng sẽ post lên cho anh em tham khảo luôn
    Đã được chỉnh sửa lần cuối bởi halfblood88 : 15-01-2008 lúc 09:47 PM.

  9. #9
    Ngày gia nhập
    12 2007
    Bài viết
    12

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    int i,j,n,a[100],tg;
    sapxep(int a[100])
    {         
    for(i=1;i<=n-1;i++)
    for(j=i+1;j<=n;j++)
    if(a[i]<a[j])
    {
    tg=a[i];
    a[i]=a[j];
    a[j]=tg;
    }
    }
    void main()
    {
    printf("Nhap n :");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    printf("a[%d]=",i);
    scanf("%d",&a[i]);
    }
    sapxep(a);
    do
    {
    a[1]=a[1]-a[n];
    sapxep(a);
    }
    while(a[1]!=a[n]);
    for(i=1;i<=n;i++)
    printf("Uoc chung lon nhat la :%d\n",a[i]);
    getch();
    }
    Đã thử với vài dãy cho kết quả đúng.Anh em xem thử có sai sót hoặc vô lý chỗ nào không.

  10. #10
    Ngày gia nhập
    12 2007
    Bài viết
    12

    Viết theo cách của bạn huynguyen
    Code:
    #include <stdio.h>
    #include <conio.h>
    int i,x[100],d,n;
    int ucln(int a, int b)
    {
      while (a != 0 && b != 0)
        if (a>b)
          a -= b;
        else
          b -= a;
      if (a == 0)
        return b;
      else
        return a;
    }
    void main()
    {
    printf("Nhap n:");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    printf("x[%d]=",i);
    scanf("%d",&x[i]);
    }
    d = ucln(x[1],x[2]);
    for(int i = 3; i <= n; ++i)
        if (d == 1) break;
        else d = ucln(d,x[i]);
    printf("uoc chung lon nhat la :%d",d);
    getch();
    }

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