Número de divisiones en el algoritmo de Euclides

3 Comentarios

1. Haskell

   import Test.QuickCheck mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones a b = (mcdDato a b, mcdNumero a b) mcdDato :: Integral a => a -> a -> a mcdDato a b | b == 0 = a | a == 0 = b | a > b = mcdDato (a `mod` b) b | a <= b = mcdDato a (b `mod` a) mcdNumero :: (Integral a1, Num a) => a1 -> a1 -> a mcdNumero a b | b == 0 = 0 | a == 0 = 0 | a > b = 1 + mcdNumero (a `mod` b) b | a <= b = 1 + mcdNumero a (b `mod` a) prop :: (Integral a, Show a) => a -> a -> Property prop a b = a > 0 && b > 0 ==> 5 * (length (show (min a b))) >= (mcdNumero a b)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   import Test.QuickCheck   mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones a b = (mcdDato a b, mcdNumero a b) mcdDato :: Integral a => a -> a -> a mcdDato a b | b == 0  = a             | a == 0  = b             | a > b   = mcdDato (a `mod` b) b             | a <= b  = mcdDato a (b `mod` a) mcdNumero :: (Integral a1, Num a) => a1 -> a1 -> a mcdNumero a b | b == 0  = 0               | a == 0  = 0               | a > b   = 1 + mcdNumero (a `mod` b) b               | a <= b  = 1 + mcdNumero a (b `mod` a) prop :: (Integral a, Show a) => a -> a -> Property prop a b =     a > 0 && b > 0 ==>     5 * (length (show (min a b))) >= (mcdNumero a b)

   Responder

2. Haskell

   mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones a b = (last $ init xs, length xs) where xs = divisiones a b divisiones :: Int -> Int -> [Int] divisiones a 0 = [0] divisiones 0 b = [0] divisiones a b | r == 0 = [r] | a > b = r : divisiones b r | otherwise = m : divisiones a m where r = mod a b m = mod b a prop_mcd :: Int -> Int -> Property prop_mcd a b = a > 0 && b > 0 ==> length (divisiones a b) <= 5 * length (show (min a b))

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones a b = (last $ init xs, length xs)     where xs = divisiones a b   divisiones :: Int -> Int -> [Int] divisiones a 0 = [0] divisiones 0 b = [0] divisiones a b | r == 0    = [r]                | a > b     = r : divisiones b r                | otherwise = m : divisiones a m        where r = mod a b              m = mod b a   prop_mcd :: Int -> Int -> Property prop_mcd a b =     a > 0 && b > 0 ==>     length (divisiones a b) <= 5 * length (show (min a b))

   Responder

3. Haskell

   mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones = aux 0 where aux n a b | a == 0 = (b,n) | a >= b = aux (n+1) (rem a b) b | otherwise = aux n b a prop_mcd :: Int -> Int -> Property prop_mcd a b = a > 0 && b > 0 ==> snd (mcdYdivisiones a b) <= 5 * (length $ show (min a b))

   1 2 3 4 5 6 7 8 9 10

   mcdYdivisiones :: Int -> Int -> (Int,Int) mcdYdivisiones = aux 0      where aux n a b | a == 0    = (b,n)                      | a >= b    = aux (n+1) (rem a b) b                      | otherwise = aux n b a   prop_mcd :: Int -> Int -> Property prop_mcd a b =     a > 0 && b > 0 ==>       snd (mcdYdivisiones a b) <= 5 * (length $ show (min a b))

   Responder