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

[halfblood88]

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

[Kevin Hoang]

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

[metal_shield]

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?

[sieuphuong]

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 .

[hailoc12]

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.

[ath]

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

[huynguyen]

hix, chi đâu mà rắc rối rứa. Đơn giản vầy là được rồi

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.

[halfblood88]

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
-

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

[halfblood88]

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

[halfblood88]

Viết theo cách của bạn huynguyen

#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();
}