Menu Close

Tablas de operaciones binarias

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

   0 1 2    0 2 1
   1 2 0    1 0 2
   2 0 1    2 1 0
   Suma     Resta

Definir las funciones

   tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
   tablaSuma      :: Int -> [[Int]]
   tablaResta     :: Int -> [[Int]]
   tablaProducto  :: Int -> [[Int]]

tales que

  • (tablaOperacion f n) es la tabla de la operación f módulo n en [0..n-1]. Por ejemplo,
     tablaOperacion (+) 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
     tablaOperacion (-) 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
     tablaOperacion (-) 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
     tablaOperacion (\x y -> abs (x-y)) 3  ==  [[0,1,2],[1,0,1],[2,1,0]]
  • (tablaSuma n) es la tabla de la suma módulo n en [0..n-1]. Por ejemplo,
     tablaSuma 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
     tablaSuma 4  ==  [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
  • (tablaResta n) es la tabla de la resta módulo n en [0..n-1]. Por ejemplo,
     tablaResta 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
     tablaResta 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
  • (tablaProducto n) es la tabla del producto módulo n en [0..n-1]. Por ejemplo,
     tablaProducto 3  ==  [[0,0,0],[0,1,2],[0,2,1]]
     tablaProducto 4  ==  [[0,0,0,0],[0,1,2,3],[0,2,0,2],[0,3,2,1]]

Comprobar con QuickCheck, si parato entero positivo n de verificar las siguientes propiedades:

  • La suma, módulo n, de todos los números de (tablaSuma n) es 0.
  • La suma, módulo n, de todos los números de (tablaResta n) es 0.
  • La suma, módulo n, de todos los números de (tablaProducto n) es n/2 si n es el doble de un número impar y es 0, en caso contrario.

Soluciones

import Test.QuickCheck
 
tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
tablaOperacion f n =
  [[f i j `mod` n | j <- [0..n-1]] | i <- [0..n-1]]
 
tablaSuma :: Int -> [[Int]]
tablaSuma = tablaOperacion (+)
 
tablaResta :: Int -> [[Int]]
tablaResta = tablaOperacion (-)
 
tablaProducto :: Int -> [[Int]]
tablaProducto = tablaOperacion (*)
 
-- (sumaTabla xss) es la suma, módulo n, de los elementos de la tabla de
-- operación xss (donde n es el número de elementos de xss). Por
-- ejemplo, 
--    sumaTabla [[0,2,1],[1,1,2],[2,1,0]]  ==  1
sumaTabla :: [[Int]] -> Int
sumaTabla = sum . concat
 
-- La propiedad de la tabla de la suma es
prop_tablaSuma :: (Positive Int) -> Bool
prop_tablaSuma (Positive n) =
  sumaTabla (tablaSuma n) == 0
 
-- La comprobación es
--    λ> quickCheck prop_tablaSuma
--    +++ OK, passed 100 tests.
 
-- La propiedad de la tabla de la resta es
prop_tablaResta :: (Positive Int) -> Bool
prop_tablaResta (Positive n) =
  sumaTabla (tablaResta n) == 0
 
-- La comprobación es
--    λ> quickCheck prop_tablaResta
--    +++ OK, passed 100 tests.
 
-- La propiedad de la tabla del producto es
prop_tablaProducto :: (Positive Int) -> Bool
prop_tablaProducto (Positive n)
  | even n && odd (n `div` 2) = suma == n `div` 2
  | otherwise                 = suma == 0
  where suma = sumaTabla (tablaProducto n)

Pensamiento

¿Tu verdad? No, la Verdad,
y ven conmigo a buscarla.
La tuya guárdatela.

Antonio Machado

Posted in Medio

6 Comments

  1. frahidzam
    import Test.QuickCheck
     
    tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
    tablaOperacion o n = [tablaOperacionAux o n x | x <- [0..(n-1)]]
     
    tablaOperacionAux :: (Int -> Int -> Int) -> Int -> Int -> [Int]
    tablaOperacionAux o n x = [mod (o x b) n | b <- [0..(n-1)]]
     
    tablaSuma :: Int -> [[Int]]
    tablaSuma n = tablaOperacion (+) n
     
    tablaResta :: Int -> [[Int]]
    tablaResta n = tablaOperacion (-) n
     
    tablaProducto :: Int -> [[Int]]
    tablaProducto n = tablaOperacion (*) n
     
    prop_tablaSuma :: Int -> Property
    prop_tablaSuma n =
      n > 0 ==> mod (sum (map sum (tablaSuma n))) n == 0
     
    prop_tablaResta :: Int -> Property
    prop_tablaResta n =
      n > 0 ==> mod (sum (map sum (tablaResta n))) n == 0
     
    prop_tablaProducto :: Int -> Property
    prop_tablaProducto n
      | even n && odd (div n 2) =
          n > 0 ==> mod (sum (map sum (tablaProducto n))) n == div n 2
      | otherwise =
          n > 0 ==> mod (sum (map sum (tablaProducto n))) n == 0
     
    -- Las comprobaciones son:
    --    λ> quickCheck prop_tablaSuma
    --    +++ OK, passed 100 tests.
    --    λ> quickCheck prop_tablaResta
    --    +++ OK, passed 100 tests.
    --    λ> quickCheck prop_tablaProducto
    --    +++ OK, passed 100 tests.
  2. ireprirod
    import Test.QuickCheck
     
    tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
    tablaOperacion f x = map opera [0..x-1]
      where opera n = [mod (f n m) x | m <- [0..x-1]]
     
    tablaSuma :: Int -> [[Int]]
    tablaSuma x = tablaOperacion (+) x
     
    tablaResta :: Int -> [[Int]]
    tablaResta x = tablaOperacion (-) x
     
    tablaProducto :: Int -> [[Int]]
    tablaProducto x = tablaOperacion (*) x
     
    prop_suma :: Int -> Property
    prop_suma n =
      n > 0 ==> mod (sum (map sum (tablaSuma n))) n == 0
     
    prop_resta :: Int -> Property
    prop_resta n =
      n > 0 ==> mod (sum (map sum (tablaResta n))) n == 0
     
    prop_producto :: Int -> Property
    prop_producto n
      | even n && odd (div n 2) = n > 0 ==> s == div n 2
      | otherwise               = n > 0 ==> s == 0
      where s = mod (sum (map sum (tablaProducto n))) n
  3. adogargon
    import Test.QuickCheck
     
    tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
    tablaOperacion f n = [map (`mod` n) (map (f x) [0..n-1]) | x <- [0..n-1]]
     
    tablaSuma :: Int -> [[Int]]
    tablaSuma n = tablaOperacion (+) n
     
    tablaResta :: Int -> [[Int]]
    tablaResta n = tablaOperacion (-) n
     
    tablaProducto :: Int -> [[Int]]
    tablaProducto n = tablaOperacion (*) n
     
    prop_tablaSuma :: Int -> Property
    prop_tablaSuma n =
      n > 0 ==> mod (sum (map sum (tablaSuma n))) n == 0
     
    prop_tablaResta :: Int -> Property
    prop_tablaResta n =
      n > 0 ==> mod (sum (map sum (tablaResta n))) n == 0
     
    prop_tablaProducto :: Int -> Property
    prop_tablaProducto n
      | even n && odd (div n 2) =
          n > 0 ==> mod (sum (map sum (tablaProducto n))) n == div n 2
      | otherwise =
          n > 0 ==> mod (sum (map sum (tablaProducto n))) n == 0
  4. luipromor
    import Test.QuickCheck
     
    tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
    tablaOperacion f n = [[mod (f y x) n  | x <- [0..n-1]  ] | y <- [0..n-1] ]
     
    tablaSuma :: Int -> [[Int]]
    tablaSuma = tablaOperacion (+)
     
    tablaResta :: Int -> [[Int]]
    tablaResta = tablaOperacion (-)
     
    tablaProducto :: Int -> [[Int]]
    tablaProducto  = tablaOperacion (*)
     
    prop_tablaSuma :: Int -> Property
    prop_tablaSuma n =
      n > 0 ==> mod ((sum . map sum . tablaSuma) n) n == 0
     
    prop_tablaResta :: Int -> Property
    prop_tablaResta n =
      n > 0 ==> mod ((sum . map sum . tablaResta ) n) n == 0
     
    prop_tablaProducto :: Int -> Property
    prop_tablaProducto n
      | odd( div  n 2) && mod n 2 == 0 =
        n > 0 ==> mod ((sum . map sum . tablaProducto ) n) n == div n 2
      | otherwise =
        n > 0 ==> mod ((sum . map sum . tablaProducto ) n) n == 0
  5. lucsanand
    import Test.QuickCheck
     
    tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
    tablaOperacion f x = [aux (map (f n) xs) | n <- xs]
     where aux n = map (`mod` x) n
           xs = [0..x-1]
     
    tablaSuma :: Int -> [[Int]]
    tablaSuma x = tablaOperacion (+) x
     
    tablaResta :: Int -> [[Int]]
    tablaResta x = tablaOperacion (-) x
     
    tablaProducto :: Int -> [[Int]]
    tablaProducto x = tablaOperacion (*) x
     
    prop_tSuma :: Int -> Property
    prop_tSuma n =
      n > 0 ==> mod (sum (map sum (tablaSuma n))) n == 0
     
    prop_tResta :: Int -> Property
    prop_tResta n =
      n > 0 ==> mod (sum (map sum (tablaResta n))) n == 0
     
    prop_tProducto :: Int -> Property
    prop_tProducto n
      | even n && odd x =
        n > 0 ==>  mod (sum (map sum (tablaProducto n))) n == x
      | otherwise =
        n > 0 ==> mod (sum (map sum (tablaProducto n))) n == 0
      where x = div n 2
  6. javmarcha1
    import Test.QuickCheck
     
    tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
    tablaOperacion f n =
      agrupaR1 n [mod (f x y) n | x <- take n [0..], y <- take n [0..]]
     
    tablaSuma :: Int -> [[Int]]
    tablaSuma n =
      agrupaR1 n [mod (x+y) n | x <- take n [0..], y <- take n [0..]] 
     
    tablaResta :: Int -> [[Int]]
    tablaResta n =
      agrupaR1 n [mod (x-y) n | x <- take n [0..], y <- take n [0..]]
     
    tablaProducto :: Int -> [[Int]]
    tablaProducto n =
      agrupaR1 n [mod (x*y) n | x <- take n [0..], y <- take n [0..]]
     
    agrupaR1 :: Int -> [a] -> [[a]]
    agrupaR1 _ []                 = []
    agrupaR1 n xs | n > length xs = []
    agrupaR1 n xs                 = take n xs : agrupaR1 n (drop n xs) 
     
    prop_tablaSuma :: Int -> Bool
    prop_tablaSuma n = prop_tablaSuma1 (abs n) == True
     
    prop_tablaSuma1 :: Int -> Bool
    prop_tablaSuma1 n
      | n == 0    = sum [] == 0
      | n > 0     = mod (sum (concat (tablaSuma n))) n == 0
      | otherwise = False
     
    prop_tablaResta :: Int -> Bool
    prop_tablaResta n = prop_tablaResta1 (abs n) == True
     
    prop_tablaResta1 :: Int -> Bool
    prop_tablaResta1 n
      | n == 0    = sum [] == 0
      | n > 0     = mod (sum (concat (tablaResta n))) n == 0
      | otherwise = False
     
    prop_tablaProducto :: Int -> Bool
    prop_tablaProducto n = prop_tablaProducto1 (abs n) == True
     
    prop_tablaProducto1 :: Int -> Bool
    prop_tablaProducto1 n
      | n == 0 = sum [] == 0
      | even n && odd (div n 2) && n > 0 =
        mod (sum (concat (tablaProducto n))) n == div n 2
      | otherwise = mod (sum (concat (tablaProducto n))) n == 0
     
    --   λ> quickCheck prop_tablaSuma
    --   +++ OK, passed 100 tests.
    --   λ> quickCheck prop_tablaResta
    --   +++ OK, passed 100 tests.
    --   λ> quickCheck prop_tablaProducto
    --   +++ OK, passed 100 tests.

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.