Algoritmo de Euclides del mcd
Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:
1 2 |
mcd(a,b) = a, si b = 0 = mcd (b, a módulo b), si b > 0 |
Definir la función
1 |
mcd :: Integer -> Integer -> Integer |
tal que mcd a b
es el máximo común divisor de a
y b
calculado mediante el algoritmo de Euclides. Por ejemplo,
1 2 |
mcd 30 45 == 15 mcd 45 30 == 15 |
Comprobar con QuickCheck que el máximo común divisor de dos números a
y b
(ambos mayores que 0) es siempre mayor o igual que 1 y además es menor o igual que el menor de los números a
y b
.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import Test.QuickCheck mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd a b = mcd b (a `mod` b) -- La propiedad es prop_mcd :: Positive Integer -> Positive Integer -> Bool prop_mcd (Positive a) (Positive b) = m >= 1 && m <= min a b where m = mcd a b -- La comprobación es -- λ> quickCheck prop_mcd -- OK, passed 100 tests. |
El código se encuentra en GitHub.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
from hypothesis import given from hypothesis import strategies as st def mcd(a: int, b: int) -> int: if b == 0: return a return mcd(b, a % b) # -- La propiedad es @given(st.integers(min_value=1, max_value=1000), st.integers(min_value=1, max_value=1000)) def test_mcd(a: int, b: int) -> None: assert 1 <= mcd(a, b) <= min(a, b) # La comprobación es # src> poetry run pytest -q algoritmo_de_Euclides_del_mcd.py # 1 passed in 0.22s |
El código se encuentra en GitHub.