30/09/2018, 22:54

Xin góp ý thuật toán: Tìm ƯCLN của các phần tử trong mảng

Xin chào mọi người.

Mình đang làm 1 bài tập như sau: Cho mảng một chiều các số nguyên dương.Hãy viết hàm tìm ước chung lớn nhất của tất cả các phần tử trong mảng.

Và code giải kèm thuật toán của mình như sau:

#define MAX 100
using namespace std;

void NhapMang(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << "
Nhap a[" << i << "] = ";
		cin >> a[i];
	}
}
void XuatMang(int a[], int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << "   ";
}
int Min(int a[], int n) // tìm ra phần tử Min (nhỏ nhất) trong mảng
{
	int Min = a[0];
	for (int i = 1; i < n; i++)
		if (a[i] < Min)
			Min = a[i];
	return Min; // trả về phần tử nhỏ nhất trong mảng là Min
}
bool KiemTraChiaHet(int a[], int n, int x) // kiểm tra xem tất cả các phần tử trong mảng có chia hết cho phần tử X hay không
{
	for (int i = 0; i < n; i++)
		if (a[i] % x != 0)
			return false;
	return true; // tất cả các phần tử trong mảng chia hết cho phần tử X
}
int UCLN(int a[], int n)
{
	int b[MAX], m = 0, phantu = 0; // tạo 1 mảng b khác.
	int Minimum = Min(a, n); // 12
	if (KiemTraChiaHet(a, n, Minimum)) // nếu trong mảng có 1 số mà tất cả các phần tử đều chia hết cho số đó thì số đó là UCLN
		return Minimum;
	else // Nếu không thì chúng ta phân tích các trường hợp:
	{
		for (int i = 1; i <= Minimum / 2; i++) // Lưu tất cả các ước của số Min trừ chính nó vào mảng b 
		{
			if (Minimum % i == 0)
			{
				b[phantu++] = i;
				m++;
			}
		}
		for (int i = m - 1; i >= 0; i--) // xét từng ước của Min (trừ chính nó)
		{
			bool Check = true;
			for (int j = 0; j < n; j++) // xét các số trong mảng, nếu số nào không chia hết cho b[i] thì false và không xét nữa
			{
				if (a[j] % b[i] != 0)
				{
					Check = false;
					break;
				}
			}
			if (Check == true) //chạy xong vòng lặp trên mà Check vẫn true, nghĩa là tất cả các số trong mảng đều chia hết cho b[i]
				return b[i]; // b[i] chính là số phải tìm
		}
	}
}
int main()
{
	int a[MAX];
	int n;
	do
	{
		cout << "
Nhap so luong phan tu: ";
		cin >> n;
		if (n < 0 || n > MAX)
			cout << "
So luong phan tu khong hop le";
	} while (n < 0 || n > MAX);
	NhapMang(a, n);
	XuatMang(a, n);
	cout << "
UCLN cua cac phan tu trong mang: " << UCLN(a, n) << endl;
	getch();
	return 0;
}

Tuy nhiên thì mình thấy code của mình có phần hơi “dài” nên nhờ mọi người góp ý xem là thuật toán của mình phù hợp chưa, có tối ưu nhất chưa …
Xin cảm ơn mọi người rất nhiều !

P/S: Sư phụ @tntxtnt vô xem giùm cháu 1 cái

‏ viết 01:10 ngày 01/10/2018

UCLN của (a,b,c,d,e,…) thì tìm u₁ = ucln(a,b), rồi tìm u₂ = ucln(u₁,c), rồi u₃ = ucln(u₂,d), v.v… tới khi hết thì u_n chính là UCLN của (a,b,c,d,e,…). Tóm lại chỉ cần 1 hàm int ulcn(int a, int b) rồi 1 vòng for quét hết là xong

Người bí ẩn viết 01:10 ngày 01/10/2018

Ok anh
Nếu đề bài sửa lại là Tìm BCNN thì anh có thuật nào y hệt như vậy không ạ ?

‏ viết 00:54 ngày 01/10/2018

chắc cũng tương tự thôi
b₁ = bcnn(a,b),
b₂ = bcnn(b₁,c),
b₃ = bcnn(b₂,d),
v.v…

tìm bcnn của 2 số a,b bằng cách lấy a / ucln(a,b) * b. Lấy ab/ucln(a,b) cũng được, nhưng sợ bị tràn số khi lấy ab, nên lấy a chia cho ucln trước rồi nhân b sau.

Lưu Nguyễn Phát viết 00:56 ngày 01/10/2018

Bạn này viết code dễ đọc, biết comment đúng chỗ
Thuật của bạn “chưa” sai (mình đọc qua nhưng chưa thấy chỗ sai).
Còn thuật đúng đắn và tối ưu hơn như anh @tntxtnt đã nói.
Mình bổ sung thêm cái nữa là: BCNN(A, B) = (A*B)/UCLN(A, B);
BCNN(A, B, … Y, Z) = BCNN(BCNN(A, B, …, Y), Z)

Tao Không Ngu. viết 01:02 ngày 01/10/2018

This post was flagged by the community and is temporarily hidden.

Thái viết 01:08 ngày 01/10/2018

Bạn nên viết một hàm riêng tính UCLN của hai số, sau đó mới tính đến chuyện tính cho một dãy nhiều số. Viết như lập chương trình sẽ tường minh hơn.

Bạn có thể tìm hiểu thuật toán Euclid. Thuật toán này giúp tìm ước chung lớn nhất của 2 số. Sau đó bạn hãy thử suy nghĩ xem UCLN(a, b, c) có mối quan hệ như thế nào với UCLN(a, b) hoặc UCLN(b, c).

Người bí ẩn viết 01:00 ngày 01/10/2018

UCLN của (a,b,c,d,e,…) thì tìm u1 = ucln(a,b), rồi tìm u2 = ucln(u1,c), rồi u3 = ucln(u2,d), v.v.

Còn thuật đúng đắn và tối ưu hơn như anh @tntxtnt đã nói.

Phát triển thuật toán tìm UCLN cho mảng. Làm kiểu duyệt qua các số như vậy nó thế nào ý.

Bạn nên viết một hàm riêng tính UCLN của hai số, sau đó mới tính đến chuyện tính cho một dãy nhiều số.

Ok, code update của em đây

int UCLN2So(int x, int y)
{
	if (x % y == 0)
		return y;
	return UCLN2So(y, x % y);//dùng đệ quy tìm ƯCLN của 2 số bằng thuật toán Euclid
}
int UCLN(int a[], int n)
{
	int UCLN = a[0];
	for (int i = 1; i < n; i++)
	{
		UCLN = UCLN2So(UCLN, a[i]);
	}
	return UCLN;
}

Mọi người cho em ý kiến ạ, em sẽ tiếp tục tối ưu nữa

P/S:

tìm bcnn của 2 số a,b bằng cách lấy a / ucln(a,b) * b. Lấy ab/ucln(a,b) cũng được, nhưng sợ bị tràn số khi lấy ab, nên lấy a chia cho ucln trước rồi nhân b sau.

Cách này có đúng với trường hợp có nhiều số không anh @tntxtnt ?
VD: 4 * 6 * 10 / ƯCLN(4, 6, 10) = 240 / 2 = 120 => Chưa đúng vì BCNN(4, 6, 10) = 60 …

Người bí ẩn viết 01:09 ngày 01/10/2018

Và sẵn tiện mọi người nhận xét + cho ý kiến về code tìm BCNN của em luôn ạ

int BCNN2So(int x, int y)
{
	return (x * y) / UCLN2So(x, y);
}
int BCNN(int a[], int n)
{
	int BCNN = a[0];
	for (int i = 1; i < n; i++)
	{
		BCNN = BCNN2So(BCNN, a[i]);
	}
	return BCNN;
}

‏ viết 01:01 ngày 01/10/2018

thử BCNN2So(65536, 65536) coi ra 65536 hay 0

chia trước nhân sau

Người bí ẩn viết 01:02 ngày 01/10/2018

thử BCNN2So(65536, 65536) coi ra 65536 hay 0

chia trước nhân sau

Dòng này đúng không anh

return (x * y) / UCLN2So(x, y);

‏ viết 01:06 ngày 01/10/2018

dòng đó đó. Chia trước rồi mới nhân sau. Bảo đảm a chia hết cho ucln(a,b) vì nó là ước của a.

VD: 4 * 6 * 10 / ƯCLN(4, 6, 10) = 240 / 2 = 120 => Chưa đúng vì BCNN(4, 6, 10) = 60 …

cái này ko đúng mà ƯCLN(4, 6, 10) vẫn cần 1 vòng for mà. Cách BCNN cũng 1 vòng for. Tội gì xài cách này ko lẹ hơn mà còn sai nữa

Người bí ẩn viết 01:07 ngày 01/10/2018

OK rồi Quá tuyệt vời anh @tntxtnt ơi

Còn chỗ nào cần sửa hoặc tối ưu nữa không anh ?

P/S: Cái code cũ, em nhập 2 số 32 vs 32 thì nó vẫn ra BCNN là 32 nhưng nhập 65536 và 65536 thì nó lại ra 0 nhỉ Còn code mới anh hướng dẫn thì nó mới ra đúng

‏ viết 00:56 ngày 01/10/2018

do tràn số đó. int 32 bit chỉ chứa được giá trị max là 2³¹ - 1, trong khi lấy 65536 * 65536 thì ra 2³² rồi, tràn số.

BCNN dễ tràn số lắm, ví dụ BCNN(65535,65537) thì int 32 bit ko chứa nổi kết quả rồi: 65535 * 65537 = 2³² - 1, trong khi int 32 bit chỉ chứa được tới 2³¹ - 1

Người bí ẩn viết 01:08 ngày 01/10/2018

do tràn số đó. int 32 bit chỉ chứa được giá trị max là 231 - 1, trong khi lấy 65536 * 65536 thì ra 232 rồi, tràn số.

BCNN dễ tràn số lắm, ví dụ BCNN(65535,65537) thì int 32 bit ko chứa nổi kết quả rồi: 65535 * 65537 = 232 - 1, trong khi int 32 bit chỉ chứa được tới 231 - 1

Ok em hiểu òi