Número de divisiones en el algoritmo de Euclides
Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:
mcd(a,b) = a, si b = 0 = b, si a = 0 = mcd (a módulo b, b), si a > b = mcd (a, b módulo a), si b >= a
Definir la función
mcdYdivisiones :: Int -> Int -> (Int,Int)
tal que (mcdYdivisiones a b) es el número de divisiones usadas en el cálculo del máximo común divisor de a y b mediante el algoritmo de Euclides. Por ejemplo,
mcdYdivisiones 252 198 == (18,4)
ya que los 4 divisiones del cálculo son
mcd 252 198 = mcd 54 198 = mcd 54 36 = mcd 18 36 = mcd 18 0
Comprobar con QuickCheck que el número de divisiones requeridas por el algoritmo de Euclides para calcular el MCD de a y b es igual o menor que cinco veces el número de dígitos de menor de los números a y b.
Soluciones
import Test.QuickCheck import Debug.Trace mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones a b = mcd a b 0 where mcd a 0 n = (a,n) mcd 0 b n = (b,n) mcd a b n | a > b = mcd (a `mod` b) b (n+1) | otherwise = mcd a (b `mod` a) (n+1) -- La propiedad es prop_mcdYdivisiones :: Int -> Int -> Property prop_mcdYdivisiones a b = a > 0 && b > 0 ==> n < 5 * length (show (min a b)) where (_,n) = mcdYdivisiones a b -- La comprobación es -- λ> quickCheck prop_mcdYdivisiones -- +++ OK, passed 100 tests. -- 2ª definición (con traza) mcdYdivisiones2 :: Int -> Int -> (Int,Int) mcdYdivisiones2 a b = mcd a b 0 where mcd a b n | trace (show a ++ ", " ++ show b) False = undefined mcd a 0 n = (a,n) mcd 0 b n = (b,n) mcd a b n | a > b = mcd (a `mod` b) b (n+1) | otherwise = mcd a (b `mod` a) (n+1) -- Por ejemplo, -- λ> mcdYdivisiones2 252 198 -- 252, 198 -- 54, 198 -- 54, 36 -- 18, 36 -- 18, 0 -- (18,4)