Algoritmo de Euclides: Una forma efectiva para encontrar máximo común divisor (MCD)

En este artículo, vamos a aprender lo que es euclidiana algoritmo ? Cómo calcular máximo común divisor de dos números utilizando el algoritmo de Euclides y el programa en Kotlin .

euclidiana algoritmo es un algoritmo eficiente para calcular máximo común divisor de dos números. Una forma sencilla es encontrar factores tanto del numberand continuación, se multiplican los factores comunes. Pero esto es poco complicado mediante programación. Así algoritmo de Euclides es la solución óptima hallazgo class GCD.

Ejemplo: GCD (93219)

219 = 93 x 2 + 33
93 = 33 x 2 + 27
33 = 27 x 1 + 6
27 = 6 x 4 + 3
6 = 3 x 2 + 0

Desde el resto distinto de cero es 3, de modo 3 es el MCD de 93 y 219.

Algoritmo

1) iterativo Algoritmo

    GCD(a,b)
1. while (b != 0)
2. temp = b
3. b = a % b;
4. a = t;
5. return a

2) Recursive Algoritmo

    GCD(a,b)
1. if (b == 0)
2. return a
3. else
4. return gcd(b, a % b)

complejidad de tiempo: O (Log min (a, b))

programa para implementar euclidiana Algoritmo en Kotlin

fun gcd_1(a:Int, b:Int) :Int {
var a=a
var b=b
while (b != 0) {
var t = b;
b = a % b;
a = t;
}
return a
}
fun gcd_2(a:Int, b:Int) :Int {
if (b == 0)
return a
else
return gcd_2(b, a % b)
}
fun main(args: Array<String>) {
println("Enter two number ")
var a = readLine()!!.toInt()
var b = readLine()!!.toInt()
println("Using iterative function GCD = ${gcd_1(a, b)}")
println("using recursive function GCD = ${gcd_2(a, b)}")
}

de salida

Enter two number 
93
219
Using iterative function GCD = 3
using recursive function GCD = 3

Leer más: programa java para encontrar GCD utilizando el algoritmo de Euclides.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *