es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Evaluación de la implementación del algoritmo de Euclides extendido.

19 Jul, 2023 Programación

Después de algunas experimentaciones y búsquedas, llegué a la siguiente definición:

emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b = 
  let (g, t, s) = emcd' b r
  in (g, s, t - (q * s))
    where
      (q, r) = divMod a b

Evaluaría emcd' 56 15 hasta el nivel más interno, por ejemplo, de esta manera:

  emcd' 56 15 
= let (g, t, s) = emcd' 15 11 in (
    let (g, t, s) = emcd' 11 4 in (
      let (g, t, s) = emcd' 4 3 in (
          let (g, t, s) = emcd' 3 1 in (
            let (g, t, s) = emcd' 1 0 in (
              (1, 1, 0)
            ) in (g, s, t - (3 * s))
          ) in (g, s, t - (1 * s))
        ) in (g, s, t - (2 * s))
      ) in (g, s, t - (1 * s))
  ) in (g, s, t - (3 * s))
  • ¿Está mi evaluación yendo en la dirección correcta?

EDITADO:

A partir de los comentarios de Will Ness, estoy actualizando la evaluación.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    No, su evaluación no va en la dirección correcta.

    En primer lugar, el paso (g, t, s) = emcd' 15 11 está mal, debería ser (g, s, t) = emcd' 15 11, ya que la tupla devuelta es (gcd, x, y).

    En segundo lugar, parece que está evaluando la función de manera recursiva en profundidad, lo cual no es la forma correcta de evaluarla. En cambio, debería evaluar la función de abajo hacia arriba, reemplazando cada llamada por su resultado hasta llegar al resultado final.

    Aquí tienes un ejemplo de evaluación:

    emcd' 56 15
-- a = 56, b = 15
-- q = 56 `div` 15 = 3, r = 56 `mod` 15 = 11
-- llamada recursiva: emcd' 15 11
-- g = 1, s = 4, t = -13
-- volviendo a la llamada original: (g, s, t) = (1, 4, -13)
(1, 4, -13)

    Explicación:

    • La función primero verifica si b es igual a 0. En este caso, devuelve (a, 1, 0) ya que el máximo común divisor de a y 0 es a y 1*a + 0*0 = a.
    • Si b no es igual a 0, calcula el cociente q y el resto r de la división de a por b.
    • Hace una llamada recursiva a emcd', pasando b y r como argumentos.
    • La llamada recursiva devuelve una tupla (g, t, s), donde g es el máximo común divisor de b y r, y t y s son enteros tal que b*t + r*s = g.
    • La función calcula nuevos valores para g, s, y t de la siguiente manera: g es igual al resultado de la llamada recursiva (es decir, el máximo común divisor de b y r), s es igual al tercer elemento de la tupla devuelta por la llamada recursiva (es decir, s es el valor de t en emcd' b r), y t se calcula como t - q*s.
    • La función devuelve la tupla (g, s, t).

    En la evaluación emcd' 56 15, b no es igual a 0, por lo que la función calcula q y r como 3 y 11, respectivamente, y hace una llamada recursiva a emcd' 15 11. La llamada recursiva devuelve (1, -13, 4), lo que significa que el máximo común divisor de 15 y 11 es 1, y 15*(-13) + 11*4 = 1.

    Al sustituir los valores de g, s y t en la llamada original, obtenemos (1, 4, -13) como resultado final.

Comments are closed.