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:
1 2 3 4 |
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
1 |
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,
1 |
mcdYdivisiones 252 198 == (18,4) |
ya que los 4 divisiones del cálculo son
1 2 3 4 5 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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) |
3 Comentarios