Tìm ước chung của 2 số

Khóa học Lập trình Lập trình C++ Bài toán kinh điển trong thiết kế Tìm ước số bình thường lớn nhất và bội số phổ biến nhỏ duy nhất của a cùng b
*

Mục tiêu

Làm quen bí quyết viết các lịch trình đơn giản, cách sử dụng:

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

Viết lịch trình nhập vào 2 số ngulặng dương a cùng b. Tìmước số phổ biến lớn nhấtbội số tầm thường nhỏ tuổi nhất của a cùng b.

You watching: Tìm ước chung của 2 số

Ví dụ:

Input:a = 30 b = 40 Output:UCLN = 10 BCNN = 1trăng tròn

Hướng dẫn

Định nghĩa

Ước thông thường bự nhấtcủa nhị số nguim a cùng b là số nguyên dương lớn nhất màavàb phân chia hết.

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

Thuật toán

ƯCLN của hai số rất có thể tìm kiếm được bởi vấn đề đối chiếu hai số đó ra thừa số nguyên tố. Nhưng có 1 phương thức tối ưu tốt nhất là sử dụngthuật toán thù Eucliddựa trên hàng tiếp tục những phnghiền phân chia bao gồm dư.

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

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

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

Nhận xét: ngẫu nhiên số nào phân chia không còn bởi 287 với 91 cũng sẽphân tách hếtbởi 287 - 91*3 = 14. Tương từ bỏ,số chiakhông còn vì 91 với 14 cũng phân tách hết bởi vì 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán biến chuyển tra cứu ƯSCLN(91,14). Lặp lạiquy trìnhbên trên cho tới khiphnghiền chiako 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ư, xong, 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).

See more: Bạn Có Biết : Máy Chủ Là Gì? Sever Na Là Gì ? Sever Là Gì? Learn To Speak Vietnamese For Czech Speakers

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 ý nghĩa tham khảo, hỗ trợ các bạn làm cho thân quen và luyện tập cùng với những bàn toán thiết kế cơ phiên bản vào C++.

Kteamkhuyến nghị chúng ta tựphân tích đề bài bác > từ bỏ giải bài tân oán > debugđể bình chọn hiệu quả với fix lỗi vào quy trình giải. Sau đó, chúng ta có thể tđắm đuối khảosource codemẫu để hoàn hảo bài tập.

Để được cung ứng rất tốt, bạn có thể đặt thắc mắc nghỉ ngơi phầnbình luậndưới nội dung bài viết hoặc sinh hoạt mụcHỏi & Đáp.


Source code tsi mê khảo

#include using namespace std;// Cho 2 số ngulặng dương a với b. Hãy kiếm tìm ước phổ biến lớn số 1 của 2 số này.// Input : 2 số a,b// Output đầu ra : Ướ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// Cho 2 số nguyên dương a với b. Hãy tìm kiếm bội phổ biến bé dại nhất của 2 số này// Input : 2 số a,b// Output đầu ra : Bội thông thường 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

Quý Khách có thể củng cầm kỹ năng và kiến thức C++ trường đoản cú khóa Lập trình C++ cơ bạn dạng.

Hoặc tìm hiểu thêm những bài bác tập khác vào khóa Bài toán kinh khủng vào 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 mua hàng để tiến tới bài viết giỏi hơn. Đừng quên“Luyện tập – Thử thách – Không ngại khó”.

See more: Mẫu Đơn Ủy Quyền Nhận Bằng Tốt Nghiệp File Word 2021, Mẫu Giấy Ủy Quyền Nhận Bằng Tốt Nghiệp Mới Nhất

Thảo luận

Nếu các bạn gồm bất kỳ khó khăn giỏi thắc mắc gì về khóa đào tạo, đừng e dè đặt câu hỏi vào phần BÌNH LUẬN bên dưới hoặc vào mục HỎI và ĐÁP trên tlỗi viện ehefs.org.com nhằm nhận ra sự hỗ trợ trường đoản cú cộng đồng.