Tiếp tục Series nội dung bài viết CTDL và Thuật tân oán, bây giờ hãy thuộc blog hanvietfoundation.org mày mò về thuật tân oán kiếm tìm UCLN cùng BCNN vào bài viết sau đây nhé.

Bạn đang xem: Tìm bội chung nhỏ nhất trong c

Giới thiệu bài toán thù UCLN, BCNN

Bài toán thù tìmước chung lớn nhất, bội bình thường bé dại độc nhất C/C++là một trong những bài bác tân oán rất lôi cuốn vào lập trình cơ phiên bản, số đông chúng ta bắt đầu học tập lập trình thường rất hứng thú với nó.

Bài tân oán hoàn toàn có thể được nêu ra dưới các dạng không giống nhau, dẫu vậy bắt tắt lại là: Tìm ước bình thường lớn nhất xuất xắc Tìm bội tầm thường bé dại tốt nhất của nhị số ngulặng A, B.

Ước của một số trong những X là số YX rất có thể phân chia không còn mang đến Y, ví dụ 2 là ước của 4 . . . UCLN của nhị số A, B là ước lớn số 1 của cả nhị số đó(Tức là số lớn số 1 nhưng mà cả A và B phần nhiều phân tách hết). UCLN rất có thể là thiết yếu số A hoặc B, 1 hay bất cứ số nguim như thế nào khác.


Tương trường đoản cú, Bội của một số X là số Y nhưng Y có thể phân tách không còn cho X, ví dụ 4 là bội của 2 . . . BCNN của nhì số A, B là bội nhỏ tuyệt nhất của tất cả nhì số đó(Tức là số nhỏ dại nhất cơ mà có thể phân tách không còn cho cả A với B). BCNN có thể là thiết yếu số A hoặc B, hay bất kỳ số nguim như thế nào khác, tuy vậy BCNN chẳng thể nhỏ dại rộng A hoặc B.

3 cách hay được dùng duy nhất nhằm tìm kiếm UCLN vào lập trình:

Cách 1: Kiểm tra tuần từ bỏ.Cách 1: Tìm UCLN áp dụng phnghiền trừ.Cách 2: Tìm UCLN áp dụng phnghiền chia(Hay còn gọi là lời giải Euclid).

Để kiếm tìm BCNN, sau khi đang tất cả UCLN ta chỉ bài toán lấy tích A, B phân chia đến UCLN.

Giải thuật search UCLN cùng BCNN

Tìm UCLN bằng phương pháp kiểm tra tuần tự

Ý tưởngtìm UCLN bằng phương pháp khám nghiệm tuần tựnhư sau:

Bước 1: Tìm số minab = min(A,B)Tìm số nhỏ dại rộng giữa 2 số A và B.Cách 2: Duyệt vòng lặp i chạy ngược từ bỏ minAB cho tới 1(tính cả hàng đầu với minAB).Cách 3: Nếu cả hai số A, B gần như chia hết i giới hạn thuật toán thù, và i đó là UCLN nên kiếm tìm.Minch họa thuật toán

Giải thuật bằng vòng lặp


int GCD(int a, int b) int temp; if(b > a) // Nếu b > a ta chạy kân hận lệnh để gửi b thành a và ngược lại temp = b; b = a; a = temp; // sau kăn năn lệnh, a khoác định vẫn là số được gắn thêm bằng số to hơn, b là số nhỏ tuổi hơn int i = b; // i chạy trường đoản cú b while(i >= 1) if(a%i == 0 &và b%i == 0) // trường hợp a với b thuộc phân chia hết cho i break; // thoát vòng lặp i--; return i; // Trả về i, i là UCLN của A, B
Giải thuật bằng đệ quy


int GCD(int a, int b, int i) if(a%i==0 && b%i==0) return i; // nếu như a cùng b thuộc phân tách hết cho i trả về kq cho hàm return GCD(a,b,i-1); //call đệ quy cùng i giảm sút 1
Lưu ý: Trong lời giải bằng đệ quy phần này khoác định chúng ta bắt buộc kiếm tìm trước số imin(a,b), kế tiếp mới gọi cùng truyền tsay đắm số đến hàm.

Tìm UCLN thực hiện phnghiền trừ

Thuật toán thù này có phát minh nhỏng sau: Khi làm sao a != b thì mang số to hơn trừ mang đến số bé hơn tiếp đến gán lại giá trị bởi chính hiệu vừa tính được. lúc nhị số cân nhau thì kia chính là ước thông thường lớn nhất.

Nói thì hơi khó gọi, bạn chỉ việc nhớ thuật toán là được, thuộc xem thêm code C/C++ phía dưới:

Minh họa giải thuật bởi vòng lặp


int GCD(int a, int b) while(a != b) // khi a còn khác b if(a > b) // nếu như a > b a = a - b; // gán lại a else // Trường hòa hợp b > a b = b - a; // Gán lại b return a; // return b;
Minc họa giải thuật bằng đệ quy


int GCD(int a, int b)if(a==b) return a; //Nếu a bởi với b trả về qk là a hoặc bif(a>b) return GCD(a-b,b); // Nếu a > b hotline hàm đệ quay trở về bài toán thù tính UCLN a-b cùng bif(aa call hàm đệ quay lại bài xích toán thù tính UCLN a và b-a

Thuật toán thù kiếm tìm UCLN sử dụng phnghiền chia(giải mã Euclid)

Có một công thức tân oán học được nêu ra nhỏng sau: a = b*x + rtức là: số a phân tách số b sẽ tiến hành x lần với dư r.


Với thuật tân oán này chúng ta có thể phát âm dễ dàng và đơn giản nhỏng sau: Lấy a%b được r, lắp lại a = b, b=r, bây giờ bài toán trở lại tìm kiếm UCLN của b cùng r. Thực hiện nay lặp cho đến lúc r = 0 thì b chính là hiệu quả ta đề xuất tìm.

Thuật tân oán này có độ phức tạp hết sức thấp buộc phải thường được ưu tiên trong những bài xích tân oán thực tiễn.

Minch họa lời giải bằng vòng lặp


int GCD(int a, int b ) int r = a % b; // a = b*x + r; while (r!=0) // Gán lại a = b, quay về bài bác toán tra cứu ucln của b cùng r a = b; b = r; r = a % b; // r là phần dư của phnghiền phân chia a/b return b;
Minch họa lời giải bằng đệ quy


int GCD(int a, int b)if(b==0) return a; //Sau đệ quy lúc này soát sổ b đó là a%b được truyền vào tức nó đó là r, còn a chính là b được truyền vàoreturn GCD(b, a%b); // call lại hàm đệ quy tính UCLN thân b và r
Nếu bạn là người bắt đầu, cùng với hàm Đệ quy này chú ý vào hoàn toàn có thể bạn sẽ ko tưởng tượng ra được thuật toán thù chạy ra làm cho sao…chúng ta nên thăm khảo thêm nội dung bài viết tiếp sau đây.


Tìm hiểu về Hàm đệ quy vào lập trình

Tìm bội thông thường nhỏ dại nhất

Thứ nhất họ hãy chạy test 1 công tác tính UCLN với cùng 1 trong những thuật toán thù bên trên nhỏng sau.

Xem thêm: Cách Tìm Gtln Gtnn Của Hàm Số Lượng Giác Lớp 12, Tìm Gtln, Gtnn Của Hàm Số Lượng Giác


#includeusing namespace std;int GCD(int a, int b)if(b==0) return a;return GCD(b, a%b);int main(){int a=4,b=6;int c = GCD(a,b);cout
Kết trái chương trình:


*

Về blog Tui có cách


TUI CÓ CÁCH là blog cá thể thiết kế nhằm mục đích chia sẻ các tài năng lập trình, mẹo nhỏ máy tính xách tay, mẹo nhỏ điện thoại cảm ứng thông minh, kỹ năng và kiến thức kiếm chi phí online nhưng tôi được biết cùng với cộng đồng.


Kết nối với tôi


Blogger
Facebook
Mail
Twitter
Youtube

hanvietfoundation.org · Bảo vệ câu chữ vày DMCA.com Protection Status