Giải thuật euclid

Kchất hóa học Lập trình Lập trình C++ Bài toán thù bom tấn vào thiết kế Tìm ước số tầm thường lớn số 1 với bội số bình thường nhỏ dại nhất của a cùng b
*

Mục tiêu

Làm thân quen giải pháp viết những chương 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 lịch trình nhtràn lên 2 số nguim dương a và b. Tìm ước số phổ biến Khủng nhất với bội số thông thường nhỏ tuổi nhất của a cùng b.

You watching: Giải thuật euclid

Ví dụ:

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

Hướng dẫn

Định nghĩa

Ước phổ biến bự nhấtcủa hai số nguyên ổn a với b là số nguim dương lớn nhất màavàb phân chia hết.

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

Thuật toán

ƯCLN của hai số rất có thể tìm kiếm được bằng câu hỏi so với hai số kia ra quá số nguyên tố. Nhưng có 1 phương pháp tối ưu tốt nhất là áp dụng thuật toán Euclid dựa vào dãy thường xuyên những phxay chia tất cả dư.

Ví dụ: Tínhước số phổ biến mập nhấtcủa 91 với 287.

Trước hết đem 287 (số to hơn vào 2 số)chiacho 91:

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

Nhận xét: bất kỳ số nào phân chia hết vì chưng 287 và 91 cũng sẽchia hếtvì 287 - 91*3 = 14. Tương từ,số chiakhông còn vì chưng 91 cùng 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán thù biến hóa kiếm tìm ƯSCLN(91,14). Lặp lạiquy trìnhbên trên cho tới khiphép chiako cònsố dưnhỏng 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 kết quả)

Cuối cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

See more: Làm Thế Nào Để Ngăn Chặn Virus Hiệu Quả Cho Các Mẫu Điện Thoại Android? ?

BCNN của a, b được xem dựa trên UCLN của 2 số đó theo công thức:

*

Bài tậpmang ý nghĩa xem thêm, cung ứng chúng ta làm cho quen với rèn luyện cùng với những bàn toán lập trình cơ bạn dạng vào C++.

Kteamkhuyến nghị các bạn tựso với đề bài > trường đoản cú giải bài xích tân oán > debugđể soát sổ công dụng với fix lỗi vào quá trình giải. Sau kia, chúng ta có thể tđắm đuối khảosource codechủng loại nhằm hoàn hảo bài bác tập.

Để được hỗ trợ cực tốt, bạn có thể đặt câu hỏi nghỉ ngơi phầnbình luậnbên dưới nội dung bài viết hoặc ở mụcHỏi và Đáp.


Source code tsay mê khảo

#include using namespace std;// Cho 2 số ngulặng dương a và b. Hãy tra cứu ước chung lớn nhất của 2 số này.// Input : 2 số a,b// Output : Ước thông thường 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// Cho 2 số nguim dương a với b. Hãy tra cứu bội tầm thường nhỏ dại độc nhất vô nhị của 2 số này// Input : 2 số a,b// Output : 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

Quý Khách rất có thể củng cố gắng kỹ năng C++ tự khóa Lập trình C++ cơ bạn dạng.

Hoặc xem thêm các bài bác tập khác trong khóa Bài tân oán 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 quý khách hàng để phát lên bài viết giỏi rộng. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

See more: Nồi Cơm Điện Tử Toshiba Rc-10Nmfvn, Nồi Cơm Điện Tử Toshiba 1 Lít Rc

Thảo luận

Nếu các bạn bao gồm ngẫu nhiên khó khăn tốt vướng mắc gì về khóa đào tạo và huấn luyện, đừng e dè đặt thắc mắc trong phần BÌNH LUẬN bên dưới hoặc vào mục HỎI & ĐÁP.. trên thư viện peaceworld.com.vn.com để nhận thấy sự cung cấp tự xã hội.