Caminos en un grafo

Definir las funciones

tales que

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

  • (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,

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

Problema de las bolas de Dijkstra

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

tales que

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

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

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.

Soluciones

Reparto de escaños por la ley d’Hont

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

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,

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.

Soluciones

Ciclos de un grafo

Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),…,v(n)] de nodos de G tal que:

  • (v(1),v(2)), (v(2),v(3)), (v(3),v(4)), …, (v(n-1),v(n)) son aristas de G,
  • v(1) = v(n), y
  • salvo v(1) = v(n), todos los v(i) son distintos entre sí.

Definir la función

tal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por

entonces

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

El teorema de Midy

El ejercicio de hoy, propuesto por Antonio García Blázquez, tiene como objetivo comprobar la veracidad del Teorema de Midy, este teorema dice:

Sea a/p una fracción, donde a < p y p > 5 es un número primo. Si esta fracción tiene una expansión decimal periódica, donde la cantidad de dígitos en el período es par, entonces podemos partir el período en dos mitades, cuya suma es un número formado únicamente por nueves.

Por ejemplo, 2/7 = 0’285714285714… El período es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.

Definir la función

tal que (teoremaMidy n) se verifica si para todo todo número primo p menor que n y mayor que 5 y todo número natural a menor que p tales que la cantidad de dígitos en el período de a/p es par, entonces podemos partir el período de a/p en dos mitades, cuya suma es un número formado únicamente por nueves. Por ejemplo,

Además, comprobar el teorema de Midy usando QuickCheck.

Soluciones

Representación decimal de números racionales

Continuando con los ejercicios propuestos por los alumnos, Antonio García Blázquez ha propuesto un ejercicio que usa el período de los números decimales. El ejercicio de hoy, basado en su propuesta, trata de la representación decimal de los números racionales.

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

Su tipo es

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

Definir las funciones

tales que

  • (decimal r) es la representación decimal del número racional r. Por ejemplo,

  • (racional d) es el número racional cuya representación decimal es d. Por ejemplo,

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

Potencias de primos con exponentes potencias de dos

Se llaman potencias de Fermi-Dirac a los números de la forma p^(2^k), donde p es un número primo y k es un número natural.

Definir la sucesión

cuyos términos sean las potencias de Fermi-Dirac ordenadas de menor a mayor. Por ejemplo,

Soluciones

Fracciones cancelativas

Una fracción x/y es cancelativa si se cumplen las siguientes condiciones:

  • x/y es propia (es decir, x < y),
  • ninguno de los números x e y son múltiplos de 10 y
  • existe un dígito d tal que al borrar una ocurrencia de d en x y otra en y se obtiene una fracción cuyo valor coincide con x/y.

Por ejemplo, 16/64 es cancelativa ya que borrando el 6 en el numerador y el denominador se obtiene 1/4 que es igual a la original: 16/64 = 1/4.

Definir la función

tal que (cancelativas m n) es la lista de las fracciones cancelativas con su denominador entre m y n. Por ejemplo,

Soluciones

Caminos reducidos

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

Definir la función

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

Nótese que en el penúltimo ejemplo las reducciones son

Soluciones

Casas con números equilibrados

Continuando con los problema propuestos por alumnos, el de hoy es el propuesto por Rafael Jiménez.

Se tiene una calle en la que las casas sólo están en un lado de ésta y las casas están numeradas de 1 hasta n, donde n es el número total de casas en la calle. Se dice que el número de una casa es equilibrado si y solamente si la suma de los números de las casas anteriores es igual a la suma de los números posteriores a la casa. Por ejemplo, el número de la 6ª casa, en una calle con 8 casas, es equilibrado ya que

Definir la función

tal que (soluciones x y) es la lista de pares (a,n) tales que a es el número equilibrado de una casa en una calle con n casas y n está entre x e y. Por ejemplo,

Soluciones

Pandigitales múltiplos de un número por una lista de números

Un número pandigital es un número que contiene todos los dígitos del 1 al 9 sólo una vez. Por ejemplo, 192384576 es un número pandigital.

El producto de un número natural x por una lista de números naturales ys es el número obtenido concatenando los productos de x por cada uno de los elementos de ys. Por ejemplo, el producto de 2 por [3,2,5] es 6410.

Un número pandigital x es un múltiplo si existe un y y un n > 1 tales que x es el producto de y por [1,2,3,…,n]. Por ejemplo, 192384576 es un pandigital múltiplo ya que

por tanto, 192384576 es el producto de 192 por [1,2,3]. Otro pandgital múltiplo es el 918273645 ya que es el producto de 9 por [1,2,3,4,5].

Definir la sucesión

tal que sus elementos son los números pandigitales múltiplos. Por ejemplo,

Soluciones

Perímetro más frecuente de triángulos rectángulos

El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.

Definir la función

tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,

Soluciones

Números de suma prima hereditarios por la derecha

Decimos que un número es de suma prima si la suma de todos sus dígitos es un número primo. Por ejemplo el número 562 es de suma prima pues la suma de sus dígitos es el número primo 13; sin embargo, el número 514 no es de suma prima pues la suma de sus dígitos es 10, que no es primo.

Decimos que un número es de suma prima hereditario por la derecha si es de suma prima y los números que se obtienen eliminando sus últimas cifras también son de suma prima. Por ejemplo 7426 es de suma prima hereditario por la derecha pues 7426, 742, 74 y 7 son todos números de suma prima.

Definir la constante

cuyo valor es la lista infinita de los números de suma prima hereditarios por la derecha. Por ejemplo,

Soluciones

Pares como sumas de pares

Todo número par se puede escribir como suma de números pares de varias formas. Por ejemplo,

Definir la función

tal que (descomposicionesDecrecientes n) es la lista con las descomposiciones de n como suma de pares, en forma decreciente. Por ejemplo,

Soluciones

Mayor capicúa producto de dos números de n cifras

Un capicúa es un número que es igual leído de izquierda a derecha que de derecha a izquierda.

Definir la función

tal que (mayorCapicuaP n) es el mayor capicúa que es el producto de dos números de n cifras. Por ejemplo,

Soluciones

Mezcla de infinitas listas infinitas

Definir la función

tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,

Soluciones

Triángulos de Herón

Un triángulo de Herón es un triángulo tal que sus lados y su área son números enteros. Su nombre se debe al matemático griego Herón de Alejandría que descubrió la fórmula para calcular el área de un triángulo a partir de sus lados.

La fórmula de Herón dice que el área de un triángulo cuyos lados miden a, b y c es
     \sqrt{s(s-a)(s-b)(s-c)}
donde s es el semiperímetro del triángulo; es decir,
     s = \displaystyle \frac{a+b+c}{2}

Un ejemplo de triángulo de Herón es el triángulo de lados 3, 4 y 5 cuya área es 6. Se puede observar que cualquier triángulo cuyos lados sean múltiplos de 3, 4 y 5 también es de Herón; por ejemplo, el de lados 6, 8 y 10 también lo es.

Se dice que un triángulo de Herón es primitivo si el máximo común divisor de sus lados es 1. Por ejemplo, el de lados 3, 4 y 5 es primitivo; pero el de lados 6, 8 y 10 no lo es.

Definir la sucesión

tal que sus elementos son los triángulos de Herón primitivos ordenados por su perímetro. Por ejemplo,

Soluciones

Varios cuadrados encajados rotando

Enunciado

Definir la función

de forma que (cuadrados n) sea la animación obtenida rotando n cuadrados encajados como se muestra a continuación.

Nota: Escribir las soluciones usando la siguiente plantilla

Soluciones

Simplificación de expresiones booleanas

El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

Por ejemplo, la expresión (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

tales que (valor p i) es el valor de la expresión p cuando se le asigna a X el valor i. Por ejemplo,

y (simplifica p) es la expresión obtenida aplicándole a p las siguientes reglas de simplificación:

Por ejemplo,

Comprobar con QuickCheck que para cualquier expresión p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de expresiones booleanas

Soluciones

2015 como raíz cuadrada de la suma de tres cubos

Todos los años, en las proximidades del final de año suelen aparecer cuestiones con propiedades del número del nuevo año. Una sobre el 2015 es la publicada el martes en la entrada 2015 como raíz de la suma de tres cubos del blog Números y algo más en la que se pide calcular tres números tales que 2015 sea igual a la raíz cuadrada de la suma de dichos tres números.

A partir de dicha entrada, se propone el siguiente problema: Definir la sucesión

cuyos elementos son los números que se pueden escribir como raíces cuadradas de sumas de tres cubos. Por ejemplo,

El 6 está en la sucesión porque 1³+2³+3³ = 36 y la raíz cuadrada de36 es 6 y el 9 está porque 3³+3³+3³ = 81 y la raíz cuadrada de 81 es 9. Algunos números tienen varias descomposiones como raíz cuadrada de suma de tres cubos; por ejemplo, el 71 se puede escribir como la raíz cuadrada de la suma de los cubos de 6, 9 y 16 y también como la de 4, 4, y 17.

A partir de la sucesión se plantean las siguientes cuestiones:

  • ¿Qué lugar ocupa el 2015 en la sucesión?
  • ¿Cuál será el próximo año que se podrá escribir como la raíz cuadrada de suma de tres cubos?
  • ¿Cuáles son las descomposiciones de 2015 como raíz cuadrada de suma de tres cubos?
  • ¿Cuáles son los años hasta el 2015 que se pueden escribir como raíz cuadrada de suma de tres cubos de más formas distintas?

Soluciones

Fractal de la curva del dragón

La curva del dragón es un fractal que se construye siguiendo los siguientes pasos:

  • A partir de un segmento, se construye el triángulo rectángulo e isósceles, como lo muestra las dos primeras figuras. Luego se borra el segmento inicial.
  • Se repite varias veces el proceso de remplazar un segmento por otros dos para cada línea de la curva, alternando siempre la orientación de los triángulos.

La siguiente figura muestra los trece primeros pasos:
Formación_de_la_curva_del_dragón

El ejercicio consiste en definir (en CodeWorld) la función

tal que dragon(n) es el dibujo correspondiente al paso n de la construcción de la curva del dragón. Por ejemplo, el dibujo de dragon(20) es
Dragon

Comentarios

  1. La descripción de la curva dragón es la que se encuentra en el artículo de la Wikipedia.
  2. Una definición análoga es la del fractal de la curva de Koch.

Soluciones

Juego de bloques con letras

Introducción

Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.

Enunciado

Soluciones

Normalización de expresiones aritméticas

Enunciado

Soluciones

Particiones de longitud fija

Enunciado

Soluciones

Máximo de una función

Enunciado

Soluciones

Laberinto numérico

Enunciado

Soluciones

Producto de matrices como listas de listas

Soluciones

Código Morse

El código Morse es un sistema de representación de letras y números mediante señales emitidas de forma intermitente.

A los signos (letras mayúsculas o dígitos) se le asigna un código como se muestra a continuación

El código Morse de las palabras se obtiene a partir del de sus caracteres insertando un espacio entre cada uno. Por ejemplo, el código de "todo" es "- --- -.. ---"

El código Morse de las frases se obtiene a partir del de sus palabras insertando dos espacios entre cada uno. Por ejemplo, el código de "todo o nada" es "- --- -.. --- --- -. .- -.. .-"

Enunciado

Ayuda: Se puede usar la función splitOn de la librería Data.List.Split.

Soluciones

Renombramiento de un árbol

Soluciones

N gramas

Un n-grama de una sucesión es una subsucesión de n elementos.

Enunciado

Soluciones

Referencia

El ejercicio está basado en el problema del 3 de junio de 1HaskellADay.