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

bookEuclidean 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.

Tarea

Swipe to start coding

Complete the Euclidean Algorithm and test it.

Solución

¿Todo estuvo claro?

¿Cómo podemos mejorarlo?

¡Gracias por tus comentarios!

Sección 1. Capítulo 4
single

single

Pregunte a AI

expand

Pregunte a AI

ChatGPT

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Suggested prompts:

Resumir este capítulo

Explicar el código en file

Explicar por qué file no resuelve la tarea

close

Awesome!

Completion rate improved to 7.69

bookEuclidean Algorithm

Desliza para mostrar el menú

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.

Tarea

Swipe to start coding

Complete the Euclidean Algorithm and test it.

Solución

Switch to desktopCambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones
¿Todo estuvo claro?

¿Cómo podemos mejorarlo?

¡Gracias por tus comentarios!

close

Awesome!

Completion rate improved to 7.69
Sección 1. Capítulo 4
single

single

some-alt