Sucesión contadora

Definir las siguientes funciones

tales que

  • (numeroContado n) es el número obtenido al contar las repeticiones de cada una de las cifras de n. Por ejemplo,

  • (contadora n) es la sucesión cuyo primer elemento es n y los restantes se obtienen contando el número anterior de la sucesión. Por ejemplo,

  • (lugarPuntoFijoContadora n k) es el menor i <= k tal que son iguales los elementos en las posiciones i e i+1 de la sucesión contadora que cominza con n. Por ejemplo,

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz.

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

[schedule expon=’2017-05-26′ expat=»06:00″]

  • Las soluciones se pueden escribir en los comentarios hasta el 26 de mayo.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-26′ at=»06:00″]

[/schedule]

Problema de las 3 jarras

En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).

Definir las funciones

tales que

  • (solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,

  • (tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,

Soluciones

Normalización de expresiones aritméticas

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z) y x+(y*z) están en forma normal; pero x*(y+z) y (x+y)*(x+z) no lo están.

Definir la función

tales que

  • (esTermino a) se verifica si a es un término. Por ejemplo,

  • (esNormal a) se verifica si a está en forma normal. Por ejemplo,

  • (normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:

Por ejemplo,

Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).

Nota. Para la comprobación se usará el siguiente generador de expresiones aritméticas

Soluciones

Sucesión de Recamán

La sucesión de Recamán está definida como sigue:

Definir las funciones

tales que

  • sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,

  • (invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,

  • (graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja
    Sucesion_de_Recaman_1
  • (graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja
    Sucesion_de_Recaman_2
    y (graficaInvRecaman 100) dibuja
    Sucesion_de_Recaman_3

Soluciones

Operaciones con series de potencias

Una serie de potencias es una serie de la forma

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

Definir las siguientes funciones

tales que

  • (opuesta xs) es la opuesta de la serie xs. Por ejemplo,

  • (suma xs ys) es la suma de las series xs e ys. Por ejemplo,

  • (resta xs ys) es la resta de las series xs es ys. Por ejemplo,

  • (producto xs ys) es el producto de las series xs e ys. Por ejemplo,

  • (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

  • (derivada xs) es la derivada de la serie xs. Por ejemplo,

  • (integral xs) es la integral de la serie xs. Por ejemplo,

  • expx es la serie de la función exponencial. Por ejemplo,

Soluciones

Operaciones con polinomios como diccionarios

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

se definen por

Definir las funciones

tales que

  • (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

  • (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,

  • (multPol p q) es el producto de los polinomios p y q. Por ejemplo,

Soluciones

Números como sumas de primos consecutivos

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

el número 41 se puede escribir de 4 formas

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,

Soluciones

Clases de equivalencia

Definir la función

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

Soluciones

Problema de las jarras

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

La interpretación de la solución anterior es

Otros ejemplos:

Soluciones

El problema de las N torres

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

representa una solución del problema de las 3 torres.

Definir las funciones

tales que
+ (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

  • (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,

Soluciones

Sumas con sumandos distintos o con sumandos impares

El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:

y también se puede descomponer de 4 formas distintas como suma con sumandos impares:

Definir las siguientes funciones

tales que

  • (sumasSumandosDistintos n) es la lista de las descomposiciones de n como sumas con sumandos distintos. Por ejemplo,

  • (nSumasSumandosDistintos n) es el número de descomposiciones de n como sumas con sumandos distintos. Por ejemplo,

  • (sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,

  • (nSumasSumandosImpares n) es el número de descomposiciones de n como sumas con sumandos impares. Por ejemplo,

  • (igualdadDeSumas n) se verifica si, para todo k entre 1 y n, las funciones nSumasSumandosDistintos y nSumasSumandosImpares son iguales. Por ejemplo,

Soluciones

Puntos alcanzables en un mapa

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

Definir las funciones

tales que

  • (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,

  • (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Soluciones

Distribución de diferencias de dígitos consecutivos de pi

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

Las diferencias de sus elementos consecutivos es

y la distribución de sus frecuencias en el intervalo [-9,9] es

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

tales que

  • (distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

  • (graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] «distribucionDDCpi.png» se escribe en el fichero «distribucionDDCpi.png» la siguiente gráfica
    Distribucion_de_diferencias_de_digitos_consecutivos_de_pi

Nota: Se puede usar la librería Data.Number.CReal.

Soluciones

Caminos minimales en un arbol numérico

En la librería Data.Tree se definen los árboles y los bosques como sigue

Se pueden definir árboles. Por ejemplo,

Y se pueden dibujar con la función drawTree. Por ejemplo,

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

Definir las siguientes funciones

tales que

  • (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

Soluciones

Generadores de números de Gabonacci

Los números de Gabonacci generados por (a,b) son los elementos de la sucesión de Gabonacci definida por

Por ejemplo, la sucesión de Gabonacci generada por (2,5) es 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, …

Un número pertenece a distintas sucesiones de Gabonacci. Por ejemplo, el 9 pertenece a las sucesiones de Gabonacci generados por (3,3), (1,4) y (4,5).

El menor generador de Gabonacci de un número x es el par (a,b), con 1 ≤ a ≤ b, tal que (a,b) es un generador de Gabonacci de x y no existe ningún generador de Gabonacci de x (a’,b’) tal que b’ < b ó b’ = b y a’ < a. Por ejemplo, el menor generador de Gabonacci de 9 es (3,3).

Definir la función

tal que (menorGenerador x) es el menor generador de Gabonacci de x. Por ejemplo,

Soluciones

Números construibles como sumas de dos dados

Un número x es construible a partir de de los números enteros positivos a y b si se puede escribir como una suma cuyos sumandos son a o b. Por ejemplo, 7 y 9 son construibles a partir de 2 y 3 ya que 7 = 2+2+3 y 9 = 3+3+3.

Definir las funciones

tales que

  • (construibles a b) es la lista de los números construibles a partir de a y b. Por ejemplo,

  • (esConstruible a b x) se verifica si x es construible a partir de a y b. Por ejemplo,

Soluciones

Cálculo de pi mediante la serie de Nilakantha

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es
Calculo_de_pi_mediante_la_serie_de_Nilakantha

Definir las funciones

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

  • (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

hace que el contenido del fichero «AproximacionesPi.txt» sea

y al evaluar la expresión

hace que el contenido del fichero «AproximacionesPi.txt» sea

Nota: Este ejercicio ha sido propuesto por Manuel Herrera.

Referencias

Soluciones

Cálculo de pi mediante la fracción continua de Lange

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua
Calculo_de_pi_mediante_la_fraccion_continua_de_Lange

La primeras aproximaciones son

Definir las funciones

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja
    Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_2
    (grafica [10..100]) dibuja
    Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_3
    y (grafica [100..200]) dibuja
    Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_4

Nota: Este ejercicio ha sido propuesto por Antonio Morales.

Soluciones

Máxima potencia que divide al factorial

La máxima potencia de 2 que divide al factorial de 5 es 3, ya que 5! = 120, 120 es divisible por 2^3 y no lo es por 2^4.

Definir la función

tal que (maxPotDivFact p n), para cada primo p, es el mayor k tal que p^k divide al factorial de n. Por ejemplo,

Soluciones

Números dorados

Los dígitos del número 2375 se pueden separar en dos grupos de igual tamaño ([7,2] y [5,3]) tales que para los correspondientes números (72 y 53) se verifique que la diferencia de sus cuadrados sea el número original (es decir, 72^2 – 53^2 = 2375).

Un número x es dorado si sus dígitos se pueden separar en dos grupos de igual tamaño tales que para los correspondientes números (a y b) se verifique que la diferencia de sus cuadrados sea el número original (es decir, b^2 – a^2 = x).

Definir la función

tales que (esDorado x) se verifica si x es un número dorado. Por
ejemplo,

Soluciones

Día de la semana

Definir la función

tal que (dia d m a) es el día de la semana correspondiente al día d del mes m del año a. Por ejemplo,

Nota: Este ejercicio ha sido propuesto por Miguel Ibáñez.

Soluciones

Números de la suerte

Un número de la suerte es un número natural que se genera por una criba, similar a la criba de Eratóstenes, como se indica a continuación:

Se comienza con la lista de los números enteros a partir de 1:

Se eliminan los números de dos en dos

Como el segundo número que ha quedado es 3, se eliminan los números
restantes de tres en tres:

Como el tercer número que ha quedado es 7, se eliminan los números restantes de
siete en siete:

Este procedimiento se repite indefinidamente y los supervivientes son
los números de la suerte:

Definir la sucesión

cuyos elementos son los números de la suerte. Por ejemplo,

Soluciones

Posiciones de equilibrio

Se dice que k es una posición de equilibrio de una lista xs si la suma de los elementos de xs en las posiciones menores que k es igual a la suma de los elementos de xs en las posiciones mayores que k. Por ejemplo, en la lista [-7,1,5,2,-4,3,0] el 3 es una posición de equilibrio ya que -7+1+5 = -4+3+0; también lo es el 6 ya que -7+1+5+2+(-4)+3 = 0.

Definir la función,

tal que (equilibrios xs) es la lista de las posiciones de equilibrio de xs. Por ejemplo,

Soluciones

Distancia a Erdős

Una de las razones por la que el matemático húngaro Paul Erdős es conocido es por la multitud de colaboraciones que realizó durante toda su carrera, un total de 511. Tal es así que se establece la distancia a Erdős como la distancia que has estado de coautoría con Erdős. Por ejemplo, si eres Paul Erdős tu distancia a Erdős es 0, si has escrito un artículo con Erdős tu distancia es 1, si has escrito un artículo con alguien que ha escrito un artículo con Erdős tu distancia es 2, etc. El objetivo de este problema es definir una función que a partir de una lista de pares de coautores y un número natural n calcular la lista de los matemáticos a una distancia n de Erdős.

Para el problema se considerará la siguiente lista de coautores

La lista anterior es real y se ha obtenido del artículo Famous trails to Paul Erdős.

Definir la función

tal que (numeroDeErdos xs n) es la lista de lista de los matemáticos de la
lista de coautores xs que se encuentran a una distancia n de Erdős. Por ejemplo,

Nota: Este ejercicio ha sido propuesto por Enrique Naranjo.

Soluciones

Problema de las particiones óptimas

El problema de la particiones óptimas consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una partición óptima de xs. Por ejemplo, la partición óptima de [2,3,5] es ([2,3],[5]) ya que |(2+3) – 5| = 0. Una lista puede tener distintas particiones óptimas. Por ejemplo, [1,1,2,3] tiene dos particiones óptimas ([1,2],[1,3]) y ([1,1,2],[3]) ambas con diferencia 1 (es decir, 1 = |(1+2)-(1+3)| = |(1+1+2)-3|).

Definir la función

tal que (particionesOptimas xs) es la lista de las particiones óptimas de xs. Por ejemplo,

Soluciones

Mínimo número de operaciones para transformar un número en otro

Se considera el siguiente par de operaciones sobre los números:

  • multiplicar por dos
  • restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

y el menor número de operaciones para transformar 2 en 5 es 4

Definir las siguientes funciones

tales que

  • (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

  • (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

Soluciones

Referencias

Basado en el artículo Minimum number of operation required to
convert number x into y
de Vipin Khushu en
GeeksforGeeks.

Menor potencia de 2 comenzando un número dado

Definir las siguientes funciones

tales que

  • (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,

  • (menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,

Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.

Soluciones

Referencias

Máxima ramificación

Los árboles se pueden representar mediante el siguiente tipo de datos

Por ejemplo, los árboles

se representan por

En el primer ejemplo la máxima ramificación es 2 (en el nodo 1 que tiene 2 hijos), la del segundo es 3 (en el nodo 3 que tiene 3 hijos) y la del tercero es 3 (en el nodo 3 que tiene 3 hijos).

Definir la función

tal que (maximaRamificacion a) es la máxima ramificación del árbol a. Por ejemplo,

Soluciones

Números consecutivos compuestos

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función

tal que (menorSerieCompuesta n) es la menor serie compuesta (es decir, la que tiene menores elementos) de longitud 3. Por ejemplo,

Comprobar con QuickCheck que para n > 1, el primer elemento de (menorSerieCompuesta n) es igual al primero de (menorSerieCompuesta (n-1)) o al primero de (menorSerieCompuesta (n+1)).

Soluciones

Referencias