Problem
Donald Knuth, tác giả của “
Nghệ thuật lập trình”, coi thuật toán Euclid là thuật toán đầu tiên. Bởi vì, mặc dù thực tế là thuật toán đã được phát minh và sử dụng ngay cả trước
Euclid, người sống ở thế kỷ IV-III. BC (nó đã được đề cập bởi
Aristotle, người sống trước đó một thế kỷ), Euclid mô tả quá trình lặp đi lặp lại, đó là phù hợp với nghĩa hiện đại của từ "thuật toán".
"Thay số lớn hơn trong hai số bằng hiệu giữa số lớn hơn và số nhỏ hơn cho đến khi chúng bằng nhau. Đây là GCD."
Bản thân thuật toán Euclid đã quen thuộc với bất kỳ học sinh hiện đại nào. Bạn có thể xem mô tả toán học
tại đây. Implement
classic Thuật toán Euclid và định dạng nó dưới dạng một hàm
nod(a, b) lấy 2 số làm đầu vào và trả về ước chung lớn nhất của hai số này.
Không cần đầu vào hoặc đầu ra! Bạn chỉ cần thực hiện chức năng.
Запрещенные операторы: gcd;%