Mục tiêu
Làm quen biện pháp viết các chương trình đối kháng giản, giải pháp sử dụng:
Mô tả bài bác 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 mập nhất với bội số chung bé dại nhất của a cùng b.
Bạn đang xem: Thuật toán bội chung nhỏ nhất
Ví dụ:
Input:a = 30 b = 40 Output:UCLN = 10 BCNN = 120Hướng dẫn
Định nghĩa
Ước chung khủng nhấtcủa hai số nguyên a với b là số nguyên dương lớn nhất màavàb phân tách hết.
Bội số chung nhỏ tuổi nhấtcủa nhị số nguyên a và b là số nguyên dương nhỏ dại nhất phân tách hết mang đến 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ố đó ra quá số nguyên tố. Nhưng có 1 cách thức tối ưu duy nhất là sử dụngthuật toán Eucliddựa bên trên dãy tiếp tục các phép chia gồm dư.
Ví dụ: Tínhước số chung phệ nhấtcủa 91 với 287.
Trước hết lấy 287 (số to hơn trong 2 số)chiacho91:
287 =91*3 +14(91 & 14 sẽ được dùng mang đến vòng lặp kế)Nhận xét: ngẫu nhiên số nào phân chia hết vì chưng 287 và 91 cũng sẽchia hếtbởi 287 - 91*3 = 14. Tương tự,số chiahết vày 91 cùng 14 cũng phân tách hết vì chưng 91*3 + 14 = 287. Vị đó, Ư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 và 7 sẽ được 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: Phim Lan Quế Phường 2 Full Hd, Lan Quế Phường 2, Lan Kwai Fong 2 2012
BCNN của a, b được tính dựa trên UCLN của 2 số kia 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à rèn luyện với những bàn toán xây dựng cơ bản trong C++.
Kteamkhuyến khích các bạn tựphân tích đề bài xích > trường đoản cú giải bài toán > debugđể kiểm tra kết quả 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, chúng ta 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 mong chung lớn số 1 của 2 số này.// đầ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ới b. Hãy tìm bội chung nhỏ dại nhất của 2 số này// input đầu vào : 2 số a,b// đầ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ố kỹ năng và kiến thức C++ từ bỏ khóa Lập trình C++ cơ bản.Hoặc tham khảo thêm các bài bác 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 – ko ngại khó”.
Thảo luận
Nếu chúng ta 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 và ĐÁP trên thư viện baoveangiang.com.com để nhận được sự cung cấp từ cùng đồng.