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

Mục tiêu

Làm quen biện pháp viết những chương trình đơn giản, giải 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 cùng b. Tìmước số chung khủng nhất với bội số chung nhỏ tuổi nhất của a với b.

Bạn đang xem: Bài 4

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 cùng b là số nguyên dương lớn số 1 màavàb phân tách hết.

Bội số chung bé dại nhấtcủa hai số nguyên a cùng b là số nguyên dương nhỏ nhất phân tách hết mang lại 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ố kia ra vượt số nguyên tố. Nhưng 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 liên tục các phép chia có dư.

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

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

287 =91*3 +14(91 & 14 sẽ được dùng cho vòng lặp kế)

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

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ợ chúng ta làm thân quen và luyện tập với các bàn toán lập trình cơ bạn dạng trong C++.

Kteamkhuyến khích các bạn tựphân tích đề bài bác > trường đoản cú giải bài toán > debugđể kiểm tra công dụng và fix lỗi trong quy trình giải. Sau đó, chúng ta cũng 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ũ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// đầ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 đến 2 số nguyên dương a và b. Hãy search bội chung nhỏ tuổi nhất của 2 số này// đầu vào : 2 số a,b// output đầu ra : Bội chung bé dại 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 và kỹ năng C++ tự khóa Lập trình C++ cơ bản.

Hoặc bài viết liên quan 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: Mã Trường Đại Học Luật Huế, Mã Ngành, Tổ Hợp Xét Tuyển Đại Học Luật

Thảo luận

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