Viết Chương Trình Tìm Ước Chung Lớn Nhất

Đề bài

bài bác tập Python: Viết chương trình tìm ước số chung lớn nhất (USCLN) với bội số chung nhỏ nhất (BSCNN) của 2 số nguyên dương a và b nhập trường đoản cú bàn phím.

Bạn đang xem: Viết chương trình tìm ước chung lớn nhất

Định nghĩa

USCLN của 2 số nguyên dương a cùng b là một số k bự nhất, sao cho a cùng b đầy đủ chia hết đến k.

BSCNN của 2 số nguyên dương a với b là một số h bé dại nhất, làm thế nào cho h phân chia hết cho tất cả a với b.

lời giải

Một phương pháp đơn giản đề tìm USCLN của a cùng b là cẩn thận từ số nhỏ hơn trong 2 số a cùng b cho tới 1, khi gặp gỡ số nào đó mà cả a và b đông đảo chia hết mang đến nó thì đó đó là USCLN của a với b. Mặc dù vậy phương thức này chưa phải là tác dụng nhất.

Vào cố kỉnh kỷ 3 TCN, công ty toán học Euclid (phiên âm giờ Việt là Ơ-clit) đã sáng tạo ra một giải mã tìm USCLN của nhì số nguyên dương rất kết quả được điện thoại tư vấn là giải mã Euclid. Ví dụ về ý tưởng của bài xích toán, trả sử a to hơn b, lúc đó việc tính UCSLN của a với b đang được đem lại bài toán tính USCLN của a mod b với b vày USCLN(a, b) = USCLN(a mod b, b).

khi đã kiếm được USCLN thì việc tìm kiếm BSCNN của nhì số nguyên dương a cùng b khá đối chọi giản. Khi ấy BSCNN(a, b) = (a * b) / UCSLN(a, b).

1. Tìm kiếm USCLN cùng BSCNN của 2 số nguyên dương trong Python bằng giải mã Euclid

Ví dụ tiếp sau đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn số 1 (USCLN) với bội số chung bé dại nhất (BSCNN) của nhị số nguyên dương a với b bằng phương pháp sử dụng giải thuật Euclid.

""" * Tìm mong số chung lớn nhất (USCLN) * *
param a: số nguyên dương *
param b: số nguyên dương *
return USCLN của a và b"""def uscln(a, b): if (b == 0): return a; return uscln(b, a % b);""" * tìm bội số chung nhỏ nhất (BSCNN) * *
param a: số nguyên dương *
param b: số nguyên dương *
return BSCNN của a và b"""def bscnn(a, b): return int((a * b) / uscln(a, b));a = int(input("Nhập số nguyên dương a = "));b = int(input("Nhập số nguyên dương b = "));#tính USCLN của a cùng bprint("Ước số chung lớn nhất của", a, "và", b, "là:", uscln(a, b));#tính BSCNN của a cùng bprint("Bội số chung nhỏ dại nhất của", a, "và", b, "là:", bscnn(a, b));
Kết quả:

Nhập số nguyên dương a = 15Nhập số nguyên dương b = 20Ước số chung lớn số 1 của 15 và 20 là: 5Bội số chung nhỏ tuổi nhất của 15 và đôi mươi là: 60

2. Tìm USCLN cùng BSCNN của 2 số nguyên dương trong Python bằng phương pháp khác

""" * Tìm ước số chung lớn nhất (USCLN) * *
param a: số nguyên dương *
param b: số nguyên dương *
return USCLN của a với b"""def uscln(a, b): temp1 = a; temp2 = b; while (temp1 != temp2): if (temp1 > temp2): temp1 -= temp2; else: temp2 -= temp1; uscln = temp1; return uscln;""" * kiếm tìm bội số chung nhỏ nhất (BSCNN) * *
param a: số nguyên dương *


Xem thêm: Cho Hình Chóp Sabcd Có Đáy Là Hình Bình Hành Tâm O Hình Chóp S

param b: số nguyên dương *
return BSCNN của a và b"""def bscnn(a, b): return int((a * b) / uscln(a, b));a = int(input("Nhập số nguyên dương a = "));b = int(input("Nhập số nguyên dương b = "));#tính USCLN của a với bprint("Ước số chung lớn nhất của", a, "và", b, "là:", uscln(a, b));#tính BSCNN của a cùng bprint("Bội số chung nhỏ tuổi nhất của", a, "và", b, "là:", bscnn(a, b));
Kết quả:

Nhập số nguyên dương a = 15Nhập số nguyên dương b = 20Ước số chung lớn số 1 của 15 và trăng tròn là: 5Bội số chung nhỏ dại nhất của 15 và 20 là: 60
Giải thích hoạt động của chương trình trên: Trong công tác này, tôi nhập vào nhì số 15 và trăng tròn thì trình biên dịch sẽ thực thi hàm uscln() với công việc như sau:

Gán giá trị vươn lên là temp1 = 15 với temp2 = 20. khám nghiệm điều kiện phía bên trong while: vì 15 != 20 nên sẽ xúc tiến lệnh bên phía trong while. Từ bây giờ 15 trở về bước 3, chất vấn điều kiện bên phía trong while: do 15 != 5 đề nghị sẽ thực thi lệnh bên trong while. Bây giờ 15 > 5 buộc phải lệnh bên phía trong if sẽ tiến hành thực thi và lúc này biến temp1 = 10. quay trở về bước 3, soát sổ điều kiện bên trong while: vì chưng 10 != 5 đề nghị sẽ thực thi lệnh bên phía trong while. Hôm nay 10 > 5 đề xuất lệnh bên phía trong if sẽ được thực thi và bây giờ biến temp1 = 5. quay trở lại bước 3, soát sổ điều kiện bên phía trong while: bởi vì 5 == 5 nên sẽ không thực thi lệnh phía bên trong while. Vòng lặp kết thúc, trả về quý hiếm uscln = 5.
dãy số Fibonacci trong Python
Python - Liệt kê toàn bộ các số nguyên tố nhỏ dại hơn n
Recent Updates chuẩn bị Tết 2023 Rồi! - Còn từng nào ngày nữa là cho tết 2023?Vẽ tam giác Pascal trong PythonVẽ tam giác Floyd vào PythonVẽ tam giác hầu hết trong PythonBài tập vòng lặp vào PythonBài tập cai quản sinh viên trong PythonBài tập Python bao gồm lời giảiVẽ tam giác vuông cân nặng trong PythonCheck số thành phần trong PythonCách setup Python (Thiết lập môi trường)Hướng dẫn thiết kế Python cùng với EclipseHướng dẫn lập trình Python với PyCharm Community EditionHướng dẫn thiết kế Python cùng với Visual Studio Code
buoidienxanhha.com on facebook
học Lập Trình Online Miễn giá tiền - buoidienxanhha.com

Danh Sách bài học kinh nghiệm

học Java | Hibernate | Spring học tập Excel | Excel VBA học tập Servlet | JSP | Struts2 học C | C++ | C# học tập Python học SQL

bài xích Tập Có giải thuật

bài xích tập Java bài bác tập C bài tập C++ bài bác tập C# bài xích tập Python lấy ví dụ như Excel VBA

câu hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java 25 câu hỏi phỏng vấn servlet 75 thắc mắc phỏng vấn jsp 52 câu hỏi phỏng vấn Hibernate 70 câu hỏi phỏng vấn Spring 57 câu hỏi phỏng vấn SQL

Xem thêm: Cách Viết Phương Trình Đường Thẳng Đi Qua 2 Điểm Có Vd Từ A, Viết Phương Trình Đường Thẳng Đi Qua 2 Điểm

Scroll back to đứng đầu