BÀI TẬP VỀ ƯỚC CHUNG LỚN NHẤT VÀ BỘI CHUNG NHỎ NHẤT

     
khóa huấn luyện Lập trình lập trình sẵn C++ bài bác toán kinh điển trong thiết kế Tìm mong số chung lớn nhất và bội số chung bé 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 1-1 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 bự nhất cùng bội số chung nhỏ tuổi nhất của a và b.

Bạn đang xem: Bài tập về ước chung lớn nhất và bội chung nhỏ nhất

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ới 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 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 hai số hoàn toàn có thể tìm được bằng việc phân tích hai số kia ra quá số nguyên tố. Nhưng bao gồm 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 tiếp các phép chia tất cả dư.

Ví dụ: Tínhước số chung mập nhấtcủa 91 cùng 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 phân tách hết vị 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 cùng 14 cũng phân chia hết vì 91*3 + 14 = 287. Bởi đó, Ư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 đến 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: Đề Cương Ôn Tập Tiếng Anh Lớp 7 Học Kì 2 Năm 2021, Đề Cương Tiếng Anh Lớp 7 Học Kì 2 Năm Học 2021

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 quen và luyện tập với những bàn toán lập trình sẵn cơ bản trong C++.

Kteamkhuyến khích chúng ta tựphân tích đề bài > tự giải vấn đề > debugđể kiểm tra tác dụng và fix lỗi trong quá 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 hỗ trợ tốt nhất, bạn có thể đặt câu hỏi ở phầnbình luậnbên dưới bài viết hoặc sinh sống mụcHỏi và Đáp.


Source code tham khảo

#include using namespace std;// cho 2 số nguyên dương a với b. Hãy tìm ước chung lớn số 1 của 2 số này.// input : 2 số a,b// output đầu ra : Ước chung lớn số 1 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// cho 2 số nguyên dương a với b. Hãy 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ỏ 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 rất có thể củng cố kiến thức và kỹ năng C++ trường đoản cú 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: Giống Và Khác Nhau Giữa Bánh Mì Đen Làm Từ Gì ? Thành Phần Của Bánh Mì Đen?

Thảo luận

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