Representación decimal de números racionales

3 Comentarios

1. Haskell

   import Test.QuickCheck type Decimal = (Integer,[Integer],[Integer]) type Racional = (Integer,Integer) decimal :: Racional -> Decimal decimal r | null ds = (0, [], []) | otherwise = (fst (head ds), as', ps') where ds = digitos r (as, ps) = partePuraPeriodica (tail ds) as' = map fst as ps' = map fst ps digitos :: Racional -> [Racional] digitos (n,d) | n == 0 = [] | r == 0 = [(e,0)] | otherwise = (e,r) : digitos (10*r, d) where (e,r) = n `divMod` d partePuraPeriodica :: Eq a => [a] -> ([a],[a]) partePuraPeriodica = aux [] where aux as [] = (reverse as, []) aux as (b:bs) | b `elem` as = span (/=b) (reverse as) | otherwise = aux (b:as) bs racional :: Decimal -> Racional racional (e, as, ps) | null ps = reduce (x, 10^a) | otherwise = reduce (y-x, 10^b-10^a) where a = length as x = read (concatMap show (e:as)) b = length as + length ps y = read (concatMap show (e:as ++ ps)) reduce :: Racional -> Racional reduce (n,d) = (n `div` g, d `div` g) where g = gcd n d prop_inversa :: (Positive Integer, Positive Integer) -> Bool prop_inversa (n,d) = (racional . decimal) r == r where r = reduce (getPositive n, getPositive d)

   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 40 41 42 43

   import Test.QuickCheck   type Decimal = (Integer,[Integer],[Integer]) type Racional = (Integer,Integer)   decimal  :: Racional -> Decimal decimal r | null ds     = (0, [], [])           | otherwise   = (fst (head ds), as', ps')     where         ds = digitos r         (as, ps) = partePuraPeriodica (tail ds)         as' = map fst as         ps' = map fst ps   digitos :: Racional -> [Racional] digitos (n,d) | n == 0    = []               | r == 0    = [(e,0)]               | otherwise = (e,r) : digitos (10*r, d)     where (e,r) = n `divMod` d   partePuraPeriodica :: Eq a => [a] -> ([a],[a]) partePuraPeriodica = aux []     where         aux as []  = (reverse as, [])         aux as (b:bs) | b `elem` as = span (/=b) (reverse as)                       | otherwise = aux (b:as) bs   racional :: Decimal -> Racional racional (e, as, ps) | null ps   = reduce (x, 10^a)                      | otherwise = reduce (y-x, 10^b-10^a)     where         a = length as         x = read (concatMap show (e:as))         b = length as + length ps         y = read (concatMap show (e:as ++ ps))   reduce :: Racional -> Racional reduce (n,d) = (n `div` g, d `div` g)     where g = gcd n d   prop_inversa :: (Positive Integer, Positive Integer) -> Bool prop_inversa (n,d) = (racional . decimal) r == r     where r = reduce (getPositive n, getPositive d)

   Responder

2. Haskell

   import Test.QuickCheck import Data.List import Data.Char type Decimal = (Integer,[Integer],[Integer]) type Racional = (Integer,Integer) -- * La función "decimal" es: decimal :: Racional -> Decimal decimal (_,0) = error "El denominador no puede ser cero" decimal (0,_) = (0,[],[]) decimal (a,b) | parteEnteraPequeña ds2 = (0,(replicate ((digitToInt (last ds2))-1) 0) ++ (stringAlista (buscarAnteperiodo (init ds') [])), stringAlista (quitarLista (buscarPeriodo (init ds')))) | parteEnteraGrande ds2 = (e*10^((digitToInt (last ds2))-1),xs,ys) | a < 0 = algunNegativo (decimal (-a,b)) | b < 0 = algunNegativo (decimal (a,-b)) | otherwise = (e,xs,ys) where e = (fromIntegral (parteEntera ds1)) xs = stringAlista (buscarAnteperiodo ds2 []) ys = quitaRepetidosSolos (stringAlista (quitarLista(buscarPeriodo ds2))) ds = digitos ((fromIntegral a)/(fromIntegral b)) ds' = filter (isDigit) ((fst ds) ++ (snd ds)) ds1 = fst ds ds2 = snd ds -- * Las funciones auxiliares utilizadas son: -- (digitos n) devuelve el par (a,b), donde a es la parte entera del número racional n -- y b es la parte decimal de n (a y b son cadenas). digitos :: Show a => a -> ([Char], [Char]) digitos n = aux (show n) [] where aux [] ys = (ys,[]) aux (x:xs) ys | x == '.' = (ys,xs) | otherwise = aux xs (ys ++ [x]) -- (stringAlista xs) tranforma la lista de caracteres xs en una lista de números. stringAlista :: Num t => [Char] -> [t] stringAlista xs = [ fromIntegral (digitToInt x) | x <- xs ] -- (buscarPeriodo' xs) devuelve la lista con las cadenas que se repiten en xs. buscarPeriodo' :: [Char] -> [[Char]] buscarPeriodo' xs = [ x | x <- inits xs, y <- inits xs, x ++ x == y, x /= "", length x >= 2 ] -- (buscarPeriodo xs) va analizando los decimales del número racional hasta que -- encuentra alguna cadena que se repita; esto se hace por si tuviera anteperíodo. buscarPeriodo :: [Char] -> [[Char]] buscarPeriodo [] = [] buscarPeriodo (x:xs) | buscarPeriodo' (x:xs) == [] = buscarPeriodo xs | otherwise = buscarPeriodo' (x:xs) -- (buscarAnteperiodo xs) devuelve el anteperiodo de la cadena xs. buscarAnteperiodo :: [Char] -> [Char] -> [Char] buscarAnteperiodo [] ys = ys buscarAnteperiodo (x:xs) ys | buscarPeriodo' (x:xs) == [] = buscarAnteperiodo xs (ys ++ [x]) | otherwise = ys -- (quitarLista xss) la uso para la función (buscarPeriodo xs), de la cual quiero solo -- el primer elemento, aunque si se tratara de una lista vacía querría una lista vacía, -- por lo que no puedo usar "head" sólo, de ahí a que tenga que crearla. quitarLista :: [[t]] -> [t] quitarLista xss | length xss >= 1 = head xss | otherwise = [] -- (parteEntera xs) transforma la cadena xs en un número entero. parteEntera :: [Char] -> Int parteEntera (x:[]) = digitToInt x parteEntera (x:xs) = (10 ^ ((length (x:xs))-1)) * (digitToInt x) + parteEntera xs -- (parteEnteraPequeña xs) se verifica si el número racional que estamos trabajando -- es muy pequeño, tanto que Haskell nos lo devuelve con notación científica. parteEnteraPequeña :: [Char] -> Bool parteEnteraPequeña ys = isInfixOf "e-" ys -- (parteEnteraGrande xs) se verifica si el número racional que estamos trabajando -- es muy grande, tanto que Haskell nos lo devuelve con notación científica. parteEnteraGrande :: Foldable t => t Char -> Bool parteEnteraGrande ys = notElem '-' ys && elem 'e' ys -- (quitaRepetidoSolos xs) devuelve [x] si todos los elementos de xs son x; se usa por -- si, por ejemplo, tenemos un período [3,3,3], y solo queremos [3] (no se puede usar -- (nub xs) por si el período fuera, por ejemplo, [3,3,4] ). quitaRepetidosSolos :: Eq t => [t] -> [t] quitaRepetidosSolos [] = [] quitaRepetidosSolos (x:xs) | all (== x) xs = [x] | otherwise = (x:xs) -- (algunNegativo d) devuelve la representación decimal d, pero con parte entera negativa. algunNegativo :: Num t => (t, t1, t2) -> (t, t1, t2) algunNegativo (e,xs,ys) = (-e,xs,ys) -- * Por otro lado, la función "racional" es: racional :: Decimal -> Racional racional d@(e,xs,ys) | e < 0 = head [ (-a,b) | a <- [1..], b <- [1..a], decimal (-a,b) == d ] | e > 0 = head [ (a,b) | a <- [1..], b <- [1..a], decimal (a,b) == d ] | otherwise = head [ (a,b) | b <- [1..], a <- [1..b], decimal (a,b) == d ] -- * La propiedad es prop_inversa :: Integer -> Integer -> Property prop_inversa a b = a > 0 && b > 0 ==> racional (decimal (a,b)) == reduce (a,b) reduce :: Racional -> Racional reduce (n,d) = (n `div` g, d `div` g) where g = gcd n d -- La comprobación es -- *Main> quickCheck prop_inversa -- +++ OK, passed 100 tests. -- NOTAS: -- * No he conseguido verificar los dos últimos ejemplos sobre calcular los -- períodos de los números racionales (mi función tiene en cuenta -- solo los 17 primeros dígitos de los números racionales). -- * A la hora de comprobar con QuickCheck si la propiedad se cumple, evito los -- negativos debido al caso en el que la parte entera del racional es 0, ya que -- no puedo diferenciar si es positiva o negativa (para Haskell: 0 == -0). Es decir: -- *Main> decimal (1,3) -- (0,[],[3]) -- *Main> decimal (-1,3) -- (0,[],[3])

   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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

   import Test.QuickCheck import Data.List import Data.Char   type Decimal = (Integer,[Integer],[Integer])   type Racional = (Integer,Integer)   -- * La función "decimal" es:   decimal  :: Racional -> Decimal decimal (_,0) = error "El denominador no puede ser cero" decimal (0,_) = (0,[],[]) decimal (a,b) | parteEnteraPequeña ds2 =                 (0,(replicate ((digitToInt (last ds2))-1) 0) ++                 (stringAlista (buscarAnteperiodo (init ds') [])),                 stringAlista (quitarLista (buscarPeriodo (init ds'))))               | parteEnteraGrande ds2 = (e*10^((digitToInt (last ds2))-1),xs,ys)               | a < 0 = algunNegativo (decimal (-a,b))               | b < 0 = algunNegativo (decimal (a,-b))               | otherwise = (e,xs,ys)            where e  = (fromIntegral (parteEntera ds1))                  xs = stringAlista (buscarAnteperiodo ds2 [])                  ys = quitaRepetidosSolos (stringAlista                       (quitarLista(buscarPeriodo ds2)))                  ds = digitos ((fromIntegral a)/(fromIntegral b))                  ds' = filter (isDigit) ((fst ds) ++ (snd ds))                  ds1 = fst ds                  ds2 = snd ds   -- * Las funciones auxiliares utilizadas son:   -- (digitos n) devuelve el par (a,b), donde a es la parte entera del número racional n -- y b es la parte decimal de n (a y b son cadenas). digitos :: Show a => a -> ([Char], [Char]) digitos n = aux (show n) []        where aux [] ys = (ys,[])              aux (x:xs) ys | x == '.'  = (ys,xs)                            | otherwise = aux xs (ys ++ [x])                            -- (stringAlista xs) tranforma la lista de caracteres xs en una lista de números. stringAlista :: Num t => [Char] -> [t] stringAlista xs = [ fromIntegral (digitToInt x) | x <- xs ]   -- (buscarPeriodo' xs) devuelve la lista con las cadenas que se repiten en xs. buscarPeriodo' :: [Char] -> [[Char]] buscarPeriodo' xs =  [ x | x <- inits xs, y <- inits xs, x ++ x == y, x /= "",                      length x >= 2 ]                      -- (buscarPeriodo xs) va analizando los decimales del número racional hasta que -- encuentra alguna cadena que se repita; esto se hace por si tuviera anteperíodo. buscarPeriodo :: [Char] -> [[Char]] buscarPeriodo [] =  [] buscarPeriodo (x:xs) | buscarPeriodo' (x:xs) == [] = buscarPeriodo xs                      | otherwise = buscarPeriodo' (x:xs)   -- (buscarAnteperiodo xs) devuelve el anteperiodo de la cadena xs. buscarAnteperiodo :: [Char] -> [Char] -> [Char] buscarAnteperiodo [] ys = ys buscarAnteperiodo (x:xs) ys | buscarPeriodo' (x:xs) == [] =                                 buscarAnteperiodo xs (ys ++ [x])                             | otherwise = ys   -- (quitarLista xss) la uso para la función (buscarPeriodo xs), de la cual quiero solo -- el primer elemento, aunque si se tratara de una lista vacía querría una lista vacía, -- por lo que no puedo usar "head" sólo, de ahí a que tenga que crearla. quitarLista :: [[t]] -> [t] quitarLista xss | length xss >= 1 = head xss                 | otherwise       = []   -- (parteEntera xs) transforma la cadena xs en un número entero. parteEntera :: [Char] -> Int parteEntera (x:[]) = digitToInt x parteEntera (x:xs) = (10 ^ ((length (x:xs))-1)) * (digitToInt x) + parteEntera xs   -- (parteEnteraPequeña xs) se verifica si el número racional que estamos trabajando -- es muy pequeño, tanto que Haskell nos lo devuelve con notación científica. parteEnteraPequeña :: [Char] -> Bool parteEnteraPequeña ys = isInfixOf "e-" ys   -- (parteEnteraGrande xs) se verifica si el número racional que estamos trabajando -- es muy grande, tanto que Haskell nos lo devuelve con notación científica. parteEnteraGrande :: Foldable t => t Char -> Bool parteEnteraGrande ys = notElem '-' ys && elem 'e' ys   -- (quitaRepetidoSolos xs) devuelve [x] si todos los elementos de xs son x; se usa por -- si, por ejemplo, tenemos un período [3,3,3], y solo queremos [3] (no se puede usar -- (nub xs) por si el período fuera, por ejemplo, [3,3,4] ). quitaRepetidosSolos :: Eq t => [t] -> [t] quitaRepetidosSolos [] = [] quitaRepetidosSolos (x:xs) | all (== x) xs = [x]                            | otherwise     = (x:xs)   -- (algunNegativo d) devuelve la representación decimal d, pero con parte entera negativa. algunNegativo :: Num t => (t, t1, t2) -> (t, t1, t2) algunNegativo (e,xs,ys) = (-e,xs,ys)       -- * Por otro lado, la función "racional" es:   racional :: Decimal -> Racional racional d@(e,xs,ys) | e < 0 = head [ (-a,b) | a <- [1..], b <- [1..a],                        decimal (-a,b) == d ]                      | e > 0 = head [ (a,b) | a <- [1..], b <- [1..a],                        decimal (a,b) == d ]                      | otherwise = head [ (a,b) | b <- [1..], a <- [1..b],                        decimal (a,b) == d ]   -- * La propiedad es   prop_inversa :: Integer -> Integer -> Property prop_inversa a b = a > 0 && b > 0 ==> racional (decimal (a,b)) == reduce (a,b)   reduce :: Racional -> Racional reduce (n,d) = (n `div` g, d `div` g)     where g = gcd n d   -- La comprobación es -- *Main> quickCheck prop_inversa -- +++ OK, passed 100 tests.      -- NOTAS: --  * No he conseguido verificar los dos últimos ejemplos sobre calcular los --    períodos de los números racionales (mi función tiene en cuenta --    solo los 17 primeros dígitos de los números racionales). --  * A la hora de comprobar con QuickCheck si la propiedad se cumple, evito los --    negativos debido al caso en el que la parte entera del racional es 0, ya que --    no puedo diferenciar si es positiva o negativa (para Haskell: 0 == -0). Es decir: --    *Main> decimal (1,3) --    (0,[],[3]) --    *Main> decimal (-1,3) --    (0,[],[3])

   Responder

3. Haskell

   import Data.Numbers.Primes type Decimal = (Integer,[Integer],[Integer]) type Racional = (Integer,Integer) -- Funciones auxiliares: lista2Int :: [Integer] -> Integer lista2Int = read.concatMap show digitos :: Integer -> [Integer] digitos x = [read [c]| c <- show x] decimales :: Integer -> Integer -> [[Integer]] decimales x y = tail (aux x) where aux m = [a,z] : aux (10*z) where z = m-y*a a = div m y seccion :: Eq a => [a] -> [a] seccion xs = aux xs [] where aux [] ys = reverse ys aux (x:xs) ys | x `elem` ys = reverse ys | otherwise = aux xs (x:ys) -- Las funciones pedidas: decimal :: Racional -> Decimal decimal (x,y) | all (`elem`[2,5]) (primeFactors y) = (div x y, map head $ fst d, []) | otherwise = (div x y, map head $ fst d, map head $ snd d) where xs = seccion ys ys = decimales x y d = span (/= ys!!n) xs n = length xs racional :: Decimal -> Racional racional (x,ys,[]) = (div b a, div c a) where b = lista2Int (digitos x ++ ys) c = 10^(length ys) a = gcd c b racional (x,[],zs) = (div c a, div d a) where c = lista2Int (digitos x ++ zs) - x d = 10^(length zs) - 1 a = gcd c d racional (x,ys,zs) = (div d a, div e a) where d = lista2Int (digitos x ++ ys ++ zs) - lista2Int (digitos x ++ ys) e = lista2Int (replicate (length zs) 9 ++ replicate (length ys) 0) a = gcd d e -- Y la comprobación (usando la propiedad definida por Chema Cortés): --*Main> quickCheck prop_inversa -- +++ OK, passed 100 tests.

   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 40 41 42 43 44 45 46 47 48 49 50 51

   import Data.Numbers.Primes   type Decimal = (Integer,[Integer],[Integer]) type Racional = (Integer,Integer)   -- Funciones auxiliares: lista2Int :: [Integer] -> Integer lista2Int = read.concatMap show   digitos :: Integer -> [Integer] digitos x = [read [c]| c <- show x]   decimales :: Integer -> Integer -> [[Integer]] decimales x y = tail (aux x)    where aux m = [a,z] : aux (10*z)                  where z = m-y*a                        a = div m y   seccion :: Eq a => [a] -> [a] seccion xs = aux xs []     where aux [] ys = reverse ys           aux (x:xs) ys | x `elem` ys = reverse ys                         | otherwise   = aux xs (x:ys)   -- Las funciones pedidas: decimal  :: Racional -> Decimal decimal (x,y) | all (`elem`[2,5]) (primeFactors y) = (div x y, map head $ fst d, [])               | otherwise = (div x y, map head $ fst d, map head $ snd d)                                where xs = seccion ys                                      ys = decimales x y                                      d  =  span (/= ys!!n) xs                                      n  = length xs   racional :: Decimal -> Racional racional (x,ys,[]) = (div b a, div c a)    where b = lista2Int (digitos x ++ ys)          c = 10^(length ys)          a = gcd c b racional (x,[],zs) = (div c a, div d a)      where c = lista2Int (digitos x ++ zs) - x            d = 10^(length zs) - 1            a = gcd c d racional (x,ys,zs) = (div d a, div e a)     where d = lista2Int (digitos x ++ ys ++ zs) - lista2Int (digitos x ++ ys)           e = lista2Int (replicate (length zs) 9 ++ replicate (length ys) 0)           a = gcd d e   -- Y la comprobación (usando la propiedad definida por Chema Cortés):   --*Main> quickCheck prop_inversa -- +++ OK, passed 100 tests.

   Responder