Khóa học Lập trình Lập trình C++ Bài toán bom tấn trong lập trình Tìm ước số chung lớn số 1 cùng bội số bình thường nhỏ tuổi độc nhất của a với b


*

Mục tiêu

Làm quen giải pháp viết các công tác đơn giản và dễ dàng, biện pháp sử dụng:

Mô tả bài toán

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

Bạn đang xem: Tìm bội chung nhỏ nhất trong c

quý khách hàng đang xem: Tìm bội tầm thường nhỏ tuổi tuyệt nhất của 2 số

Ví dụ:

Input:a = 30 b = 40 Output:UCLN = 10 BCNN = 1đôi mươi

Hướng dẫn

Định nghĩa

Ước tầm thường lớn nhấtcủa hai số ngulặng a cùng b là số nguim dương lớn số 1 màavàb chia hết.

Bội số chung nhỏ tuổi nhấtcủa nhì số nguim a cùng b là số ngulặng dương nhỏ tốt nhất phân tách không còn đến cảavàb.

Thuật toán

ƯCLN của hai số có thể tìm kiếm được bằng Việc đối chiếu hai số kia ra vượt số ngulặng tố. Nhưng có 1 phương thức về tối ưu tốt nhất là sử dụngthuật toán thù Eucliddựa vào hàng tiếp tục những phxay phân chia có dư.

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

Trước hết rước 287 (số to hơn trong 2 số)chiacho91:

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

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

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

14 =7*2 (không hề số dư, xong xuôi, 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).

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 tham khảo, cung ứng các bạn có tác dụng quen thuộc và luyện tập với các bàn toán thù thiết kế cơ phiên bản vào C++.

Kteamkhuyến nghị chúng ta tựso với đề bài > tự giải bài bác toán > debugđể bình chọn kết quả cùng fix lỗi trong quá trình giải. Sau kia, chúng ta có thể tsi mê khảosource codemẫu mã nhằm hoàn chỉnh bài tập.

Để được hỗ trợ rất tốt, bạn có thể đặt câu hỏi ở phầnbình luậndưới bài viết hoặc ở mụcHỏi & Đáp.

Source code ttê mê khảo

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

Hoặc xem 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 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 để 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ó”.

Xem thêm: Kinh Nghiệm Xin Visa Du Lịch Úc Tự Túc, Thủ Tục & Kinh Nghiệm Xin Visa Úc 600

Thảo luận

Nếu chúng ta gồm ngẫu nhiên khó khăn tuyệt vướng mắc gì về khóa đào tạo, chớ e dè đặt thắc mắc trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI và ĐÁP bên trên thư viện pesleague.vn.com để cảm nhận sự cung cấp từ cộng đồng.