THUẬT TOÁN ƯỚC CHUNG LỚN NHẤT

     
khóa đào tạo Lập trình lập trình sẵn C++ bài xích toán bom tấn trong lập trình Tìm ước số chung lớn nhất và bội số chung nhỏ tuổi nhất của a và b
*

Mục tiêu

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

Bạn đang xem: Thuật toán ướ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ự nhấtcủa nhì số nguyên a và b là số nguyên dương lớn số 1 màavàb chia hết.

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

Thuật toán

ƯCLN của nhị số rất có thể tìm được bằng câu hỏi phân tích hai số kia ra thừa số nguyên tố. Nhưng gồm 1 phương thức tối ưu tuyệt nhất là sử dụngthuật toán Eucliddựa bên trên dãy liên tục các phép chia bao gồm dư.

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

Trước hết mang 287 (số to hơn trong 2 số)chiacho91:

287 =91*3 +14(91 và 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 tách hết vày 287 cùng 91 cũng sẽchia hếtbởi 287 - 91*3 = 14. Tương tự,số chiahết bởi vì 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Bởi vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm kiế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ẽ đượ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: Soạn Bài Rừng Xà Nu Theo Sách Giáo Khoa, Soạn Bài Rừng Xà Nu

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

Kteamkhuyến khích các bạn tựphân tích đề bài xích > tự giải việc > debugđể kiểm tra hiệu quả và fix lỗi trong quy trình giải. Sau đó, bạn có thể tham khảosource codemẫu để hoàn chỉnh bài tập.

Để được cung cấp tốt nhất, bạn cũng có thể đặt câu hỏi ở phầnbình luậnbên dưới bài viết hoặc ngơi nghỉ 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 mong chung lớn số 1 của 2 số này.// input đầu vào : 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// mang lại 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// đầ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ố kỹ năng C++ tự khóa Lập trình C++ cơ bản.

Hoặc đọc 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: Những Bài Văn Hay Lớp 2 Tả Về Người Thân (Bố Mẹ, Ông Bà, Anh Chị

Thảo luận

Nếu chúng ta có bất kỳ 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 dưới hoặc trong mục HỎI và ĐÁP trên tủ sách olympicmyviet.com.vn.com để nhận thấy sự hỗ trợ từ cùng đồng.