Thuật Toán Tìm Ước Chung Lớn Nhất Và Bội Chung Nhỏ Nhất

     

Tiếp tục Series bài viết CTDL và Thuật toán, lúc này hãy thuộc blog maybomnuocchuachay.vn khám phá về thuật toán tìm UCLN BCNN trong nội dung bài viết dưới phía trên nhé.

Bạn đang xem: Thuật toán tìm ước chung lớn nhất và bội chung nhỏ nhất

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

Bài toán tìmước chung mập nhất, bội chung nhỏ tuổi nhất C/C++là một bài bác toán rất thú vị 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 nêu lên dưới nhiều dạng không giống nhau, nhưng tóm tắt lại là: Tìm cầu chung lớn số 1 hay kiếm tìm bội chung nhỏ tuổ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 X rất có thể chia hết mang lại Y, lấy một ví dụ 2 là cầu 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 mà cả A cùng B phần đa chia hết). UCLN có thể là bao gồm số A hoặc B, 1 hay bất kỳ số nguyên như thế nào khác.


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

3 cách thường được sử dụng nhất để tìm UCLN trong lập trình:

Cách 1: bình chọn tuần tự.Cách 1: tìm UCLN thực hiện phép trừ.Cách 2: kiếm tìm UCLN sử dụng phép chia(Hay nói một cách khác là giải thuật Euclid).

Để tìm kiế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 với BCNN

Tìm UCLN bằng cách kiểm tra tuần tự

Ý tưởngtìm UCLN bằng cách kiểm tra tuần tựnhư sau:

Bước 1: Tìm số minab = min(A,B)Tìm số nhỏ hơn giữa 2 số A và B.

Xem thêm: 798 Cách Mạng Tháng 8 Cách Mạng Tháng 8, P, 798 Cách Mạng Tháng 8, P

Bước 2: Duyệt vòng lặp i chạy ngược từ bỏ minAB tới 1(tính cả tiên phong hàng đầu và minAB).Bước 3: Nếu cả hai số A, B các 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) // nếu như b > a ta chạy khối lệnh để gửi b thành a và ngược lại temp = b; b = a; a = temp; // sau khối lệnh, a khoác định đã là số được gắn thông qua số lớn hơn, b là số nhỏ tuổi hơn int i = b; // i chạy từ b while(i >= 1) if(a%i == 0 && b%i == 0) // trường hợp a với b cùng phân tách hết mang lại 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; // trường hợp a với b cùng chia hết cho i trả về kq mang lại hàm return GCD(a,b,i-1); //Gọi đệ quy cùng i giảm đi 1
Lưu ý: Trong giải thuật bằng đệ quy phần này mặc định các bạn phải tra cứu trước số imin(a,b), sau đó mới gọi cùng truyền tham số cho hàm.

Tìm UCLN thực hiện phép trừ

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

Nói thì hơi cạnh tranh hiểu, bạn chỉ việc nhớ thuật toán là được, cùng xem thêm 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ông giống b if(a > b) // giả dụ a > b a = a - b; // gán lại a else // Trường phù hợp b > a b = b - a; // Gán lại b return a; // return b;
Minh họa lời giải 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); // trường hợp a > b điện thoại tư vấn hàm đệ trở về bài toán tính UCLN a-b với bif(aa call hàm đệ quay trở về bài toán tính UCLN a với b-a

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

Có một công thức toán học tập đượ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ó thể hiểu dễ dàng như sau: Lấy a%b được r, đính lại a = b, b=r, hôm nay bài toán quay trở về tìm UCLN của b cùng r. Thực hiện lặp cho tới khi r = 0 thì b đó là kết quả ta yêu cầu tìm.

Thuật toán này còn có độ phức tạp rất thấp yêu cầu thường được ưu tiên trong số 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, quay về bài toán kiếm tìm ucln của b với 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 lời giải bằng đệ quy


int GCD(int a, int b)if(b==0) return a; //Sau đệ quy hôm nay kiểm tra b chính 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); // hotline lại hàm đệ quy tính UCLN giữa b cùng r
Nếu chúng ta là người bắt đầu, cùng với hàm Đệ quy này chú ý vào tất cả thể bạn sẽ không hình dung ra được thuật toán chạy ra làm cho sao…bạn đề xuất thăm khảo thêm bài viết dưới đây.


Tìm đọc về Hàm đệ quy vào lập trình

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

Đầu tiên bọn họ hãy kiểm tra 1 công tác tính UCLN với 1 trong các thuật toán trên như sau.

Xem thêm: Bạn Bao Nhiêu Tuổi Tiếng Trung Và Cách Trả Lời Trong Giao Tiếp


#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 tất cả cách


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


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


Blogger
Facebook
Mail
Twitter
Youtube

maybomnuocchuachay.vn · đảm bảo an toàn nội dung vày DMCA.com Protection Status