Tìm ước số chung lớn nhất

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ố chung lớn nhất với bội số phổ biến nhỏ dại duy nhất của a với b
*

Mục tiêu

Làm quen bí quyết viết những công tác dễ dàng, cách 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ất cùng bội số thông thường nhỏ dại nhất của a cùng b.

You watching: Tìm ước số 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 mập nhấtcủa hai số ngulặng a cùng b là số nguyên dương lớn số 1 màavàb phân tách hết.

Bội số phổ biến bé dại nhấtcủa nhì số nguyên ổn a với b là số ngulặng dương nhỏ dại tuyệt nhất chia hết cho cảavàb.

Thuật toán

ƯCLN của nhì số hoàn toàn có thể kiếm được bằng Việc phân tích nhị số kia ra thừa số nguim tố. Nhưng có 1 phương thức buổi tối ưu tuyệt nhất là áp dụng thuật toán Euclid dựa trên hàng thường xuyên những phxay chia tất cả dư.

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

Trước không còn mang 287 (số to hơn trong 2 số)chiamang đến 91:

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

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

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

14 =7*2 (không thể số dư, kết thúc, 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: Ngón Tay Thối - Vì Sao Ngón Giữa Bị Gọi Là

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 chất tìm hiểu thêm, hỗ trợ chúng ta làm cho thân quen và rèn luyện cùng với những bàn toán thiết kế cơ bạn dạng vào C++.

Kteamkhuyến nghị các bạn tựphân tích đề bài xích > từ bỏ giải bài toán > debugnhằm kiểm tra kết quả với fix lỗi vào quy trình giải. Sau đó, chúng ta cũng có thể tham khảosource codechủng loại để hoàn hảo bài tập.

Để được hỗ trợ tốt nhất, chúng ta có thể đặt thắc mắc làm việc phầnbình luậndưới nội dung bài viết hoặc ở mụcHỏi và Đáp.


Source code tyêu thích khảo

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

Hoặc xem thêm những bài xích tập không giống vào khóa Bài tân oán kinh điển trong lập trình

Cảm ơn các người mua 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 để tiến nhanh bài viết hay hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

See more: Các Môn Thi Đấu Thế Vận Hội Mùa Đông, Thế Vận Hội Mùa Đông

Thảo luận

Nếu bạn gồm ngẫu nhiên trở ngại tốt vướng mắc gì về khóa học, chớ ngần ngại đặt thắc mắc vào phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP.. trên thỏng viện twrising.com.com để cảm nhận sự cung ứng trường đoản cú xã hội.


Chuyên mục: Blog