Tìm Ước Số Chung Lớn Nhất Trong C

     

Tiếp tục Series nội dung bài viết CTDL và Thuật toán, từ bây giờ hãy thuộc blog thucdemcungban.vn tìm hiểu về thuật toán tìm kiếm UCLN BCNN trong bài viết dưới đây nhé.

Bạn đang xem: Tìm ước số chung lớn nhất trong c

Giới thiệu câu hỏi UCLN, BCNN

Bài toán tìmước chung béo nhất, bội chung nhỏ dại nhất C/C++là một bài toán rất hay trong lập trình sẵn cơ bản, hầu hết chúng ta mới học tập lập trình đều rất hứng thú cùng với nó.

Bài toán hoàn toàn có thể được đặt ra dưới những dạng không giống nhau, tuy vậy tóm tắt lại là: Tìm mong chung lớn số 1 hay tìm kiếm bội chung bé dại nhất của nhì số nguyên A, B.

Ước của một trong những X là số Y nhưng mà X rất có thể chia hết cho Y, lấy ví dụ như 2 là cầu của 4 . . . UCLN của nhị số A, B là ước lớn nhất của cả nhì số đó(Tức là số lớn số 1 mà cả A với B đông đảo chia hết). UCLN có thể là chính số A hoặc B, 1 hay bất cứ số nguyên làm sao khác.


Tương tự, Bội của một số X là số Y Y rất có thể chia hết đến X, ví dụ 4 là bội của 2 . . . BCNN của nhị số A, B là bội bé dại nhất của tất cả hai số đó(Tức là số bé dại nhất mà hoàn toàn có thể chia hết cho cả A và B). BCNN có thể là thiết yếu số A hoặc B, hay bất kể số nguyên nào khác, tuy nhiên BCNN không thể nhỏ hơn A hoặc B.

3 cách hay được dùng nhất để tìm UCLN trong lập trình:

Cách 1: soát sổ tuần tự.Cách 1: tra cứu UCLN sử dụng phép trừ.Cách 2: tra cứu UCLN sử dụng phép chia(Hay nói một cách khác là giải thuật Euclid).

Để tìm BCNN, sau khoản thời gian đã bao gồm UCLN ta chỉ việc lấy tích A, B chia cho UCLN.

Giải thuật tra cứu 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 kiểm tra tuần tựnhư sau:

Bước 1: Tìm số minab = min(A,B)Tìm số bé dại hơn thân 2 số A cùng B.

Xem thêm: Cây Cao Su Được Trồng Nhiều Chủ Yếu Trên Đất, Dựa Vào Bảng 32

Bước 2: Duyệt vòng lặp i chạy ngược trường đoản cú minAB tới 1(tính cả số 1 và minAB).Bước 3: Nếu cả 2 số A, B đều chia hết i ngừng thuật toán, và i chính là UCLN cần tìm.Minh 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) // giả dụ b > a ta chạy khối lệnh để gửi b thành a và trái lại temp = b; b = a; a = temp; // sau khối lệnh, a mang định sẽ là số được gắn ngay số lớn hơn, b là số bé dại hơn int i = b; // i chạy trường đoản cú b while(i >= 1) if(a%i == 0 && b%i == 0) // nếu a với b cùng phân chia hết mang đến i break; // bay vòng lặp i--; return i; // Trả về i, i là UCLN của A, B
Giải thuật bởi đệ quy


int GCD(int a, int b, int i) if(a%i==0 && b%i==0) return i; // giả dụ a và b cùng phân tách hết mang lại i trả về kq mang lại hàm return GCD(a,b,i-1); //Gọi đệ quy với i giảm sút 1
Lưu ý: Trong lời giải bằng đệ quy phần này mang định các bạn phải kiếm tìm trước số imin(a,b), sau đó bắt đầu gọi cùng truyền tham số cho hàm.

Tìm UCLN sử dụng phép trừ

Thuật toán này còn có ý tưởng như sau: khi nào a != b thì lấy số lớn hơn trừ đến số bé nhiều hơn sau đó gán lại quý hiếm bằng đúng thương hiệu vừa tính được. Khi hai số cân nhau thì đó chính là ước chung phệ nhất.

Nói thì hơi cực nhọc hiểu, bạn chỉ việc nhớ thuật toán là được, cùng tham khảo code C/C++ phía dưới:

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


int GCD(int a, int b) while(a != b) // khi a còn khác b if(a > b) // trường hợp a > b a = a - b; // gán lại a else // Trường vừa lòng b > a b = b - a; // Gán lại b return a; // return b;
Minh họa giải mã bằng đệ quy


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

Thuật toán kiếm tìm UCLN sử dụng phép chia(giải thuật Euclid)

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


Với thuật toán này bạn cũng có thể hiểu đơn giản dễ dàng như sau: Lấy a%b được r, thêm lại a = b, b=r, hôm nay bài toán trở về tìm UCLN của b cùng r. Triển khai lặp cho tới khi r = 0 thì b chính là kết quả ta đề xuất tìm.

Thuật toán này có độ phức hợp rất thấp phải thường được ưu tiên trong các bài toán thực tế.

Minh họa giải mã 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, trở lại bài toán kiếm tìm ucln của b và r a = b; b = r; r = a % b; // r là phần dư của phép phân tách a/b return b;
Minh họa giải thuật bằng đệ quy


int GCD(int a, int b)if(b==0) return a; //Sau đệ quy lúc này kiểm tra b đó là a%b được truyền vào tức nó chính là r, còn a đó là b được truyền vàoreturn GCD(b, a%b); // gọi lại hàm đệ quy tính UCLN giữa b cùng r
Nếu bạn là người bắt đầu, với hàm Đệ quy này nhìn vào tất cả thể các bạn sẽ không tưởng tượng ra được thuật toán chạy ra làm sao…bạn cần thăm khảo thêm nội dung bài viết dưới đây.


Tìm phát âm về Hàm đệ quy vào lập trình

Tìm bội chung bé dại nhất

Đầu tiên họ hãy chạy thử 1 lịch trình tính UCLN với 1 trong các thuật toán trên như sau.

Xem thêm: Hai Điện Tích Điểm Q1=2.10^-6


#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 quả chương trình:


*

Về blog Tui gồm cách


TUI CÓ CÁCH là blog cá nhân xây dựng nhằm share các kĩ năng lập trình, thủ thuật thiết bị tính, thủ thuật điện thoại, kỹ năng và kiến thức kiếm chi phí online mà tôi được cho là với cùng đồng.


Kết nối cùng với tôi


Blogger
Facebook
Mail
Twitter
Youtube

thucdemcungban.vn · bảo vệ nội dung vì chưng DMCA.com Protection Status