Thuật toán tìm ước chung lớn nhất

Kchất hóa học Lập trình Lập trình C++ Bài toán kinh điển vào thiết kế Tìm ước số tầm thường lớn nhất với bội số chung nhỏ tốt 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 đơn giản và dễ dàng, phương pháp sử dụng:

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

Viết chương trình nhập vào 2 số nguyên dương a với b. Tìm ước số tầm thường béo nhất với bội số thông thường nhỏ dại nhất của a cùng b.

You watching: Thuật toán tìm ước chung lớn nhất

Ví dụ:

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

Hướng dẫn

Định nghĩa

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

Bội số thông thường bé dại nhấtcủa hai số nguim a và b là số ngulặng dương nhỏ nhất chia hết mang đến cảavàb.

Thuật toán

ƯCLN của hai số hoàn toàn có thể tìm kiếm được bởi việc đối chiếu hai số kia ra vượt số nguyên tố. Nhưng có 1 phương pháp tối ưu độc nhất là sử dụng thuật toán thù Euclid dựa vào dãy tiếp tục những phnghiền phân chia bao gồm dư.

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

Trước không còn rước 287 (số to hơn vào 2 số)chiamang đến 91:

287 =91*3 +14(91 & 14 sẽ tiến hành cần sử 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ị 287 cùng 91 cũng sẽchia hếtbởi 287 - 91*3 = 14. Tương trường đoản cú,số chiahết vày 91 cùng 14 cũng phân chia không còn bởi 91*3 + 14 = 287. Do đó, Ư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 chiakhông cònsố dưnhư sau:

91 =14*6 +7(14 và 7 sẽ được cần sử dụng cho 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).

See more: Đối Thủ Cạnh Tranh Của Coca Cola, Phân Tích Nghành Và Đối Thủ Cạnh Tranh

BCNN của a, b được xem 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, cung cấp chúng ta làm cho thân quen và rèn luyện cùng với những bàn toán xây dựng cơ bản vào C++.

Kteamkhuyến khích các bạn tựso sánh đề bài xích > tự giải bài bác tân oán > debugđể chất vấn công dụng cùng fix lỗi trong quy trình giải. Sau kia, bạn cũng có thể tđê mê khảosource codemẫu mã để hoàn hảo bài xích tập.

Để được cung cấp tốt nhất, chúng ta cũng có thể đặt câu hỏi sống phầnbình luậndưới bài viết hoặc nghỉ ngơi mụcHỏi & Đáp.


Source code tham mê khảo

#include using namespace std;// Cho 2 số nguim dương a và b. Hãy tra cứu ước bình thường lớn nhất của 2 số này.// Input : 2 số a,b// đầu ra : Ướ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ố nguyên ổn dương a và b. Hãy tìm kiếm bội tầm thường nhỏ tuổi độc nhất của 2 số này// Input : 2 số a,b// Output : Bội phổ biến 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 rất có thể củng núm kỹ năng C++ tự khóa Lập trình C++ cơ phiên bản.

Hoặc đọc thêm những bài tập khác vào khóa Bài tân oán bom tấn vào lập trình

Cảm ơn các 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 khách hàng để phát lên 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: Ba Quy Luật Của Phép Biện Chứng Duy Vật, Phân Tích 03 Quy Luật Của Phép Biện Chứng Duy Vật

Thảo luận

Nếu chúng ta tất cả ngẫu nhiên trở ngại tốt thắc mắc gì về khóa đào tạo và huấn luyện, đừng rụt rè đặt thắc mắc trong phần BÌNH LUẬN dưới hoặc vào mục HỎI & ĐÁPhường bên trên tlỗi viện ionline2017.com.com để cảm nhận sự hỗ trợ từ xã hội.


Chuyên mục: Blog