khóa đào tạo và huấn luyện Lập trình lập trình C++ bài toán bom tấn trong thiết kế Tìm mong 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 phương pháp viết những chương trình đối kháng 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ới b. Tìmước số chung mập nhất và bội số chung nhỏ dại nhất của a với b.
Bạn đang đọc: Bội chung nhỏ nhất c++
Bạn đã xem: tìm bội chung nhỏ dại 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 béo nhấtcủa hai số nguyên a cùng b là số nguyên dương lớn nhất màavàb phân chia hết.
Bội số chung nhỏ nhấtcủa nhì số nguyên a cùng b là số nguyên dương nhỏ nhất phân chia hết đến cảavàb.
Thuật toán
ƯCLN của hai số có thể tìm được bằng bài toán phân tích nhị số kia ra quá số nguyên tố. Nhưng gồm 1 cách thức tối ưu nhất là sử dụngthuật toán Eucliddựa trên dãy tiếp tục các phép chia tất cả dư.
Ví dụ: Tínhước số chung béo nhấtcủa 91 cùng 287.
Trước hết lấy 287 (số lớn hơn trong 2 số)chiacho91:
287 =91*3 +14(91 & 14 sẽ được dùng mang lại vòng lặp kế)
Nhận xét: ngẫu nhiên số nào phân chia hết vày 287 với 91 cũng sẽchia hếtbởi 287 – 91*3 = 14. Tương tự,số chiahết vì 91 cùng 14 cũng chia hết bởi 91*3 + 14 = 287. Vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Vấn đề trở thành search Ư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ẽ được dùng cho 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: Phim Hoạt Hình Đôrêmon Ngắn, Danh Sách Các Phim Dài Trong Doraemon
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 thuộc và rèn luyện với các bàn toán thiết kế cơ bạn dạng trong C++.
Kteamkhuyến khích chúng ta tựphân tích đề bài xích > từ bỏ giải việc > debugđể kiểm tra tác 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 chỉnh bài tập.
Để được hỗ trợ tốt nhất, bạn cũng có thể đặt thắc mắc ở phầnbình luậnbên dưới nội dung bài viết hoặc ở mụcHỏi và Đá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 số 1 của 2 số này.// input : 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// đến 2 số nguyên dương a cùng b. Hãy kiếm tìm bội chung nhỏ dại nhất của 2 số này// input đầu vào : 2 số a,b// output : 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 rất có thể củng cố kỹ năng C++ từ bỏ khóa Lập trình C++ cơ bản.
Hoặc xem thêm các bài xích tập không giống 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 – không ngại khó”.
Thảo luận
Nếu chúng ta có ngẫu nhiên khó khăn hay thắc mắc gì về khóa học, đừng rụt rè đặt câu hỏi trong phần BÌNH LUẬN dưới hoặc trong mục HỎI & ĐÁP trên tủ sách pesleague.vn.com để cảm nhận sự hỗ trợ từ cùng đồng.
