Зміст курсу
Greedy Algorithms using Python
Greedy Algorithms using Python
Euclidean Algorithm
Let’s create a Euclidean algorithm for searching x and y for some integers a and b that
ax + by = gcd(a,b),
where gcd() is the greatest common divisor of a and b.
Searching for gcd(a,b)
We’ll use the fact that gcd(a, b) = gcd(b, a-b), where a >= b. Let’s be greedy and subtract each time as much as possible. The result will be:
gcd(a, b) = gcd(b, a%b)
The algorithm of gcd(a, b) stops when b=0, and the answer is a.
Euclidean Algorithm Realization
Let x and y be the solution of equation ax+by = gcd(a,b) and x1 and y1 are soltion for gcd(b, a%b) = b * x1+a%b*y1. After changing we'll get that `gcd(b, a%b) = b * x1+a%by1 = bx1 + (a - b*a//b)*y1 = ay1 + b(x1-a//b*y1).
Since gcd(a,b) = gcd(b, a%b), multipliers near a and b are equal, so:
x = y1
y = x1-a//b*y1.
We'll use this fact in the algorithm.
Завдання
Complete the Euclidean Algorithm and test it.
Завдання
Complete the Euclidean Algorithm and test it.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Euclidean Algorithm
Let’s create a Euclidean algorithm for searching x and y for some integers a and b that
ax + by = gcd(a,b),
where gcd() is the greatest common divisor of a and b.
Searching for gcd(a,b)
We’ll use the fact that gcd(a, b) = gcd(b, a-b), where a >= b. Let’s be greedy and subtract each time as much as possible. The result will be:
gcd(a, b) = gcd(b, a%b)
The algorithm of gcd(a, b) stops when b=0, and the answer is a.
Euclidean Algorithm Realization
Let x and y be the solution of equation ax+by = gcd(a,b) and x1 and y1 are soltion for gcd(b, a%b) = b * x1+a%b*y1. After changing we'll get that `gcd(b, a%b) = b * x1+a%by1 = bx1 + (a - b*a//b)*y1 = ay1 + b(x1-a//b*y1).
Since gcd(a,b) = gcd(b, a%b), multipliers near a and b are equal, so:
x = y1
y = x1-a//b*y1.
We'll use this fact in the algorithm.
Завдання
Complete the Euclidean Algorithm and test it.
Завдання
Complete the Euclidean Algorithm and test it.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Euclidean Algorithm
Let’s create a Euclidean algorithm for searching x and y for some integers a and b that
ax + by = gcd(a,b),
where gcd() is the greatest common divisor of a and b.
Searching for gcd(a,b)
We’ll use the fact that gcd(a, b) = gcd(b, a-b), where a >= b. Let’s be greedy and subtract each time as much as possible. The result will be:
gcd(a, b) = gcd(b, a%b)
The algorithm of gcd(a, b) stops when b=0, and the answer is a.
Euclidean Algorithm Realization
Let x and y be the solution of equation ax+by = gcd(a,b) and x1 and y1 are soltion for gcd(b, a%b) = b * x1+a%b*y1. After changing we'll get that `gcd(b, a%b) = b * x1+a%by1 = bx1 + (a - b*a//b)*y1 = ay1 + b(x1-a//b*y1).
Since gcd(a,b) = gcd(b, a%b), multipliers near a and b are equal, so:
x = y1
y = x1-a//b*y1.
We'll use this fact in the algorithm.
Завдання
Complete the Euclidean Algorithm and test it.
Завдання
Complete the Euclidean Algorithm and test it.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Let’s create a Euclidean algorithm for searching x and y for some integers a and b that
ax + by = gcd(a,b),
where gcd() is the greatest common divisor of a and b.
Searching for gcd(a,b)
We’ll use the fact that gcd(a, b) = gcd(b, a-b), where a >= b. Let’s be greedy and subtract each time as much as possible. The result will be:
gcd(a, b) = gcd(b, a%b)
The algorithm of gcd(a, b) stops when b=0, and the answer is a.
Euclidean Algorithm Realization
Let x and y be the solution of equation ax+by = gcd(a,b) and x1 and y1 are soltion for gcd(b, a%b) = b * x1+a%b*y1. After changing we'll get that `gcd(b, a%b) = b * x1+a%by1 = bx1 + (a - b*a//b)*y1 = ay1 + b(x1-a//b*y1).
Since gcd(a,b) = gcd(b, a%b), multipliers near a and b are equal, so:
x = y1
y = x1-a//b*y1.
We'll use this fact in the algorithm.
Завдання
Complete the Euclidean Algorithm and test it.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів