Haskell y Python

Límites de sucesiones

PorJosé A. Alonso 14-noviembre-20235-noviembre-2023

Definir la función

   limite :: (Double -> Double) -> Double -> Double

1	limite :: (Double -> Double) -> Double -> Double

tal que limite f a es el valor de f en el primer término x tal que, para todo y entre x+1 y x+100, el valor absoluto de la diferencia entre f(y) y f(x) es menor que a. Por ejemplo,

   limite (\n -> (2*n+1)/(n+5)) 0.001  ==  1.9900110987791344
   limite (\n -> (1+1/n)**n) 0.001     ==  2.714072874546881

1 2	limite (\n -> (2n+1)/(n+5)) 0.001 == 1.9900110987791344 limite (\n -> (1+1/n)*n) 0.001 == 2.714072874546881

Soluciones

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

Soluciones en Haskell

module Limites_de_sucesiones where

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

limite :: (Double -> Double) -> Double -> Double
limite f a =
  head [f x | x <- [1..],
              maximum [abs (f y - f x) | y <- [x+1..x+100]] < a]

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    limite (\n -> (2*n+1)/(n+5)) 0.001  `shouldBe`  1.9900110987791344
  it "e2" $
    limite (\n -> (1+1/n)**n) 0.001     `shouldBe`  2.714072874546881

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.1927 seconds
--    2 examples, 0 failures

module Limites_de_sucesiones where

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

limite :: (Double -> Double) -> Double -> Double

limite f a =

head [f x | x <- [1..],

maximum [abs (f y - f x) | y <- [x+1..x+100]] < a]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

limite (\n -> (2*n+1)/(n+5)) 0.001 `shouldBe` 1.9900110987791344

it "e2" $

limite (\n -> (1+1/n)**n) 0.001 `shouldBe` 2.714072874546881

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.1927 seconds

-- 2 examples, 0 failures

Soluciones en Python

from itertools import count
from typing import Callable

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

def limite(f: Callable[[float], float], a: float) -> float:
    x = 1
    while True:
        maximum_diff = max(abs(f(y) - f(x)) for y in range(x+1, x+101))
        if maximum_diff < a:
            return f(x)
        x += 1

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

def limite2(f: Callable[[float], float], a: float) -> float:
    x = 1
    while True:
        y = f(x)
        if max(abs(y - f(x + i)) for i in range(1, 101)) < a:
            break
        x += 1
    return y

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

def limite3(f: Callable[[float], float], a: float) -> float:
    for x in count(1):
        if max(abs(f(y) - f(x)) for y in range(x + 1, x + 101)) < a:
            r = f(x)
            break
    return r

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

def test_limite() -> None:
    assert limite(lambda n :  (2*n+1)/(n+5), 0.001) ==  1.9900110987791344
    assert limite(lambda n : (1+1/n)**n, 0.001)     ==  2.714072874546881
    assert limite2(lambda n :  (2*n+1)/(n+5), 0.001) ==  1.9900110987791344
    assert limite2(lambda n : (1+1/n)**n, 0.001)     ==  2.714072874546881
    assert limite3(lambda n :  (2*n+1)/(n+5), 0.001) ==  1.9900110987791344
    assert limite3(lambda n : (1+1/n)**n, 0.001)     ==  2.714072874546881
    print("Verificado")

# La comprobación es
#    >>> test_limite()
#    Verificado

from itertools import count

from typing import Callable

# 1ª solución

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

def limite(f: Callable[[float], float], a: float) -> float:

x = 1

while True:

maximum_diff = max(abs(f(y) - f(x)) for y in range(x+1, x+101))

if maximum_diff < a:

return f(x)

x += 1

# 2ª solución

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

def limite2(f: Callable[[float], float], a: float) -> float:

x = 1

while True:

y = f(x)

if max(abs(y - f(x + i)) for i in range(1, 101)) < a:

break

x += 1

return y

# 3ª solución

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

def limite3(f: Callable[[float], float], a: float) -> float:

for x in count(1):

if max(abs(f(y) - f(x)) for y in range(x + 1, x + 101)) < a:

r = f(x)

break

return r

# Verificación

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

def test_limite() -> None:

assert limite(lambda n : (2*n+1)/(n+5), 0.001) == 1.9900110987791344

assert limite(lambda n : (1+1/n)**n, 0.001) == 2.714072874546881

assert limite2(lambda n : (2*n+1)/(n+5), 0.001) == 1.9900110987791344

assert limite2(lambda n : (1+1/n)**n, 0.001) == 2.714072874546881

assert limite3(lambda n : (2*n+1)/(n+5), 0.001) == 1.9900110987791344

assert limite3(lambda n : (1+1/n)**n, 0.001) == 2.714072874546881

print("Verificado")

# La comprobación es

# >>> test_limite()

# Verificado

Funciones inversas por el método de Newton

PorJosé A. Alonso 9-noviembre-20232-noviembre-2023

Definir, usando puntoCero, la función

   inversa :: (Double -> Double) -> Double -> Double

1	inversa :: (Double -> Double) -> Double -> Double

tal que inversa g x es el valor de la inversa de g en x. Por ejemplo,

   inversa (^2) 9  ==  3.000000002941184

1	inversa (^2) 9 == 3.000000002941184

Definir, usando inversa, las funciones raizCuadrada, raizCubica, arcoseno y arcocoseno que calculen la raíz cuadrada, la raíz cúbica, el arco seno y el arco coseno, respectivamente. Por ejemplo,

   raizCuadrada 9  ==  3.000000002941184
   raizCubica 27   ==  3.0000000000196048
   arcoseno 1      ==  1.5665489428306574
   arcocoseno 0    ==  1.5707963267949576

raizCuadrada 9 == 3.000000002941184

raizCubica 27 == 3.0000000000196048

arcoseno 1 == 1.5665489428306574

arcocoseno 0 == 1.5707963267949576

Soluciones

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

Soluciones en Haskell

module Funciones_inversas_por_el_metodo_de_Newton where

import Metodo_de_Newton_para_calcular_raices (puntoCero)
import Test.Hspec (Spec, hspec, it, shouldBe)

inversa :: (Double -> Double) -> Double -> Double
inversa g a = puntoCero f
  where f x = g x - a

raizCuadrada, raizCubica, arcoseno, arcocoseno :: Double -> Double
raizCuadrada = inversa (^2)
raizCubica   = inversa (^3)
arcoseno     = inversa sin
arcocoseno   = inversa cos

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    inversa (^2) 9  `shouldBe`  3.000000002941184
  it "e2" $
    raizCuadrada 9  `shouldBe`  3.000000002941184
  it "e3" $
    raizCubica 27   `shouldBe`  3.0000000000196048
  it "e4" $
    arcoseno 1      `shouldBe`  1.5665489428306574
  it "e5" $
    arcocoseno 0    `shouldBe`  1.5707963267949576

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--
--    Finished in 0.0006 seconds
--    5 examples, 0 failures

module Funciones_inversas_por_el_metodo_de_Newton where

import Metodo_de_Newton_para_calcular_raices (puntoCero)

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

inversa :: (Double -> Double) -> Double -> Double

inversa g a = puntoCero f

where f x = g x - a

raizCuadrada, raizCubica, arcoseno, arcocoseno :: Double -> Double

raizCuadrada = inversa (^2)

raizCubica = inversa (^3)

arcoseno = inversa sin

arcocoseno = inversa cos

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

inversa (^2) 9 `shouldBe` 3.000000002941184

it "e2" $

raizCuadrada 9 `shouldBe` 3.000000002941184

it "e3" $

raizCubica 27 `shouldBe` 3.0000000000196048

it "e4" $

arcoseno 1 `shouldBe` 1.5665489428306574

it "e5" $

arcocoseno 0 `shouldBe` 1.5707963267949576

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- Finished in 0.0006 seconds

-- 5 examples, 0 failures

Soluciones en Python

from math import cos, sin
from typing import Callable

from src.Metodo_de_Newton_para_calcular_raices import puntoCero


def inversa(g: Callable[[float],float], a: float) -> float:
    def f(x: float) -> float:
        return g(x) - a
    return puntoCero(f)

def raizCuadrada(x: float) -> float:
    return inversa(lambda y: y**2, x)

def raizCubica(x: float) -> float:
    return inversa(lambda y: y**3, x)

def arcoseno(x: float) -> float:
    return inversa(sin, x)

def arcocoseno(x: float) -> float:
    return inversa(cos, x)

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

def test_inversa() -> None:
    assert inversa(lambda x: x**2, 9) == 3.000000002941184
    assert raizCuadrada(9) == 3.000000002941184
    assert raizCubica(27) == 3.0000000000196048
    assert arcoseno(1) == 1.5665489428306574
    assert arcocoseno(0) == 1.5707963267949576
    print("Verificado")

# La comprobación es
#    >>> test_inversa()
#    Verificado

from math import cos, sin

from typing import Callable

from src.Metodo_de_Newton_para_calcular_raices import puntoCero

def inversa(g: Callable[[float],float], a: float) -> float:

def f(x: float) -> float:

return g(x) - a

return puntoCero(f)

def raizCuadrada(x: float) -> float:

return inversa(lambda y: y**2, x)

def raizCubica(x: float) -> float:

return inversa(lambda y: y**3, x)

def arcoseno(x: float) -> float:

return inversa(sin, x)

def arcocoseno(x: float) -> float:

return inversa(cos, x)

# Verificación

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

def test_inversa() -> None:

assert inversa(lambda x: x**2, 9) == 3.000000002941184

assert raizCuadrada(9) == 3.000000002941184

assert raizCubica(27) == 3.0000000000196048

assert arcoseno(1) == 1.5665489428306574

assert arcocoseno(0) == 1.5707963267949576

print("Verificado")

# La comprobación es

# >>> test_inversa()

# Verificado

Método de Newton para calcular raíces

PorJosé A. Alonso 4-noviembre-202329-octubre-2023

Los ceros de una función pueden calcularse mediante el método de Newton basándose en las siguientes propiedades:

Si $b$ es una aproximación para el punto cero de $f$, entonces
\[ b-\frac{f(b)}{f'(b)} \]
donde $f’$ es la derivada de $f$, es una mejor aproximación.
el límite de la sucesión $x_n$ definida por
\begin{align}
x_0 &= 1 \\
x_{n+1} &= x_n-\frac{f(x_n)}{f'(x_n)}
\end{align}
es un cero de $f$.

Definir la función

   puntoCero :: (Double -> Double) -> Double

1	puntoCero :: (Double -> Double) -> Double

tal que puntoCero f es un cero de la función f calculado usando la propiedad anterior. Por ejemplo,

   puntoCero cos  ==  1.5707963267949576

1	puntoCero cos == 1.5707963267949576

Soluciones

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

Soluciones en Haskell

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

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

puntoCero :: (Double -> Double) -> Double
puntoCero f = puntoCeroAux f 1
  where puntoCeroAux f' x | aceptable x = x
                          | otherwise   = puntoCeroAux f' (mejora x)
        aceptable b = abs (f b) < 0.00001
        mejora b    = b - f b / derivada f b

-- (derivada f x) es el valor de la derivada de la función f en el punto
-- x con aproximación 0.0001. Por ejemplo,
--    derivada sin pi == -0.9999999983354435
--    derivada cos pi == 4.999999969612645e-5
derivada :: (Double -> Double) -> Double -> Double
derivada f x = (f (x+a) - f x)/a
  where a = 0.0001

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

puntoCero2 :: (Double -> Double) -> Double
puntoCero2 f = until aceptable mejora 1
  where aceptable b = abs (f b) < 0.00001
        mejora b    = b - f b / derivada f b

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    puntoCero cos `shouldBe` 1.5707963267949576
  it "e2" $
    puntoCero2 cos `shouldBe` 1.5707963267949576

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0002 seconds
--    2 examples, 0 failures

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

-- 1ª solución

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

puntoCero :: (Double -> Double) -> Double

puntoCero f = puntoCeroAux f 1

where puntoCeroAux f' x | aceptable x = x

| otherwise = puntoCeroAux f' (mejora x)

aceptable b = abs (f b) < 0.00001

mejora b = b - f b / derivada f b

-- (derivada f x) es el valor de la derivada de la función f en el punto

-- x con aproximación 0.0001. Por ejemplo,

-- derivada sin pi == -0.9999999983354435

-- derivada cos pi == 4.999999969612645e-5

derivada :: (Double -> Double) -> Double -> Double

derivada f x = (f (x+a) - f x)/a

where a = 0.0001

-- 2ª solución

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

puntoCero2 :: (Double -> Double) -> Double

puntoCero2 f = until aceptable mejora 1

where aceptable b = abs (f b) < 0.00001

mejora b = b - f b / derivada f b

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

puntoCero cos `shouldBe` 1.5707963267949576

it "e2" $

puntoCero2 cos `shouldBe` 1.5707963267949576

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0002 seconds

-- 2 examples, 0 failures

Soluciones en Python

from math import cos, pi, sin
from typing import Callable

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

# derivada(f, x) es el valor de la derivada de la función f en el punto
# x con aproximación 0.0001. Por ejemplo,
#    derivada(sin, pi) == -0.9999999983354435
#    derivada(cos, pi) == 4.999999969612645e-5
def derivada(f: Callable[[float], float], x: float) -> float:
    a = 0.0001
    return (f(x+a) - f(x)) / a

def puntoCero(f: Callable[[float], float]) -> float:
    def aceptable(b: float) -> bool:
        return abs(f(b)) < 0.00001
    def mejora(b: float) -> float:
        return b - f(b) / derivada(f, b)
    def aux(g: Callable[[float], float], x: float) -> float:
        if aceptable(x):
            return x
        return aux(g, mejora(x))
    return aux(f, 1)

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

def puntoCero2(f: Callable[[float], float]) -> float:
    def aceptable(b: float) -> bool:
        return abs(f(b)) < 0.00001
    def mejora(b: float) -> float:
        return b - f(b) / derivada(f, b)
    y = 1.0
    while not aceptable(y):
        y = mejora(y)
    return y

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

def test_puntoCero () -> None:
    assert puntoCero(cos) == 1.5707963267949576
    assert puntoCero(cos) - pi/2 == 6.106226635438361e-14
    assert puntoCero(sin) == -5.8094940533562345e-15
    assert puntoCero2(cos) == 1.5707963267949576
    assert puntoCero2(cos) - pi/2 == 6.106226635438361e-14
    assert puntoCero2(sin) == -5.8094940533562345e-15
    print("Verificado")

# La comprobación es
#    >>> test_puntoCero()
#    Verificado

from math import cos, pi, sin

from typing import Callable

# 1ª solución

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

# derivada(f, x) es el valor de la derivada de la función f en el punto

# x con aproximación 0.0001. Por ejemplo,

# derivada(sin, pi) == -0.9999999983354435

# derivada(cos, pi) == 4.999999969612645e-5

def derivada(f: Callable[[float], float], x: float) -> float:

a = 0.0001

return (f(x+a) - f(x)) / a

def puntoCero(f: Callable[[float], float]) -> float:

def aceptable(b: float) -> bool:

return abs(f(b)) < 0.00001

def mejora(b: float) -> float:

return b - f(b) / derivada(f, b)

def aux(g: Callable[[float], float], x: float) -> float:

if aceptable(x):

return x

return aux(g, mejora(x))

return aux(f, 1)

# 2ª solución

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

def puntoCero2(f: Callable[[float], float]) -> float:

def aceptable(b: float) -> bool:

return abs(f(b)) < 0.00001

def mejora(b: float) -> float:

return b - f(b) / derivada(f, b)

y = 1.0

while not aceptable(y):

y = mejora(y)

return y

# Verificación

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

def test_puntoCero () -> None:

assert puntoCero(cos) == 1.5707963267949576

assert puntoCero(cos) - pi/2 == 6.106226635438361e-14

assert puntoCero(sin) == -5.8094940533562345e-15

assert puntoCero2(cos) == 1.5707963267949576

assert puntoCero2(cos) - pi/2 == 6.106226635438361e-14

assert puntoCero2(sin) == -5.8094940533562345e-15

print("Verificado")

# La comprobación es

# >>> test_puntoCero()

# Verificado

Método de Herón para calcular la raíz cuadrada

PorJosé A. Alonso 29-octubre-202320-octubre-2023

El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:

Si $y$ es una aproximación de la raíz cuadrada de $x$, entonces
\[\frac{y+\frac{x}{y}}{2}\] es una aproximación mejor.
El límite de la sucesión definida por
\begin{align}
x_{0} &= 1 \\
x_{n+1} &= \frac{x_n+\frac{x}{x_n}}{2}
\end{align}
es la raíz cuadrada de x.

Definir la función

   raiz :: Double -> Double

1	raiz :: Double -> Double

tal que raiz x es la raíz cuadrada de x calculada usando la propiedad anterior con una aproximación de 0.00001 y tomando como valor inicial 1. Por ejemplo,

   raiz 9  ==  3.000000001396984

1	raiz 9 == 3.000000001396984

Soluciones

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

Soluciones en Haskell

module Metodo_de_Heron_para_calcular_la_raiz_cuadrada where

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

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

raiz :: Double -> Double
raiz x = raizAux 1
  where raizAux y | aceptable y = y
                  | otherwise   = raizAux (mejora y)
        aceptable y = abs(y*y-x) < 0.00001
        mejora y    = 0.5*(y+x/y)

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

raiz2 :: Double -> Double
raiz2 x = until aceptable mejora 1
  where aceptable y = abs(y*y-x) < 0.00001
        mejora y    = 0.5*(y+x/y)

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

-- La propiedad es
prop_raiz :: Positive Double -> Bool
prop_raiz (Positive x) =
  raiz x ~= sqrt x &&
  raiz2 x ~= sqrt x
  where
    a ~= b = abs (a-b) < 0.001

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

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    raiz 9 `shouldBe`  3.000000001396984
  it "e2" $
    raiz2 9 `shouldBe`  3.000000001396984

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0008 seconds
--    2 examples, 0 failures

module Metodo_de_Heron_para_calcular_la_raiz_cuadrada where

import Test.QuickCheck

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

-- 1ª solución

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

raiz :: Double -> Double

raiz x = raizAux 1

where raizAux y | aceptable y = y

| otherwise = raizAux (mejora y)

aceptable y = abs(y*y-x) < 0.00001

mejora y = 0.5*(y+x/y)

-- 2ª solución

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

raiz2 :: Double -> Double

raiz2 x = until aceptable mejora 1

where aceptable y = abs(y*y-x) < 0.00001

mejora y = 0.5*(y+x/y)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_raiz :: Positive Double -> Bool

prop_raiz (Positive x) =

raiz x ~= sqrt x &&

raiz2 x ~= sqrt x

where

a ~= b = abs (a-b) < 0.001

-- La comprobación es

-- λ> quickCheck prop_raiz

-- +++ OK, passed 100 tests.

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

raiz 9 `shouldBe` 3.000000001396984

it "e2" $

raiz2 9 `shouldBe` 3.000000001396984

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0008 seconds

-- 2 examples, 0 failures

Soluciones en Python

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

def raiz(x : float) -> float:
    def aceptable(y: float) -> bool:
        return abs(y*y-x) < 0.00001
    def mejora(y: float) -> float:
        return 0.5*(y+x/y)
    def raizAux(y: float) -> float:
        if aceptable(y):
            return y
        return raizAux(mejora(y))
    return raizAux(1)

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

def raiz2(x: float) -> float:
    def aceptable(y: float) -> bool:
        return abs(y*y-x) < 0.00001
    def mejora(y: float) -> float:
        return 0.5*(y+x/y)
    y = 1.0
    while not aceptable(y):
        y = mejora(y)
    return y

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

def test_raiz() -> None:
    assert raiz(9)  ==  3.000000001396984
    assert raiz2(9)  ==  3.000000001396984
    print("Verificado")

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

# 1ª solución

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

def raiz(x : float) -> float:

def aceptable(y: float) -> bool:

return abs(y*y-x) < 0.00001

def mejora(y: float) -> float:

return 0.5*(y+x/y)

def raizAux(y: float) -> float:

if aceptable(y):

return y

return raizAux(mejora(y))

return raizAux(1)

# 2ª solución

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

def raiz2(x: float) -> float:

def aceptable(y: float) -> bool:

return abs(y*y-x) < 0.00001

def mejora(y: float) -> float:

return 0.5*(y+x/y)

y = 1.0

while not aceptable(y):

y = mejora(y)

return y

# Verificación

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

def test_raiz() -> None:

assert raiz(9) == 3.000000001396984

assert raiz2(9) == 3.000000001396984

print("Verificado")

# La verificación es

# >>> test_raiz()

# Verificado

Camino de máxima suma en una matriz

PorJosé A. Alonso 24-octubre-20236-octubre-2023

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:

   [1,6,11,2,8,9]
   [1,6,11,3,8,9]
   [1,6,12,3,8,9]
   [1,7,12,3,8,9]
   [1,6,11,3,4,9]
   [1,6,12,3,4,9]
   [1,7,12,3,4,9]
   [1,6,12,8,4,9]
   [1,7,12,8,4,9]
   [1,7, 3,8,4,9]

[1,6,11,2,8,9]

[1,6,11,3,8,9]

[1,6,12,3,8,9]

[1,7,12,3,8,9]

[1,6,11,3,4,9]

[1,6,12,3,4,9]

[1,7,12,3,4,9]

[1,6,12,8,4,9]

[1,7,12,8,4,9]

[1,7, 3,8,4,9]

La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

   caminoMaxSuma :: Matrix Int -> [Int]

1	caminoMaxSuma :: Matrix Int -> [Int]

tal que caminoMaxSuma m es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

   λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [1,7,12,8,4,9]
   λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
   187001249

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

[1,7,12,8,4,9]

λ> sum (caminoMaxSuma (fromList 500 500 [1..]))

187001249

Soluciones

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

Soluciones en Haskell

module Camino_de_maxima_suma_en_una_matriz where

import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición de caminoMaxSuma (con caminos1)
-- =============================================

caminoMaxSuma1 :: Matrix Int -> [Int]
caminoMaxSuma1 m =
  head [c | c <- cs, sum c == k]
  where cs = caminos1 m
        k  = maximum (map sum cs)

caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
  reverse (map reverse (caminos1Aux m (nf,nc)))
  where nf = nrows m
        nc = ncols m

-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m
-- desde la posición (1,1) hasta la posición p. Por ejemplo,
caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]
caminos1Aux m (1,1) = [[m!(1,1)]]
caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]
caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]
caminos1Aux m (i,j) = [m!(i,j) : xs
                      | xs <- caminos1Aux m (i,j-1) ++
                              caminos1Aux m (i-1,j)]

-- 2ª definición de caminoMaxSuma (con caminos2)
-- =============================================

caminoMaxSuma2 :: Matrix Int -> [Int]
caminoMaxSuma2 m =
  head [c | c <- cs, sum c == k]
  where cs = caminos2 m
        k  = maximum (map sum cs)

caminos2 :: Matrix Int -> [[Int]]
caminos2 m =
  map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = q
  where
    q = matrix (nrows m) (ncols m) f
    f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]
    f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]
    f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]

-- 3ª definición de caminoMaxSuma (con programación dinámica)
-- ==========================================================

caminoMaxSuma3 :: Matrix Int -> [Int]
caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))
  where nf = nrows m
        nc = ncols m
        q  = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])
caminoMaxSumaAux m = q
  where
    nf = nrows m
    nc = ncols m
    q  = matrix nf nc f
      where
        f (1,1) = (m!(1,1),[m!(1,1)])
        f (1,j) = (k + m!(1,j), m!(1,j):xs)
          where (k,xs) = q!(1,j-1)
        f (i,1) = (k + m!(i,1), m!(i,1):xs)
          where (k,xs) = q!(i-1,1)
        f (i,j) | k1 > k2   = (k1 + m!(i,j), m!(i,j):xs)
                | otherwise = (k2 + m!(i,j), m!(i,j):ys)
          where (k1,xs) = q!(i,j-1)
                (k2,ys) = q!(i-1,j)

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

-- La comparación es
--    λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))
--    21
--    (3.92 secs, 1,778,557,904 bytes)
--    λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))
--    21
--    (1.16 secs, 798,889,488 bytes)
--    λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))
--    21
--    (0.00 secs, 680,256 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]
  it "e2" $
    caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]
  it "e3" $
    caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0007 seconds
--    3 examples, 0 failures

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

module Camino_de_maxima_suma_en_una_matriz where

import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)

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

-- 1ª definición de caminoMaxSuma (con caminos1)

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

caminoMaxSuma1 :: Matrix Int -> [Int]

caminoMaxSuma1 m =

head [c | c <- cs, sum c == k]

where cs = caminos1 m

k = maximum (map sum cs)

caminos1 :: Matrix Int -> [[Int]]

caminos1 m =

reverse (map reverse (caminos1Aux m (nf,nc)))

where nf = nrows m

nc = ncols m

-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m

-- desde la posición (1,1) hasta la posición p. Por ejemplo,

caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]

caminos1Aux m (1,1) = [[m!(1,1)]]

caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]

caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]

caminos1Aux m (i,j) = [m!(i,j) : xs

| xs <- caminos1Aux m (i,j-1) ++

caminos1Aux m (i-1,j)]

-- 2ª definición de caminoMaxSuma (con caminos2)

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

caminoMaxSuma2 :: Matrix Int -> [Int]

caminoMaxSuma2 m =

head [c | c <- cs, sum c == k]

where cs = caminos2 m

k = maximum (map sum cs)

caminos2 :: Matrix Int -> [[Int]]

caminos2 m =

map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]

matrizCaminos m = q

where

q = matrix (nrows m) (ncols m) f

f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]

f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]

f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]

-- 3ª definición de caminoMaxSuma (con programación dinámica)

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

caminoMaxSuma3 :: Matrix Int -> [Int]

caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))

where nf = nrows m

nc = ncols m

q = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])

caminoMaxSumaAux m = q

where

nf = nrows m

nc = ncols m

q = matrix nf nc f

where

f (1,1) = (m!(1,1),[m!(1,1)])

f (1,j) = (k + m!(1,j), m!(1,j):xs)

where (k,xs) = q!(1,j-1)

f (i,1) = (k + m!(i,1), m!(i,1):xs)

where (k,xs) = q!(i-1,1)

f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs)

| otherwise = (k2 + m!(i,j), m!(i,j):ys)

where (k1,xs) = q!(i,j-1)

(k2,ys) = q!(i-1,j)

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))

-- 21

-- (3.92 secs, 1,778,557,904 bytes)

-- λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))

-- 21

-- (1.16 secs, 798,889,488 bytes)

-- λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))

-- 21

-- (0.00 secs, 680,256 bytes)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

`shouldBe` [1,7,12,8,4,9]

it "e2" $

caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

`shouldBe` [1,7,12,8,4,9]

it "e3" $

caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

`shouldBe` [1,7,12,8,4,9]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0007 seconds

-- 3 examples, 0 failures

Soluciones en Python

from collections import defaultdict
from sys import setrecursionlimit
from timeit import Timer, default_timer

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definición de caminoMaxSuma (con caminos1)
# =============================================

def caminoMaxSuma1(m: list[list[int]]) -> list[int]:
    cs = caminos1(m)
    k = max((sum(c) for c in cs))
    return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos1 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 2ª definición de caminoMaxSuma (con caminos2)
# =============================================

def caminoMaxSuma2(m: list[list[int]]) -> list[int]:
    cs = caminos2(m)
    k = max((sum(c) for c in cs))
    return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos2 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 3ª definición de caminoMaxSuma (con programación dinámica)
# ==========================================================

def caminoMaxSuma3(m: list[list[int]]) -> list[int]:
    nf = len(m)
    nc = len(m[0])
    return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1]))

# diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los
# puntos de la matriz p y sus valores son los pares formados por la
# máxima suma de los caminos hasta dicho punto y uno de los caminos con
# esa suma. Por ejemplo,
#    >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])
#    {(1, 1): (1, [1]),
#     (1, 2): (7, [6, 1]),
#     (1, 3): (18, [11, 6, 1]),
#     (1, 4): (20, [2, 11, 6, 1]),
#     (2, 1): (8, [7, 1]),
#     (3, 1): (11, [3, 7, 1]),
#     (2, 2): (20, [12, 7, 1]),
#     (2, 3): (23, [3, 12, 7, 1]),
#     (2, 4): (31, [8, 3, 12, 7, 1]),
#     (3, 2): (28, [8, 12, 7, 1]),
#     (3, 3): (32, [4, 8, 12, 7, 1]),
#     (3, 4): (41, [9, 4, 8, 12, 7, 1])}
def diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]:
    m = len(p)
    n = len(p[0])
    q: dict[tuple[int, int], tuple[int, list[int]]] = {}
    q[(1, 1)] = (p[0][0], [p[0][0]])
    for j in range(2, n + 1):
        (k, xs) = q[(1, j-1)]
        q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs)
    for i in range(2, m + 1):
        (k,xs) = q[(i-1,1)]
        q[(i, 1)] =  (k + p[i-1][0], [p[i-1][0]] + xs)
    for i in range(2, m + 1):
        for j in range(2, n + 1):
            (k1,xs) = q[(i,j-1)]
            (k2,ys) = q[(i-1,j)]
            if k1 > k2:
                q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs)
            else:
                q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys)
    return q

# 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('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    1.92 segundos
#    >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.65 segundos
#    >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.00 segundos

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

def test_caminoMaxSuma() -> None:
    assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    print("Verificado")

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

100

101

102

103

104

105

106

107

108

109

from collections import defaultdict

from sys import setrecursionlimit

from timeit import Timer, default_timer

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definición de caminoMaxSuma (con caminos1)

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

def caminoMaxSuma1(m: list[list[int]]) -> list[int]:

cs = caminos1(m)

k = max((sum(c) for c in cs))

return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos1 del ejercicio

# "Caminos en una matriz" que se encuentra en

# https://bit.ly/45bYoYE

# 2ª definición de caminoMaxSuma (con caminos2)

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

def caminoMaxSuma2(m: list[list[int]]) -> list[int]:

cs = caminos2(m)

k = max((sum(c) for c in cs))

return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos2 del ejercicio

# "Caminos en una matriz" que se encuentra en

# https://bit.ly/45bYoYE

# 3ª definición de caminoMaxSuma (con programación dinámica)

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

def caminoMaxSuma3(m: list[list[int]]) -> list[int]:

nf = len(m)

nc = len(m[0])

return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1]))

# diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los

# puntos de la matriz p y sus valores son los pares formados por la

# máxima suma de los caminos hasta dicho punto y uno de los caminos con

# esa suma. Por ejemplo,

# >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])

# {(1, 1): (1, [1]),

# (1, 2): (7, [6, 1]),

# (1, 3): (18, [11, 6, 1]),

# (1, 4): (20, [2, 11, 6, 1]),

# (2, 1): (8, [7, 1]),

# (3, 1): (11, [3, 7, 1]),

# (2, 2): (20, [12, 7, 1]),

# (2, 3): (23, [3, 12, 7, 1]),

# (2, 4): (31, [8, 3, 12, 7, 1]),

# (3, 2): (28, [8, 12, 7, 1]),

# (3, 3): (32, [4, 8, 12, 7, 1]),

# (3, 4): (41, [9, 4, 8, 12, 7, 1])}

def diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]:

m = len(p)

n = len(p[0])

q: dict[tuple[int, int], tuple[int, list[int]]] = {}

q[(1, 1)] = (p[0][0], [p[0][0]])

for j in range(2, n + 1):

(k, xs) = q[(1, j-1)]

q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs)

for i in range(2, m + 1):

(k,xs) = q[(i-1,1)]

q[(i, 1)] = (k + p[i-1][0], [p[i-1][0]] + xs)

for i in range(2, m + 1):

for j in range(2, n + 1):

(k1,xs) = q[(i,j-1)]

(k2,ys) = q[(i-1,j)]

if k1 > k2:

q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs)

else:

q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys)

return q

# 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('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')

# 1.92 segundos

# >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')

# 0.65 segundos

# >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')

# 0.00 segundos

# # Verificación

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

def test_caminoMaxSuma() -> None:

assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \

[1, 7, 12, 8, 4, 9]

assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \

[1, 7, 12, 8, 4, 9]

assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \

[1, 7, 12, 8, 4, 9]

print("Verificado")

# La verificación es

# >>> test_caminoMaxSuma()

# Verificado

Límites de sucesiones

Funciones inversas por el método de Newton

Método de Newton para calcular raíces

Método de Herón para calcular la raíz cuadrada

Camino de máxima suma en una matriz

Entradas recientes

Buscar

Correo electrónico