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

Mục tiêu

Làm quen biện pháp viết những chương trình đơn giản, cách 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 cùng b. Tìmước số chung khủng nhất và bội số chung bé dại nhất của a với b.

Bạn đang xem: Thuật toán tìm ước chung lớn nhất

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 nhì số nguyên a với b là số nguyên dương lớn số 1 màavàb chia hết.

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

Thuật toán

ƯCLN của nhì số hoàn toàn có thể tìm được bằng việc phân tích nhị số đó ra quá số nguyên tố. Nhưng bao gồm 1 phương thức tối ưu độc nhất vô nhị là sử dụngthuật toán Eucliddựa trên dãy liên tiếp các phép chia gồm dư.

Ví dụ: Tínhước số chung béo nhấtcủa 91 với 287.

Trước hết rước 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: bất kỳ số nào phân tách hết bởi 287 với 91 cũng sẽchia hếtbởi 287 - 91*3 = 14. Tương tự,số chiahết vì 91 và 14 cũng phân chia hết do 91*3 + 14 = 287. Vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Vấn đề trở thành kiếm tì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).

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ợ chúng ta làm quen thuộc và luyện tập với những bàn toán thiết kế cơ bản trong C++.

Kteamkhuyến khích các bạn tựphân tích đề bài xích > từ bỏ giải vấn đề > debugđể kiểm tra công dụng 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 hảo 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 sống mụcHỏi và Đáp.


Source code tham khảo

#include using namespace std;// mang đến 2 số nguyên dương a và 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 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// mang đến 2 số nguyên dương a và b. Hãy tìm 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ỏ 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 hoàn toàn có thể củng cố kiến thức C++ trường đoản cú khóa Lập trình C++ cơ bản.

Hoặc tham khảo thêm các bài xích tập khác 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 – không ngại khó”.

Xem thêm: 6 Vị Trí Nốt Ruồi Ở Dái Tai Phải, Nam, Nữ Nói Lên Điều Gì Của Một Người ?

Thảo luận

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