TÌM BỘI CHUNG NHỎ NHẤT CỦA HAI SỐ TRONG C

     

Tiếp tục Series bài viết CTDL & Thuật toán, lúc này hãy cùng blog gift4u.vn tò mò về thuật toán tìm kiếm UCLN BCNN trong bài viết dưới trên đây nhé.

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

Giới thiệu việc UCLN, BCNN

Bài toán tìmước chung lớn 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 thiết kế cơ bản, hầu hết chúng ta mới học lập trình thường 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 những dạng khác nhau, dẫu vậy tóm tắt lại là: Tìm ước chung lớn nhất hay tìm bội chung nhỏ 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 hoàn toàn có thể chia hết cho Y, lấy một ví dụ 2 là ước của 4 . . . UCLN của nhì số A, B là ước lớn số 1 của cả hai số đó(Tức là số lớn nhất mà cả A cùng B hồ hết chia hết). UCLN có thể là thiết yếu số A hoặc B, 1 hay bất kể số nguyên nào khác.


Tương tự, Bội của một trong những X là số Y Y có thể chia hết mang đến 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 cả hai số đó(Tức là số bé dại nhất mà rất có thể chia hết cho tất cả A cùng 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 ko thể nhỏ tuổ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: kiểm tra tuần tự.Cách 1: kiếm tìm UCLN áp dụng phép trừ.Cách 2: tra cứu UCLN sử dụng phép chia(Hay còn được gọi là giải thuật Euclid).

Để kiếm tìm BCNN, sau thời điểm đã bao gồm UCLN ta chỉ vấn đề lấy tích A, B chia mang lại UCLN.

Giải thuật search UCLN với BCNN

Tìm UCLN bằng phương pháp 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ỏ tuổi hơn thân 2 số A và B.

Xem thêm: Những Câu Tán Tỉnh Hài Hước, 210+ Câu Tán Tỉnh Cực Dễ Thương

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 phần đông chia hết i giới hạn 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ởi 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 để đưa b thành a và ngược lại temp = b; b = a; a = temp; // sau khối lệnh, a khoác định vẫn là số được gắn ngay số lớn hơn, b là số nhỏ hơn int i = b; // i chạy tự b while(i >= 1) if(a%i == 0 && b%i == 0) // giả dụ a cùng b cùng 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ởi đệ quy


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

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

Thuật toán này còn có ý tưởng chừng như sau: lúc nào a != b thì mang số lớn hơn trừ mang lại số bé 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ố bằng nhau thì đó đó là ước chung bự nhất.

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

Minh họa lời giải 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) // nếu 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;
Minh 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); // giả dụ a > b hotline hàm đệ quay trở lại bài toán tính UCLN a-b và bif(aa hotline hàm đệ quay lại bài toán tính UCLN a với b-a

Thuật toán kiếm tìm UCLN thực hiện phép chia(giải thuật Euclid)

Có một bí quyết 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 cùng dư r.


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

Thuật toán này còn có độ phức hợp rất thấp bắt buộc thường được ưu tiên trong những 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 tra cứu ucln của b với r a = b; b = r; r = a % b; // r là phần dư của phép chia a/b return b;
Minh họa giải mã bằng đệ quy


int GCD(int a, int b)if(b==0) return a; //Sau đệ quy bây giờ kiểm tra b chính là a%b được truyền vào tức nó đó là r, còn a đó là b được truyền vàoreturn GCD(b, a%b); // call 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, với hàm Đệ quy này quan sát vào gồm thể các bạn sẽ không hình dung ra được thuật toán chạy ra có tác dụng sao…bạn cần thăm khảo thêm nội dung bài viết dưới đây.


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

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

Đầu tiên chúng ta hãy kiểm tra 1 lịch trình tính UCLN với 1 trong số thuật toán bên trên như sau.

Xem thêm: Bài Tập 1,2,3,4 Trang 77 Toán Lớp 5 Trang 77 Luyện Tập Sgk Toán 5 Trang 77


#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 công nghệ tính, thủ thuật năng lượng điện thoại, kiến thức và kỹ năng 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

gift4u.vn · đảm bảo nội dung vị DMCA.com Protection Status