Máximo común divisor de x e y veces n

PorJosé A. Alonso 9-febrero-201716-febrero-2017

Definir las funciones

   repite :: Int -> Integer -> Integer
   mcdR   :: Integer -> Int -> Int -> Integer

1 2	repite :: Int -> Integer -> Integer mcdR :: Integer -> Int -> Int -> Integer

tales que

(repite x n) es el número obtenido repitiendo x veces el número n. Por ejemplo.

     repite 3 123  ==  123123123

1	repite 3 123 == 123123123

(mcdR n x y) es el máximo común divisor de los números obtenidos repitiendo x veces e y veces el número n. Por ejemplo.

     mcdR 123 2 3                     ==  123
     mcdR 4 4 6                       ==  44
     mcdR 2017 (10^1000) (2+10^1000)  ==  20172017

1

2

3

mcdR 123 2 3 == 123

mcdR 4 4 6 == 44

mcdR 2017 (10^1000) (2+10^1000) == 20172017

Soluciones

import Test.QuickCheck

repite :: Int -> Integer -> Integer
repite x n =
  read (concat (replicate x (show n)))

-- 1ª definición
mcdR :: Integer -> Int -> Int -> Integer
mcdR n x y =
  gcd (repite x n) (repite y n)

-- 2ª definición
mcdR2 :: Integer -> Int -> Int -> Integer
mcdR2 n x y =
  repite (gcd x y) n

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_equivalencia :: (Positive Integer) -> (Positive Int) -> (Positive Int)
                     -> Bool
prop_equivalencia (Positive n) (Positive x) (Positive y) =
  mcdR n x y == mcdR2 n x y

-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

--    λ> mcdR 2017 (10^6) (2+10^6)
--    20172017
--    (18.92 secs, 6,012,285,224 bytes)
--    λ> mcdR2 2017 (10^6) (2+10^6)
--    20172017
--    (0.01 secs, 0 bytes)

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

import Test.QuickCheck

repite :: Int -> Integer -> Integer

repite x n =

read (concat (replicate x (show n)))

-- 1ª definición

mcdR :: Integer -> Int -> Int -> Integer

mcdR n x y =

gcd (repite x n) (repite y n)

-- 2ª definición

mcdR2 :: Integer -> Int -> Int -> Integer

mcdR2 n x y =

repite (gcd x y) n

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_equivalencia :: (Positive Integer) -> (Positive Int) -> (Positive Int)

-> Bool

prop_equivalencia (Positive n) (Positive x) (Positive y) =

mcdR n x y == mcdR2 n x y

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- λ> mcdR 2017 (10^6) (2+10^6)

-- 20172017

-- (18.92 secs, 6,012,285,224 bytes)

-- λ> mcdR2 2017 (10^6) (2+10^6)

-- 20172017

-- (0.01 secs, 0 bytes)

5 Comentarios

repite :: Int -> Integer -> Integer
repite x n = read $ copia x $ show n

copia :: Int -> [a] -> [a]
copia 0 xs = []
copia n xs = xs ++ copia (n-1) xs

mcdR   :: Integer -> Int -> Int -> Integer
mcdR n x y | x == 0    = repite y n
           | y == 0    = repite x n
           | otherwise = gcd (read (xs ++ copia (x-z) n')) (read (xs ++ copia (y-z) n'))
     where z  = min x y
           n' = show n
           xs = copia z n'

1

2

3

4

5

6

7

8

9

10

11

12

13

14

repite :: Int -> Integer -> Integer

repite x n = read $ copia x $ show n

copia :: Int -> [a] -> [a]

copia 0 xs = []

copia n xs = xs ++ copia (n-1) xs

mcdR :: Integer -> Int -> Int -> Integer

mcdR n x y | x == 0 = repite y n

| y == 0 = repite x n

| otherwise = gcd (read (xs ++ copia (x-z) n')) (read (xs ++ copia (y-z) n'))

where z = min x y

n' = show n

xs = copia z n'

repite :: Int -> Integer -> Integer  
repite x n = read (concat (replicate x (show n)))

mcdR   :: Integer -> Int -> Int -> Integer
mcdR n x y = repite (gcd x y) n

1

2

3

4

5

repite :: Int -> Integer -> Integer

repite x n = read (concat (replicate x (show n)))

mcdR :: Integer -> Int -> Int -> Integer

mcdR n x y = repite (gcd x y) n

-- Solucion directa pero poco eficiente

repite :: Int -> Integer -> Integer
repite n k = read $ concat $ replicate n (show k)

mcdR :: Integer -> Int -> Int -> Integer
mcdR n a b = gcd (repite a n) (repite b n)

1

2

3

4

5

6

7

-- Solucion directa pero poco eficiente

repite :: Int -> Integer -> Integer

repite n k = read $ concat $ replicate n (show k)

mcdR :: Integer -> Int -> Int -> Integer

mcdR n a b = gcd (repite a n) (repite b n)

repite :: Integer -> Int -> Integer
repite x 1 = x
repite x n = x * 10 ^(length (digitos x) *(n-1)) + (repite x (n-1))

digitos :: Integer -> [Int]
digitos x = [read [c] | c <- show x]
  
mcdR :: Integer -> Int -> Int -> Integer
mcdR n x y = gcd (repite n x) (repite n y)

1

2

3

4

5

6

7

8

9

repite :: Integer -> Int -> Integer

repite x 1 = x

repite x n = x * 10 ^(length (digitos x) *(n-1)) + (repite x (n-1))

digitos :: Integer -> [Int]

digitos x = [read [c] | c <- show x]

mcdR :: Integer -> Int -> Int -> Integer

mcdR n x y = gcd (repite n x) (repite n y)

import Data.List (genericReplicate)

repite :: Integer -> Integer -> Integer
repite x n = (read . concat) $ genericReplicate x (show n)
 
-- Solución "mala"
mcdR'   :: Integer -> Integer -> Integer -> Integer
mcdR' n x y = gcd (repite x n) (repite y n)
 
-- Solución buena
mcdR :: Integer -> Integer -> Integer -> Integer
mcdR n x y = repite (gcd x y) n
 
-- Propiedad definida para estudiar la equivalencia de ambas definiciones
prop_mcdR :: Integer -> Integer -> Integer -> Property
prop_mcdR n x y =
  n > 0 && x > 0 && y > 0  ==>
  mcdR' n x y == mcdR n x y
 
-- Resultado de la prueba:
--    λ> quickCheckWith stdArgs {maxSuccess = 1000} prop_mcdR
--    +++ OK, passed 1000 tests.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

import Data.List (genericReplicate)

repite :: Integer -> Integer -> Integer

repite x n = (read . concat) $ genericReplicate x (show n)

-- Solución "mala"

mcdR' :: Integer -> Integer -> Integer -> Integer

mcdR' n x y = gcd (repite x n) (repite y n)

-- Solución buena

mcdR :: Integer -> Integer -> Integer -> Integer

mcdR n x y = repite (gcd x y) n

-- Propiedad definida para estudiar la equivalencia de ambas definiciones

prop_mcdR :: Integer -> Integer -> Integer -> Property

prop_mcdR n x y =

n > 0 && x > 0 && y > 0 ==>

mcdR' n x y == mcdR n x y

-- Resultado de la prueba:

-- λ> quickCheckWith stdArgs {maxSuccess = 1000} prop_mcdR

-- +++ OK, passed 1000 tests.

Escribe tu soluciónCancel reply