Ceros finales del factorial

Definir la función

   cerosDelFactorial :: Integer -> Integer

1	cerosDelFactorial :: Integer -> Integer

tal que cerosDelFactorial n es el número de ceros en que termina el factorial de n. Por ejemplo,

   cerosDelFactorial 24                         == 4
   cerosDelFactorial 25                         == 6
   length (show (cerosDelFactorial (10^70000))) == 70000

cerosDelFactorial 24 == 4

cerosDelFactorial 25 == 6

length (show (cerosDelFactorial (10^70000))) == 70000

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Ceros_finales_del_factorial where

import Data.List (genericLength)
import Test.QuickCheck (Positive (Positive), quickCheck)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución
-- ===========

cerosDelFactorial1 :: Integer -> Integer
cerosDelFactorial1 n = ceros (factorial n)

-- (factorial n) es el factorial n. Por ejemplo,
--    factorial 3  ==  6
factorial :: Integer -> Integer
factorial n = product [1..n]

-- (ceros n) es el número de ceros en los que termina el número n. Por
-- ejemplo,
--    ceros 320000  ==  4
ceros :: Integer -> Integer
ceros n | rem n 10 /= 0 = 0
        | otherwise     = 1 + ceros (div n 10)

-- 2ª solución
-- ===========

cerosDelFactorial2 :: Integer -> Integer
cerosDelFactorial2 = ceros2 . factorial

ceros2 :: Integer -> Integer
ceros2 n = genericLength (takeWhile (=='0') (reverse (show n)))

-- 3ª solución
-- =============

cerosDelFactorial3 :: Integer -> Integer
cerosDelFactorial3 n
  | n < 5     = 0
  | otherwise = m + cerosDelFactorial3 m
  where m = n `div` 5

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Integer) -> Spec
specG cerosDelFactorial = do
  it "e1" $
    cerosDelFactorial 24 `shouldBe` 4
  it "e2" $
    cerosDelFactorial 25 `shouldBe` 6

spec :: Spec
spec = do
  describe "def. 1" $ specG cerosDelFactorial1
  describe "def. 2" $ specG cerosDelFactorial2
  describe "def. 3" $ specG cerosDelFactorial3

-- La verificación es
--    λ> verifica
--
--    6 examples, 0 failures

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

-- La propiedad es
prop_cerosDelFactorial :: Positive Integer -> Bool
prop_cerosDelFactorial (Positive n) =
  all (== cerosDelFactorial1 n)
      [cerosDelFactorial2 n,
       cerosDelFactorial3 n]

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

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

-- La comparación es
--    λ> cerosDelFactorial1 (4*10^4)
--    9998
--    (1.93 secs, 2,296,317,904 bytes)
--    λ> cerosDelFactorial2 (4*10^4)
--    9998
--    (1.57 secs, 1,636,242,040 bytes)
--    λ> cerosDelFactorial3 (4*10^4)
--    9998
--    (0.02 secs, 527,584 bytes)

module Ceros_finales_del_factorial where

import Data.List (genericLength)

import Test.QuickCheck (Positive (Positive), quickCheck)

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución

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

cerosDelFactorial1 :: Integer -> Integer

cerosDelFactorial1 n = ceros (factorial n)

-- (factorial n) es el factorial n. Por ejemplo,

-- factorial 3 == 6

factorial :: Integer -> Integer

factorial n = product [1..n]

-- (ceros n) es el número de ceros en los que termina el número n. Por

-- ejemplo,

-- ceros 320000 == 4

ceros :: Integer -> Integer

ceros n | rem n 10 /= 0 = 0

| otherwise = 1 + ceros (div n 10)

-- 2ª solución

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

cerosDelFactorial2 :: Integer -> Integer

cerosDelFactorial2 = ceros2 . factorial

ceros2 :: Integer -> Integer

ceros2 n = genericLength (takeWhile (=='0') (reverse (show n)))

-- 3ª solución

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

cerosDelFactorial3 :: Integer -> Integer

cerosDelFactorial3 n

| n < 5 = 0

| otherwise = m + cerosDelFactorial3 m

where m = n `div` 5

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: (Integer -> Integer) -> Spec

specG cerosDelFactorial = do

it "e1" $

cerosDelFactorial 24 `shouldBe` 4

it "e2" $

cerosDelFactorial 25 `shouldBe` 6

spec :: Spec

spec = do

describe "def. 1" $ specG cerosDelFactorial1

describe "def. 2" $ specG cerosDelFactorial2

describe "def. 3" $ specG cerosDelFactorial3

-- La verificación es

-- λ> verifica

-- 6 examples, 0 failures

-- Comprobación de equivalencia

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

-- La propiedad es

prop_cerosDelFactorial :: Positive Integer -> Bool

prop_cerosDelFactorial (Positive n) =

all (== cerosDelFactorial1 n)

[cerosDelFactorial2 n,

cerosDelFactorial3 n]

-- La comprobación es

-- λ> quickCheck prop_cerosDelFactorial

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> cerosDelFactorial1 (4*10^4)

-- 9998

-- (1.93 secs, 2,296,317,904 bytes)

-- λ> cerosDelFactorial2 (4*10^4)

-- 9998

-- (1.57 secs, 1,636,242,040 bytes)

-- λ> cerosDelFactorial3 (4*10^4)

-- 9998

-- (0.02 secs, 527,584 bytes)

Soluciones en Python

from itertools import takewhile
from math import factorial
from sys import set_int_max_str_digits
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

set_int_max_str_digits(10**6)

# 1ª solución
# ===========

# ceros(n) es el número de ceros en los que termina el número n. Por
# ejemplo,
#    ceros(320000)  ==  4
def ceros(n: int) -> int:
    r = 0
    while n % 10 == 0 and n != 0:
        r += 1
        n //= 10
    return r

def cerosDelFactorial1(n: int) -> int:
    return ceros(factorial(n))

# 2ª solución
# ===========

def ceros2(n: int) -> int:
    return len(list(takewhile(lambda x: x == '0', reversed(str(n)))))

def cerosDelFactorial2(n: int) -> int:
    return ceros2(factorial(n))

# 3ª solución
# =============

def cerosDelFactorial3(n: int) -> int:
    r = 0
    while n >= 5:
        n = n // 5
        r += n
    return r

# Verificación
# ============

def test_cerosDelFactorial() -> None:
    for cerosDelFactorial in [cerosDelFactorial1,
                              cerosDelFactorial2,
                              cerosDelFactorial3]:
        assert cerosDelFactorial(24) == 4
        assert cerosDelFactorial(25) == 6
    print("Verificado")

# La verificación es
#    >>> test_cerosDelFactorial()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=1000))
def test_cerosDelFactorial_equiv(n: int) -> None:
    r = cerosDelFactorial1(n)
    assert cerosDelFactorial2(n) == r
    assert cerosDelFactorial3(n) == r

# La comprobación es
#    >>> test_cerosDelFactorial_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('cerosDelFactorial1(6*10**4)')
#    2.47 segundos
#    >>> tiempo('cerosDelFactorial2(6*10**4)')
#    0.77 segundos
#    >>> tiempo('cerosDelFactorial3(6*10**4)')
#    0.00 segundos

# Comprobación de todas las propiedades
# =====================================

# La comprobación es
#    src> poetry run pytest -v Ceros_finales_del_factorial.py
#       test_cerosDelFactorial PASSED
#       test_cerosDelFactorial_equiv PASSED

from itertools import takewhile

from math import factorial

from sys import set_int_max_str_digits

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

set_int_max_str_digits(10**6)

# 1ª solución

# ===========

# ceros(n) es el número de ceros en los que termina el número n. Por

# ejemplo,

# ceros(320000) == 4

def ceros(n: int) -> int:

r = 0

while n % 10 == 0 and n != 0:

r += 1

n //= 10

return r

def cerosDelFactorial1(n: int) -> int:

return ceros(factorial(n))

# 2ª solución

# ===========

def ceros2(n: int) -> int:

return len(list(takewhile(lambda x: x == '0', reversed(str(n)))))

def cerosDelFactorial2(n: int) -> int:

return ceros2(factorial(n))

# 3ª solución

# =============

def cerosDelFactorial3(n: int) -> int:

r = 0

while n >= 5:

n = n // 5

r += n

return r

# Verificación

# ============

def test_cerosDelFactorial() -> None:

for cerosDelFactorial in [cerosDelFactorial1,

cerosDelFactorial2,

cerosDelFactorial3]:

assert cerosDelFactorial(24) == 4

assert cerosDelFactorial(25) == 6

print("Verificado")

# La verificación es

# >>> test_cerosDelFactorial()

# Verificado

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=0, max_value=1000))

def test_cerosDelFactorial_equiv(n: int) -> None:

r = cerosDelFactorial1(n)

assert cerosDelFactorial2(n) == r

assert cerosDelFactorial3(n) == r

# La comprobación es

# >>> test_cerosDelFactorial_equiv()

# >>>

# Comparación de eficiencia

# =========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('cerosDelFactorial1(6*10**4)')

# 2.47 segundos

# >>> tiempo('cerosDelFactorial2(6*10**4)')

# 0.77 segundos

# >>> tiempo('cerosDelFactorial3(6*10**4)')

# 0.00 segundos

# Comprobación de todas las propiedades

# =====================================

# La comprobación es

# src> poetry run pytest -v Ceros_finales_del_factorial.py

# test_cerosDelFactorial PASSED

# test_cerosDelFactorial_equiv PASSED

Ceros finales del factorial

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico