Thuật toán tìm ước chung lớn nhất của 2 số

     
Khóa học Lập trình Lập trình C++ Bài toán kinh khủng vào thiết kế Tìm ước số chung lớn nhất và bội số chung nhỏ dại nhất của a và b
*

Mục tiêu

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

Mô tả bài toán

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

Bạn đang xem: Thuật toán tìm ước chung lớn nhất của 2 số

Ví dụ:

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

Hướng dẫn

Định nghĩa

Ước tầm thường béo nhấtcủa nhì số ngulặng a và b là số nguyên dương lớn số 1 màavàb chia không còn.

Bội số thông thường nhỏ nhấtcủa hai số nguyên a và b là số ngulặng dương nhỏ nhất phân chia hết cho cảavàb.

Thuật toán

ƯCLN của hai số hoàn toàn có thể tìm được bởi câu hỏi phân tích hai số kia ra vượt số nguyên tố. Nhưng có một cách thức về tối ưu tốt nhất là sử dụng thuật toán Euclid dựa vào hàng liên tục các phnghiền phân tách gồm dư.

Ví dụ: Tínhước số tầm thường Khủng nhấtcủa 91 và 287.

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

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

Nhận xét: bất kỳ số như thế nào phân chia không còn vày 287 với 91 cũng sẽphân chia hếtvì chưng 287 - 91*3 = 14. Tương từ,số chiahết vì 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán biến hóa tra cứu ƯSCLN(91,14). Lặp lạiquy trìnhbên trên cho tới khiphép chiako cònsố dưnlỗi sau:

91 =14*6 +7(14 và 7 sẽ được sử dụng mang đến vòng lặp kế)

14 =7*2 (không còn số dư, hoàn thành, 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: Bé 3 Tuổi Ra Nhiều Mồ Hôi Đầu Nhiều Có Sao Không? Trẻ Ra Nhiều Mồ Hôi Đầu Khi Ngủ

BCNN của a, b được tính dựa vào UCLN của 2 số kia theo công thức:

*

Bài tậpmang tính xem thêm, cung cấp chúng ta làm cho thân quen cùng luyện tập với những bàn tân oán lập trình sẵn cơ bạn dạng vào C++.

Kteamkhuyến nghị chúng ta tựphân tích đề bài bác > từ giải bài toán thù > debugđể bình chọn tác dụng cùng fix lỗi vào quá trình giải. Sau đó, chúng ta có thể tđê mê khảosource codemẫu để hoàn chỉnh bài bác tập.

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


Source code tmê mệt khảo

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

Hoặc đọc thêm các bài bác tập khác trong khóa Bài toán thù kinh khủng trong lập trình

Cảm ơn các quý khách đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của người dù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ó”.

Thảo luận

Nếu các bạn tất cả bất kỳ khó khăn tốt vướng mắc gì về khóa huấn luyện, đừng ngần ngại đặt thắc mắc vào phần BÌNH LUẬN dưới hoặc trong mục HỎI & ĐÁP bên trên tlỗi viện daichientitan.vn.com nhằm nhận ra sự cung ứng trường đoản cú xã hội.