Tìm Ước Chung Lớn Nhất Và Bội Chung Nhỏ Nhất Trong C

     
khóa đào tạo và huấn luyện Lập trình xây dựng C++ bài xích toán kinh khủng trong xây dựng Tìm ước số chung lớn số 1 và bội số chung nhỏ nhất của a với b
*

Mục tiêu

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

Mô tả bài toán

Viết công tác nhập vào 2 số nguyên dương a và b. Tìmước số chung bự nhất cùng bội số chung bé dại nhất của a cùng b.

Bạn đang xem: Tìm ước chung lớn nhất và bội chung nhỏ nhất trong c

Ví dụ:

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

Hướng dẫn

Định nghĩa

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

Bội số chung nhỏ dại nhấtcủa hai số nguyên a với b là số nguyên dương nhỏ tuổi nhất chia hết mang lại cảavàb.

Thuật toán

ƯCLN của nhì số rất 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 bao gồm 1 phương pháp tối ưu tuyệt nhất là sử dụngthuật toán Eucliddựa bên 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ới 287.

Trước hết rước 287 (số to 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 chia 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 bởi 91 với 14 cũng phân chia hết vị 91*3 + 14 = 287. Bởi vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán 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 và 7 sẽ tiến hành dùng mang đế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: Năm Bệnh Pháp Phòng Trừ Tổng Hợp Dịch Hại Cây Trồng Gồm Mấy Đặc Điểm

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à rèn luyện với những bàn toán xây dựng cơ bạn dạng trong C++.

Kteamkhuyến khích chúng ta tựphân tích đề bài bác > từ bỏ giải câu hỏi > debugđể kiểm tra tác dụng và fix lỗi trong quá 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 cấp 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 ở mụcHỏi & Đáp.


Source code tham khảo

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

Hoặc tham khảo thêm các bài tập khác trong khóa Bài toán bom tấn 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: Soạn Văn Bài Tinh Thần Yêu Nước Của Nhân Dân Ta (Cánh Diều), Soạn Bài Tinh Thần Yêu Nước Của Nhân Dân Ta

Thảo luận

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