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

Mục tiêu

Làm quen cách viết các chương trình solo giản, phương pháp sử dụng:

Mô tả bài xích toán

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

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

Ví dụ:

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

Hướng dẫn

Định nghĩa

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

Bội số chung bé dại nhấtcủa nhì số nguyên a và b là số nguyên dương nhỏ tuổi nhất phân tách hết cho cảavàb.

Thuật toán

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

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

Trước hết đem 287 (số to hơn trong 2 số)chiacho91:

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

Nhận xét: ngẫu nhiên số nào chia hết bởi 287 cùng 91 cũng sẽchia hếtbởi 287 - 91*3 = 14. Tương tự,số chiahết vị 91 và 14 cũng phân tách hết do 91*3 + 14 = 287. Bởi vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Việc trở thành tìm kiếm Ư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 mang lại 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).

BCNN của a, b được tính dựa trên 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à luyện tập với các 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 vấn đề > debugđể kiểm tra tác dụng và fix lỗi trong quy trình giải. Sau đó, chúng ta có thể tham khảosource codemẫu để hoàn chỉnh bài tập.

Để được cung cấp tốt nhất, bạn có thể đặt thắc mắc ở phầnbình luậnbên dưới nội dung bài viết hoặc làm việc mụcHỏi & Đáp.


Source code tham khảo

#include using namespace std;// mang đến 2 số nguyên dương a và b. Hãy tìm mong chung lớn số 1 của 2 số này.// đầu vào : 2 số a,b// đầu ra : Ướ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 lại 2 số nguyên dương a cùng b. Hãy tìm bội chung bé dại nhất của 2 số này// input đầu vào : 2 số a,b// đầ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 có thể củng cố kiến thức C++ trường đoản cú khóa Lập trình C++ cơ bản.

Hoặc tham khảo thêm các bài xích 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 – không ngại khó”.

Xem thêm: Tài Liệu Ôn Cấp Tốc Lý Thuyết Lý 12 Ôn Thi Đại Học, Ôn Thi Cấp Tốc Lý Thuyết Vật Lý 12

Thảo luận

Nếu bạn có bất kỳ khó khăn hay vướng mắc gì về khóa học, đừng rụt rè đặt thắc mắc trong phần BÌNH LUẬN dưới hoặc trong mục HỎI và ĐÁP trên thư viện girbakalim.net.com để cảm nhận sự hỗ trợ từ cộng đồng.