Thuật toán tìm ước chung lớn nhất của 2 số

khóa đào tạo Lập trình lập trình C++ bài bác toán kinh khủng trong lập trình Tìm mong số chung lớn số 1 và bội số chung nhỏ dại nhất của a với b

Mục tiêu

Làm quen phương pháp viết những chương trình đối kháng giản, giải pháp sử dụng:

Mô tả bài toán

Viết chương trình nhập vào 2 số nguyên dương a cùng b. Tìmước số chung khủng nhất với bội số chung nhỏ nhất của a cùng b.

Bạn đang xem: Thuật toán tìm ước chung lớn nhất của 2 số

Ví dụ:

Input:a = 30 b = 40 Output:UCLN = 10 BCNN = 120

Hướng dẫn

Định nghĩa

Ước chung phệ nhấtcủa nhị số nguyên a với b là số nguyên dương lớn nhất màavàb chia hết.

Bội số chung nhỏ nhấtcủa nhì số nguyên a và b là số nguyên dương nhỏ nhất chia hết đến cảavàb.

Thuật toán

ƯCLN của hai số có thể tìm được bằng vấn đề phân tích hai số kia ra vượt số nguyên tố. Nhưng bao gồm 1 phương pháp tối ưu tuyệt nhất là sử dụngthuật toán Eucliddựa trên dãy liên tục các phép chia gồm dư.

Ví dụ: Tínhước số chung phệ nhấtcủa 91 cùng 287.

Trước hết mang 287 (số lớn hơn trong 2 số)chiacho91:

287 =91*3 +14(91 và 14 sẽ tiến hành dùng cho vòng lặp kế)

Nhận xét: ngẫu nhiên số nào phân tách hết bởi vì 287 và 91 cũng sẽchia hếtbởi 287 - 91*3 = 14. Tương tự,số chiahết vì chưng 91 với 14 cũng phân tách hết vị 91*3 + 14 = 287. Bởi vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tra cứu ƯSCLN(91,14). Lặp lạiquy trìnhtrên cho tới khiphép chiakhông cònsố dưnhư sau:

91 =14*6 +7(14 & 7 sẽ tiến hành dùng đến vòng lặp kế)

14 =7*2 (không còn số dư, kết thúc, nhận7làm kết quả)

Cuối cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

Xem thêm: Bài 11 Trang 8 Sgk Toán 8 Tập 1, Chứng Minh Biểu Thức Không Phụ Thuộc Vào X

BCNN của a, b được tính dựa vào UCLN của 2 số đó theo công thức:

Bài tậpmang tính tham khảo, hỗ trợ các bạn làm quen và rèn luyện với những bàn toán thiết kế cơ phiên bản trong C++.

Kteamkhuyến khích các bạn tựphân tích đề bài bác > từ giải câu hỏi > debugđể kiểm tra công dụng và fix lỗi trong quy trình giải. Sau đó, bạn cũng có thể tham khảosource codemẫu để hoàn hảo bài tập.

Để được cung ứng tốt nhất, chúng ta cũng có thể đặt câu hỏi ở phầnbình luậnbên dưới bài viết hoặc nghỉ ngơi mụcHỏi & Đáp.

Source code tham khảo

#include using namespace std;// mang lại 2 số nguyên dương a với b. Hãy tìm mong chung lớn nhất của 2 số này.// input đầu vào : 2 số a,b// output : Ước chung lớn nhất của 2 số a, bint UCLN(int a, int b) while ( a != b) if (a > b) a = a - b; else b = b - a; return a; // or return b; a = b// mang đến 2 số nguyên dương a cùng b. Hãy kiếm tìm bội chung nhỏ nhất của 2 số này// input đầu vào : 2 số a,b// output đầu ra : Bội chung nhỏ nhấtint BCNN(int a, int b) int result = UCLN(a, b); return a * b / result;int main(){ int a, b; cout > a; cout > b; int result = UCLN(a, b); cout

Kết luận

Bạn hoàn toàn có thể củng cố kỹ năng và kiến thức C++ tự khóa Lập trình C++ cơ bản.

Hoặc tìm hiểu thêm các bài tập khác trong khóa Bài toán kinh khủng trong lập trình

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của bạn để phát triển bài viết tốt hơn. Đừng quên“Luyện tập – Thử thách – ko ngại khó”.

Xem thêm: Xin Tên Các Loài Hoa Đẹp Và Ý Nghĩa, Ý Nghĩa Các Loài Hoa

Thảo luận

Nếu bạn có ngẫu nhiên khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt thắc mắc trong phần BÌNH LUẬN dưới hoặc vào mục HỎI và ĐÁP trên thư viện goodsmart.com.vn.com để nhận ra sự cung cấp từ cùng đồng.