DATA STRUCTURE AND ALGORITHM
Recursive Euclid Algorithm
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Thực hiệu thuật toán Euclid bằng đệ qui
Dr. Dao Nam Anh

Data Structure and Algorithm

1


Resource - Reference
Slides adapted from Robert Sedgewick,
and Kevin Wayne.
Major Reference:

•

Robert Sedgewick, and Kevin Wayne, “Algorithms”
Princeton University, 2011, Addison Wesley

•

Algorithm in C (Parts 1-5 Bundle)- Third Edition by
Robert Sedgewick, Addison-Wesley

Data Structure and Algorithm

2

Recursive Euclid Algorithm
Tìm ước số chung lớn nhất của hai số nguyên
public class Euclid {
public static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
public static void main(String[] args) {
int p = Integer.parseInt(args[0]);
int q = Integer.parseInt(args[1]);
System.out.println(gcd(p, q));
}
}

Data Structure and Algorithm

3


p = 1272, q = 216
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm


4


p = 1272, q = 216
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

5


p = 1272, q = 216
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

6



p = 1272, q = 216
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

1272 = 216  5 + 192

p = 216, q = 192
environment

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

7


p = 1272, q = 216
environment

p = 216, q = 192

environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

8


p = 1272, q = 216
environment

p = 216, q = 192
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}


gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

9


p = 1272, q = 216
environment

p = 216, q = 192
environment

p = 192, q = 24
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;

else return gcd(q, p % q);
}

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

10


p = 1272, q = 216
environment

p = 216, q = 192
environment

p = 192, q = 24
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(216, 192)

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

11


p = 1272, q = 216
environment

p = 216, q = 192
environment

p = 192, q = 24
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}


gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

12


p = 1272, q = 216
environment

p = 216, q = 192
environment

p = 192, q = 24
environment

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);

}
gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

p = 24, q = 0
environment

gcd(1272, 216)

gcd(24, 0)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

13


p = 1272, q = 216

environment

p = 216, q = 192
environment

p = 192, q = 24
environment

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

p = 24, q = 0
environment

gcd(1272, 216)

gcd(24, 0)

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

14


p = 1272, q = 216
environment

p = 216, q = 192
environment

p = 192, q = 24
environment

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(192, 24)

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

p = 24, q = 0
environment

gcd(1272, 216)

gcd(24, 0)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

Data Structure and Algorithm

15


p = 1272, q = 216
environment

p = 216, q = 192
environment

p = 192, q = 24
environment


gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

Data Structure and Algorithm

16


p = 1272, q = 216
environment

p = 216, q = 192
environment


p = 192, q = 24
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

gcd(192, 24)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

Data Structure and Algorithm

17


p = 1272, q = 216

environment

p = 216, q = 192
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

Data Structure and Algorithm

18


p = 1272, q = 216
environment

p = 216, q = 192
environment

gcd(1272, 216)

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

gcd(216, 192)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

Data Structure and Algorithm

19


p = 1272, q = 216
environment

gcd(1272, 216)
static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
24

Data Structure and Algorithm


20


p = 1272, q = 216

gcd(1272, 216)

environment

static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}24

public class Euclid {
public static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}

}

public static void main(String[] args) {
int p = Integer.parseInt(args[0]);
24
int q = Integer.parseInt(args[1]);
System.out.println(gcd(p, q));
}
24
% java Euclid 1272 216

24

Data Structure and Algorithm

21