Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Impara Euclidean Algorithm | Greedy Algorithms: Overview and Examples
Greedy Algorithms using Python
course content

Contenuti del Corso

Greedy Algorithms using Python

Greedy Algorithms using Python

1. Greedy Algorithms: Overview and Examples
2. Greedy on Arrays
3. Greedy on Graphs

book
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//by1).

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.

Compito

Swipe to start coding

Complete the Euclidean Algorithm and test it.

Soluzione

Switch to desktopCambia al desktop per esercitarti nel mondo realeContinua da dove ti trovi utilizzando una delle opzioni seguenti
Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 4
toggle bottom row

book
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//by1).

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.

Compito

Swipe to start coding

Complete the Euclidean Algorithm and test it.

Soluzione

Switch to desktopCambia al desktop per esercitarti nel mondo realeContinua da dove ti trovi utilizzando una delle opzioni seguenti
Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 4
Switch to desktopCambia al desktop per esercitarti nel mondo realeContinua da dove ti trovi utilizzando una delle opzioni seguenti
Siamo spiacenti che qualcosa sia andato storto. Cosa è successo?
some-alt