VIẾT CHƯƠNG TRÌNH TÌM ƯỚC CHUNG LỚN NHẤT

     
khóa huấn luyện Lập trình lập trình sẵn C++ bài bác toán bom tấn trong xây dựng Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của a với b
*

Mục tiêu

Làm quen biện pháp viết các chương trình đối chọi giản, phương pháp sử dụng:

Mô tả bài xích 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 béo nhất với bội số chung nhỏ nhất của a với b.

Bạn đang xem: Viết chương trình 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 lớn nhấtcủa nhì 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ỏ dại nhấtcủa hai số nguyên a cùng b là số nguyên dương nhỏ tuổi nhất chia hết cho 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 quá số nguyên tố. Nhưng gồm 1 phương pháp tối ưu tốt nhất là sử dụngthuật toán Eucliddựa trên dãy liên 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 mang 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 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 bởi 91 với 14 cũng phân tách hết bởi vì 91*3 + 14 = 287. Vì đó, ƯSCLN(91,287) = ƯSCLN(91,14). Câu hỏi trở thành tra cứu Ư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ẽ tiến hành dùng đế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: Hàm Đếm Dấu X Trong Excel : Đếm Các Ô Bằng X Hoặc Y, Hàm Countif

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

Kteamkhuyến khích chúng ta tựphân tích đề bài bác > từ bỏ giải việc > debugđể kiểm tra kết quả và fix lỗi trong quá trình giải. Sau đó, chúng ta 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 sống mụcHỏi và Đáp.


Source code tham khảo

#include using namespace std;// cho 2 số nguyên dương a cùng b. Hãy tìm cầu chung lớn nhất của 2 số này.// input : 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// mang lại 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 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 rất có thể củng cố kỹ năng và kiến thức C++ tự 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 – ko ngại khó”.

Xem thêm: Cách Nấu Món Ốc Om Chuối Đậu, Cách Nấu Ốc Om Chuối Đậu Chuẩn Vị Sì Sụp Ngày Mưa

Thảo luận

Nếu các bạn có ngẫu nhiên khó khăn hay vướng 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 trong mục HỎI và ĐÁP trên tủ sách gift4u.vn.com để cảm nhận sự cung cấp từ cùng đồng.