Module: (Python) Chương trình con: Thủ tục và Hàm - 2


Problem

4/8

thuật toán Euclid

Theory Click to read/hide

Thuật toán Euclid

Thuật toán Euclid — BC hiệu quả" title="Algorithm">Thuật toán Để Tìm Ước chung lớn nhất  hai Số nguyên (hoặc chung đo  hai Dòng). Thuật toán được đặt tên theo Hy Lạp Toán Euclid (thế kỷ thứ 3 trước Công nguyên ), người đầu tiên mô tả nó theo phong cách VII và Xsách «Khởi đầu". Đây là một trong những thuật toán số lâu đời nhất được sử dụng ngày nay.

Ghi nhớ phép toán.

Ước chung lớn nhất của hai số tự nhiên (gcd) là số tự nhiên lớn nhất mà chúng chia hết.

Ví dụ: các số 12 và 18 có các ước chung là: 2, 3, 6. Ước chung lớn nhất là 6. Giá trị này được viết là: gcd(12, 18) = 6

Trong lập trình, có một số cách triển khai thuật toán Euclid. Dưới đây là mô tả về một trong số chúng ở dạng sơ đồ khối.


Hãy thử triển khai thuật toán này.

Problem

Viết hàm tính gcd của hai số.


Đầu vào
Chuỗi đầu vào chứa hai số tự nhiên được phân tách bằng dấu cách – a and b .

Dấu ấn
Chương trình sẽ xuất ra một số tự nhiên: GCD của các số đã cho.

 

Ví dụ
<đầu>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
# Đầu vào Đầu ra
1 14 21 7
Write the program below 
a, b = map(int, input().split())
print(NOD(a,b))

     

Program check result

To check the solution of the problem, you need to register or log in!