Kiến thức

Xin góp ý thuật toán: Tìm ƯCLN của các phần tử trong mảng-programming-Dạy Nhau Học

Bạn đang xem: Xin góp ý thuật toán: Tìm ƯCLN của các phần tử trong mảng-programming-Dạy Nhau Học

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

c

c++

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 << "nNhap 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 << "nNhap so luong phan tu: "; cin >> n; if (n < 0 || n > MAX) cout << "nSo luong phan tu khong hop le"; } while (n < 0 || n > MAX); NhapMang(a, n); XuatMang(a, n); cout << "nUCLN 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 :joy:

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… tới khi hết thì un 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

2 Likes

Ok anh :smiley:
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 ạ ?

chắc cũng tương tự thôi
b1 = bcnn(a,b),
b2 = bcnn(b1,c),
b3 = bcnn(b2,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.

2 Likes

Bạn này viết code dễ đọc, biết comment đúng chỗ :smiley:
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)

1 Like

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

1 Like

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

2 Likes

Ok, code update của em đây :smiley:

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 :slight_smile:

P/S:

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 …

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 ạ :slight_smile:

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; } 

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

chia trước nhân sau

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

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.

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

1 Like

OK rồi :smiley: Quá tuyệt vời anh

@tntxtnt

ơi :joy_cat:

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ỉ :smiley: Còn code mới anh hướng dẫn thì nó mới ra đúng :slight_smile:

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

1 Like

Ok em hiểu òi :smiley:

có lẽ là không

1 Like

OK, thanks anh

@tntxtnt

và mọi người nhiều lắm. Very “nhiệt tình” :thumbsup:

P/S: Nếu có ai còn cách cải thiện hoặc tối ưu thì cứ post lên đây nhé :slight_smile:

mình xin cải thiện thêm 1 chút về UCLN, trong vòng for thêm điều kiện nếu UCLN == 1 thì break; có thể hạn chế đc vòng lặp :3

1 Like

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button