- vừa được xem lúc

The Euclidean Algorithm

0 0 19

Người đăng: logbasex

Theo Viblo Asia

1. Introduction

Đây là một giải thuật để tính ước chung lớn nhất (GCD - Greatest Common Divisor) của hai số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với số dư bằng không.

Thuật toán Euclidean cho hai số nguyên A và B được mô tả bằng các bước như sau:

  1. Nếu A = 0 thì GCD (A, B) = B, vì GCD (0, B) = B, và chúng ta có thể dừng lại.
  2. Nếu B = 0 thì GCD (A, B) = A, vì GCD (A, 0) = A, và chúng ta có thể dừng lại.
  3. Biểu diễn A dưới dạng phần dư và thương số (A = B⋅Q + R)
  4. Tìm GCD(B,R) sử dụng thuật toán Euclidean vì GCD(A,B) = GCD(B,R)

Ví dụ tìm ước chung lớn nhất của 38 và 16.

visualize.png

euclidean-algorithm-1.png

euclidean-algorithm-2.png

euclidean-algorithm-3.png

euclidean-algorithm-4.png

euclidean-algorithm-5.png

2. Proof of correctness

Nếu khảo sát thuật toán này, chúng ta có thể thấy rằng, thuật toán Euclidean sử dụng những tính chất sau:

  • GCD(A,0) = A
  • GCD(0,B) = B
  • Nếu A = B⋅Q + RB ≠ 0 thì GCD(A,B) = GCD(B,R) nếu Q là một số nguyên, R là một số nguyên [0,B1]\in [0, B-1]

Hai tính chất đầu tiên cho phép chúng ta tìm ước chung lớn nhất nếu một trong hai số bằng 0, tính chất thứ ba cho phép chúng ta chuyển từ một vấn đề lớn hơn, khó giải quyết hơn thành một vấn đề nhỏ hơn, dễ giải quyết hơn. Thuật toán Euclidean sử dụng tính chất thứ 3 để nhanh chóng chuyển bài toán ban đầu về một bài toán đơn giản hơn cho đến khi nó có thể được giải quyết bằng cách sử dụng một trong hai tính chất đầu tiên.

Và để hiểu hơn thì chúng ta sẽ bắt tay vào việc chứng minh những tính chất nêu trên là đúng.

GCD(A,0)=A

  • Số nguyên lớn nhất A có thể chia hết chính là A
  • 0 chia hết cho A
  • 0 và A đều chia hết cho A nên GCD(A,0)=AGCD(A,0) = A

GCD(0,B)=B

  • Tương tự như trên nhưng thay A bằng B.

GCD(A,B)=GCD(B,R)

Để chứng minh bổ đề trên, trước hết chúng ta cần chứng minh bổ đề sau đây là đúng: GCD(A,B)=GCD(B,AB).GCD(A,B)=GCD(B,A-B).

image.png

Giả sử chúng ta có ba số nguyên A, B và C sao cho AB=CA-B = C

Ta có:

C=ABA=XGCD(A,B)B=YGCD(A,B)}C=(XY)GCD(A,B)\begin{rcases} C=A-B\\ A=X⋅GCD(A,B) \\ B=Y⋅GCD(A,B) \end{rcases}⇒C=(X - Y)⋅GCD(A,B)

=> C chia hết cho ước chung lớn nhất của A và B (1).

image.png

A=B+CB=MGCD(B,C)C=NGCD(B,C)}A=(M+N)GCD(B,C)\begin{rcases} A=B+C\\ B=M⋅GCD(B,C) \\ C=N⋅GCD(B,C) \end{rcases}⇒A=(M + N)⋅GCD(B,C)

=> A chia hết cho ước chung lớn nhất của B và C (2).

image.png

GCD(B,C) là ước chung lớn nhất của B và C (3).

GCD(A,B) là ước chung lớn nhất của A và B (4).

GCD(A,B)B,C (1)GCD(B,C)B,C (3)GCD(B,C)A,B (2)GCD(A,B)A,B (4)}\begin{rcases} GCD(A,B) \mid B, C&\ (1) \\ GCD(B,C) \mid B, C&\ (3)\\ GCD(B,C) \mid A,B&\ (2)\\ GCD(A,B) \mid A,B&\ (4) \end{rcases}⇒

(1)(3) GCD(B,C)GCD(A,B)(2)(4) GCD(A,B)GCD(B,C)}GCD(A,B)=GCD(B,C)GCD(A,B)=GCD(B,AB)\begin{rcases} (1)(3) &\ GCD(B,C) \geqslant GCD(A,B) \\ (2)(4) &\ GCD(A,B) \geqslant GCD(B,C) \end{rcases}⇒GCD(A,B) = GCD(B,C)⇒GCD(A,B) = GCD(B,A-B)

image.png

A=BQ+RGCD(A,B)=GCD(B,AB)=GCD(AB,B)}\begin{rcases} A = B⋅Q + R\\ GCD(A,B) = GCD(B,A-B) = GCD(A-B, B)\\ \end{rcases}⇒

A=BQ+RGCD(A,B)=GCD(AB,B)=GCD(A2B,B)}\begin{rcases} A = B⋅Q + R\\ GCD(A,B) = GCD(A - B,B) = GCD(A - 2B,B) \end{rcases}⇒

R=ABQGCD(A,B)=GCD(AB.Q,B)=GCD(R,B)}GCD(A,B)=GCD(B,R)\begin{rcases} R = A - B⋅Q\\ GCD(A,B) = GCD(A - B.Q,B) = GCD(R,B) \end{rcases}⇒ GCD(A,B) = GCD(B,R)

3. Reference

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán quay lui (Backtracking)

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

0 0 38

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 152

- vừa được xem lúc

Sử dụng vector trong lập trình C++ - giải bài toán lập trình muôn thủa

Chào buổi tối mọi người, hôm nay lang thang trên mạng bắt gặp bài toán quen thuộc một thời của quãng đường sinh viên IT. Đấy chính là câu số 1 trong đề thi dưới đây:.

0 0 35

- vừa được xem lúc

MÔ PHỎNG THUẬT TOÁN VƯƠNG HẠO TRONG PROLOG

. 1. Các luật suy diễn trong thuật toán Vương Hạo. Luật 1: Chuyển vế các giả thuyết và kết luận ở dạng phủ định. Ví dụ: p v q, !(r ^ s), !q, p v r -> s, !p <=> p v q, p v r, p -> s, r ^ s, q.

0 0 76

- vừa được xem lúc

A* Search Algorithm

What is A* Search Algorithm. How it works. . Explanation.

0 0 42

- vừa được xem lúc

Python: Jump Search

Search là một từ khóa khá là quen thuộc đối với chúng ta. Hiểu theo đúng nghĩa đen của nó chính là "Tìm kiếm".

0 0 35