El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 2⁴ divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

El menor número, módulo 100, con 2⁴ divisores es el 20, ya que el menor número con 16 divisores es el 120 y 120 módulo 100 es 20.

Definir la función

menor :: Integer -> Integer -> Integer

tal que (menor n m) es el menor número, módulo m, con 2^n divisores; es decir, es el resto de dividir entre m el menor número con 2^n divisores. Por ejemplo,

menor 4 1000                    ==  120
menor 4 100                     ==  20
[menor n (10^9) | n <- [1..8]]  ==  [2,6,24,120,840,7560,83160,1081080]
menor 500500 500500506          ==  8728302

Leer más…

Definir la función

sumaDePrimos :: Int -> [[Int]]

tal que (sumaDePrimos x) es la lista de las listas no crecientes de números primos que suman x. Por ejemplo,

sumaDePrimos 10  ==  [[7,3],[5,5],[5,3,2],[3,3,2,2],[2,2,2,2,2]]
sumaDePrimos 0   ==  []
sumaDePrimos 1   ==  []

Leer más…

Definir, por simulación, la función

distanciaEsperada :: Int -> Double

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

distanciaEsperada 10    ==  0.4815946544198219
distanciaEsperada 10    ==  0.5558438642543654
distanciaEsperada 100   ==  0.5699663553203216
distanciaEsperada 100   ==  0.5085629461572269
distanciaEsperada 1000  ==  0.5376963424746385
distanciaEsperada 1000  ==  0.523432374720393

Nota. El valor exacto de la distancia esperada es

(sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207

Leer más…

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

• (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

• (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo).

Leer más…

En el juego de las bolas de Dijkstra se dispone de una bolsa con bolas blancas y negras. El juego consiste en elegir al azar dos bolas de la bolsa y añadir una bola negra si las dos bolas elegidas son del mismo color o una bola blanca en caso contrario. El juego termina cuando queda sólo una bola en la bolsa.

Vamos a representar las bolas blancas por 0, las negras por 1 y la bolsa la representaremos por una lista cuyos elementos son 0 ó 1.

Definir las funciones

juego  :: [Int] -> [[Int]]
ultima :: [Int] -> Int

tales que

• (juego xs) es la lista de los pasos aleatorios de un juego de Dijkstra a partir de la lista xs. Por ejemplo,

juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]
juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]
juego [1,0,0,0,1]  ==  [[1,0,0,0,1],[0,0,0,1],[0,1,1],[1,0],[0]]
juego [1,0,1,1,1]  ==  [[1,0,1,1,1],[1,1,0,1],[1,0,1],[0,1],[0]]

• (ultima xs) es la bola que queda en la bolsa al final del juego de Dijkstra a partir de xs. Por ejemplo,

ultima [1,1,0,0,1]  ==  1
ultima [1,0,0,0,1]  ==  0
ultima [1,0,1,1,1]  ==  0

Comprobar con QuickCheck que la bola que queda en la bolsa al final del juego de Dijkstra es blanca si, y sólo si, el número de bolas blancas en la bolsa inicial es impar.

Leer más…

Una matriz latina de orden n es una matriz cuadrada de orden n tal que todos sus elementos son cero salvo los de su fila y columna central, si n es impar; o los de sus dos filas y columnas centrales, si n es par.

Definir la función

latina :: Int -> Array (Int,Int) Int

tal que (latina n) es la siguiente matriz latina de orden n:

• Para n impar:

| 0  0... 0 1   0 ... 0   0|
| 0  0... 0 2   0 ... 0   0|
| 0  0... 0 3   0 ... 0   0|
| .........................|
| 1  2..............n-1   n|
| .........................|
| 0  0... 0 n-2 0 ... 0   0|
| 0  0... 0 n-1 0 ... 0   0|
| 0  0... 0 n   0 ... 0   0|

• Para n par:

| 0  0... 0 1   n    0 ...   0   0|
| 0  0... 0 2   n-1  0 ...   0   0|
| 0  0... 0 3   n-2  0 ...   0   0|
| ................................|
| 1  2.....................n-1   n|
| n n-1 .................... 2   1|
| ................................|
| 0  0... 0 n-2  3   0 ...   0   0|
| 0  0... 0 n-1  2   0 ...   0   0|
| 0  0... 0 n    1   0 ...   0   0|

Por ejemplo,

λ> elems (latina 5)
[0,0,1,0,0,
 0,0,2,0,0,
 1,2,3,4,5,
 0,0,4,0,0,
 0,0,5,0,0]
λ> elems (latina 6)
[0,0,1,6,0,0,
 0,0,2,5,0,0,
 1,2,3,4,5,6,
 6,5,4,3,2,1,
 0,0,5,2,0,0,
 0,0,6,1,0,0]

Leer más…

Definir la función

refina :: Ord a => Monticulo a -> [a -> Bool] -> Monticulo a

tal que (refina m ps) es el montículo formado por los elementos del montículo m que cumplen todos los predicados de la lista ps. Por ejemplo,

λ> refina (foldr inserta vacio [1..22]) [(<7), even]
M 2 1 (M 4 1 (M 6 1 Vacio Vacio) Vacio) Vacio
λ> refina (foldr inserta vacio [1..22]) [(<1), even]
Vacio

Leer más…

La notas de un examen se pueden representar mediante un vector en el que los valores son los pares formados por los nombres de los alumnos y sus notas.

Definir la función

aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]

tal que (aprobados p) es la lista de los nombres de los alumnos que han aprobado y Nothing si todos están suspensos. Por ejemplo,

λ> aprobados (listArray (1,3) [("Ana",5),("Pedro",3),("Lucia",6)])
Just ["Ana","Lucia"]
λ> aprobados (listArray (1,3) [("Ana",4),("Pedro",3),("Lucia",4.9)])
Nothing

Leer más…

El sistema D'Hondt es una fórmula electoral, creada por Victor d'Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

reparto :: Int -> [Int] -> [(Int,Int)]

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

λ> reparto 7 [340000,280000,160000,60000,15000]
[(1,3),(2,3),(3,1)]
λ> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
[(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

• al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
• al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
• al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Leer más…

Un número tiene una inversión cuando existe un dígito x a la derecha de otro dígito de forma que x es menor que y. Por ejemplo, en el número 1745 hay dos inversiones ya que 4 es menor que 7 y 5 es menor que 7 y están a la derecha de 7.

Definir la función

nInversiones :: Integer -> Int

tal que (nInversiones n) es el número de inversiones de n. Por ejemplo,

nInversiones 1745  ==  2

Leer más…