Khóa học Lập trình Lập trình C++ Bài tân oán bom tấn trong lập trình Tìm ước số chung lớn số 1 và bội số thông thường nhỏ tốt nhất của a với b
*

Mục tiêu

Làm thân quen phương pháp viết những lịch trình đơn giản dễ dàng, giải pháp sử dụng:

Mô tả bài xích toán

Viết chương trình nhtràn lên 2 số nguyên dương a và b. Tìmước số chung to nhấtbội số chung bé dại nhất của a với b.

Bạn đang xem: Bài 4

Ví dụ:

Input:a = 30 b = 40 Output:UCLN = 10 BCNN = 120

Hướng dẫn

Định nghĩa

Ước thông thường to nhấtcủa nhị số ngulặng a cùng b là số nguyên ổn dương lớn nhất màavàb phân tách hết.

Bội số phổ biến nhỏ dại nhấtcủa nhị số nguim a cùng b là số nguim dương nhỏ độc nhất vô nhị chia không còn cho cảavàb.

Thuật toán

ƯCLN của nhị số có thể tìm kiếm được bằng vấn đề đối chiếu nhì số kia ra thừa số nguyên ổn tố. Nhưng có 1 phương thức buổi tối ưu tốt nhất là sử dụngthuật toán Eucliddựa vào dãy liên tiếp những phxay phân chia tất cả dư.

Ví dụ: Tínhước số chung to nhấtcủa 91 cùng 287.

Trước không còn rước 287 (số lớn hơn trong 2 số)chiacho91:

287 =91*3 +14(91 và 14 sẽ được dùng mang đến vòng lặp kế)

Nhận xét: bất kỳ số nào chia không còn bởi 287 cùng 91 cũng sẽphân tách hếtbởi 287 - 91*3 = 14. Tương trường đoản cú,số chiakhông còn do 91 với 14 cũng phân chia hết vì chưng 91*3 + 14 = 287. Do kia, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán biến hóa tìm ƯSCLN(91,14). Lặp lạiquy trìnhtrên cho tới khiphép chiako cònsố dưnhư sau:

91 =14*6 +7(14 và 7 sẽ tiến hành dùng cho vòng lặp kế)

14 =7*2 (không thể số dư, xong xuôi, nhận7làm cho 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ố kia theo công thức:

*

Bài tậpmang tính chất tham khảo, hỗ trợ chúng ta làm cho quen cùng luyện tập với những bàn toán lập trình cơ bạn dạng trong C++.

Kteamkhuyến khích các bạn tựđối chiếu đề bài xích > từ giải bài xích toán > debugđể kiểm tra tác dụng với fix lỗi trong quy trình giải. Sau kia, bạn có thể tyêu thích khảosource codechủng loại nhằm hoàn chỉnh bài xích tập.

Để được hỗ trợ rất tốt, bạn cũng có thể đặt thắc mắc sinh sống phầnbình luậndưới bài viết hoặc ở mụcHỏi và Đáp.


Source code tđắm đuối khảo

#include using namespace std;// Cho 2 số ngulặng dương a với b. Hãy tìm kiếm ước phổ biến lớn nhất của 2 số này.// Input : 2 số a,b// Output : Ước phổ biến 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// Cho 2 số ngulặng dương a và b. Hãy tra cứu bội tầm thường nhỏ dại duy nhất của 2 số này// Input : 2 số a,b// Output : 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 thế kiến thức C++ từ bỏ khóa Lập trình C++ cơ phiên bản.

Hoặc tìm hiểu thêm các bài bác tập không giống trong khóa Bài toán thù kinh điển trong lập trình

Cảm ơn các quý khách hàng đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của người tiêu dùng để tiến tới bài viết tuyệt hơn. Đừng quên“Luyện tập – Thử thách – Không ngại khó”.

Xem thêm: Các Dạng Bài Tập Nhân Đa Thức Với Đa Thức Lớp 8 Bài 2: Nhân Đa Thức Với Đa Thức

Thảo luận

Nếu bạn gồm bất kỳ khó khăn tốt thắc mắc gì về khóa đào tạo, đừng ngần ngại đặt câu hỏi vào phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁPhường trên thỏng viện hanvietfoundation.org.com để nhận ra sự cung ứng tự cộng đồng.