Mục tiêu
Làm quen cách viết những chương trình đối kháng giản, biện pháp sử dụng:
Mô tả bài bác toán
Viết lịch trình nhập vào 2 số nguyên dương a với b. Tìmước số chung to nhất cùng bội số chung bé dại nhất của a với b.
Ví dụ:
Input:a = 30 b = 40 Output:UCLN = 10 BCNN = 120Hướng dẫn
Định nghĩa
Ước chung to 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 bé dại nhấtcủa hai số nguyên a và b là số nguyên dương bé dại nhất phân chia hết mang đến cảavàb.
Thuật toán
ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố. Nhưng tất cả 1 phương thức tối ưu duy nhất là sử dụngthuật toán Eucliddựa trên dãy tiếp tục các phép chia bao gồm dư.
Ví dụ: Tínhước số chung bự nhấtcủa 91 với 287.
Trước hết lấy 287 (số lớn hơn trong 2 số)chiacho91:
287 =91*3 +14(91 & 14 sẽ tiến hành dùng mang đến vòng lặp kế)Nhận xét: ngẫu nhiên số nào chia hết do 287 cùng 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 phân tách hết vì chưng 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Việc 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 & 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).
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 thân quen và luyện tập với những bàn toán lập trình sẵn cơ bạn dạng 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 kết quả và fix lỗi trong quy 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 ứng tốt nhất, chúng ta cũng có thể đặt câu hỏi ở 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 cùng b. Hãy tìm ước chung lớn nhất của 2 số này.// input đầu vào : 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à b. Hãy tra cứu bội chung nhỏ dại nhất của 2 số này// input : 2 số a,b// output đầ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 rất có thể củng cố kỹ năng và kiến thức C++ trường đoản cú khóa Lập trình C++ cơ bản.Hoặc xem thêm các bài tập không giống trong khóa Bài toán kinh điể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ó”.
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 ngần ngại đặ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 giasuviet.edu.vn.com để nhận thấy sự cung cấp từ cùng đồng.
