Cambio con el menor número de monedas

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

Soluciones

Números de Perrin

Los números de Perrin se definen por la elación de recurrencia

con los valores iniciales

Definir la sucesión

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

Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.

Soluciones

Sucesión fractal

La sucesión fractal

está construida de la siguiente forma:

  • los términos pares forman la sucesión de los números naturales

  • los términos impares forman la misma sucesión original

Definir las funciones

tales que

  • sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

  • (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

Soluciones

Camino de máxima suma en una matriz

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

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

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

Definir la función

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,

Nota: Se recomienda usar programación dinámica.

Soluciones

Máximo de las sumas de los caminos en una matriz

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

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

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El máximo de las suma de los caminos es 41.

Definir la función

tal que (maximaSuma m) es el máximo de las sumas de los caminos 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,

Nota: Se recomienda usar programación dinámica.

Soluciones

Caminos en una matriz

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

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

Definir la función

tal que (caminos m) es la lista de los caminos 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,

Nota: Se recomienda usar programación dinámica.

Soluciones

Máxima longitud de sublistas crecientes

Definir la función

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Soluciones

La sucesión de Sylvester

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

tales que

  • (sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

  • (graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
    • (graficaSylvester 3 30) dibuja
      La_sucesion_de_Sylvester_(3,30)
    • (graficaSylvester 4 30) dibuja
      La_sucesion_de_Sylvester_(4,30)
    • (graficaSylvester 5 30) dibuja
      La_sucesion_de_Sylvester_(5,30)

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Soluciones

Matriz de mínimas distancias

Definir las funciones

tales que

  • (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

  • (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Conjetura de Goldbach

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

tales que

  • (indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

  • (graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja
    Conjetura_de_Goldbach_150

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Soluciones

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

«La diferencia entre los matemáticos y los físicos es que después de que los físicos prueban un gran resultado piensan que es fantástico, pero después de que los matemáticos prueban un gran resultado piensan que es trivial.»

Lucien Szpiro.

Número de emparejamientos de amigos

El problema del número de emparejamiento de amigos consiste en calcular el número de formas de emparejar n amigos teniendo en cuenta que cada uno puede permanecer soltero o puede ser emparejado con algún otro amigo y que cada amigo puede ser emparejado sólo una vez. Por ejemplo, los 4 posibles emparejamientos de 3 amigos son

Definir la función

tal que (nEmparejamientos n) es el número de formas de emparejar a los n amigos. Por ejemplo,

Soluciones

Pensamiento

Toda la imaginería
que no ha brotado del río,
barata bisutería.

Antonio Machado

Triángulo de Euler

El triángulo de Euler se construye a partir de las siguientes relaciones

Sus primeros términos son

Definir las siguientes funciones:

tales que

  • (numeroEuler n k) es el número de Euler A(n,k). Por ejemplo,

  • (filaTrianguloEuler n) es la n-ésima fila del triángulo de Euler. Por ejemplo,

  • trianguloEuler es la lista con las filas del triángulo de Euler

Soluciones

Pensamiento

Señor San Jerónimo,
suelte usted la piedra
con que se machaca.
Me pegó con ella.

Antonio Machado

Matriz de mínimas distancias

Definir las funciones

tales que

  • (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

  • (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

Soluciones

Pensamiento

La primavera ha venido.
Nadie sabe como ha sido.

Antonio Machado

Cambio con el menor número de monedas

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

Soluciones

Pensamiento

Demos tiempo al tiempo:
para que el vaso rebose
hay que llenarlo primero.

Antonio Machado

Máxima longitud de sublistas crecientes

Definir la función

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

Soluciones

Pensamiento

No es el yo fundamental
eso que busca el poeta,
sino el tú esencial.

Antonio Machado

Camino de máxima suma en una matriz

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

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

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

Definir la función

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,

Soluciones

Pensamiento

Caminante, no hay camino,
sino estelas en la mar.

Antonio Machado

Número de descomposiciones en sumas de cuatro cuadrados

Definir la función

tales que

  • (nDescomposiciones x) es el número de listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.

  • (graficaDescomposiciones n) dibuja la gráfica del número de descomposiciones de los n primeros números naturales. Por ejemplo, (graficaDescomposiciones 500) dibuja

Soluciones

Pensamiento

Ya habrá cigüeñas al sol,
mirando la tarde roja,
entre Moncayo y Urbión.

Antonio Machado

Descomposiciones en sumas de cuatro cuadrados

Definir la función

tal que (descomposiciones x) es la lista de las listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.

Soluciones

Pensamiento

No extrañéis, dulces amigos,
que esté mi frente arrugada;
yo vivo en paz con los hombres
y en guerra con mis entrañas.

Antonio Machado

Número de particiones de un conjunto

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

Definir la función

tal que (nParticiones xs) es el número de particiones de xs. Por ejemplo,

Soluciones

Pensamiento

Yo he visto garras fieras en las pulidas manos;
conozco grajos mélicos y líricos marranos …
El más truhán se lleva la mano al corazón,
y el bruto más espeso se carga de razón.

Antonio Machado

Divisiones del círculo

Dado 4 puntos de un círculo se pueden dibujar 2 cuerdas entre ellos de forma que no se corten. En efecto, si se enumeran los puntos del 1 al 4 en sentido de las agujas del reloj una forma tiene las cuerdas {1-2, 3-4} y la otra {1-4, 2-3}.

Definir la función

tal que (numeroFormas n) es el número de formas que se pueden dibujar n cuerdas entre 2xn puntos de un círculo sin que se corten. Por ejemplo,

Soluciones

Pensamiento

… Y si la vida es corta
y no llega la mar a tu galera,
aguarda sin partir y siempre espera,
que el arte es largo y, además no importa.

Antonio Machado

Número de sumandos en suma de cuadrados

El teorema de Lagrange de los cuatro cuadrados asegura que cualquier número entero positivo es la suma de, como máximo,cuatro cuadrados de números enteros. Por ejemplo,

Definir las funciones

tales que

  • (ordenLagrange n) es el menor número de cuadrados necesarios para escribir n como suma de cuadrados. Por ejemplo.

  • (graficaOrdenLagrange n) dibuja la gráfica de los órdenes de Lagrange de los n primeros números naturales. Por ejemplo, (graficaOrdenLagrange 100) dibuja

Comprobar con QuickCheck que. para todo entero positivo k, el orden de Lagrange de k es menos o igual que 4, el de 4k+3 es distinto de 2 y el de 8k+7 es distinto de 3.

Soluciones

Pensamiento

— Nuestro español bosteza.
¿Es hambre? ¿Sueño? ¿Hastío?
Doctor, ¿tendrá el estómago vacío?
— El vacío es más bien en la cabeza.

Antonio Machado

Sucesión fractal

La sucesión fractal

está construida de la siguiente forma:

  • los términos pares forman la sucesión de los números naturales

  • los términos impares forman la misma sucesión original

Definir las funciones

tales que

  • sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

  • (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

Soluciones

[schedule expon=’2018-06-19′ expat=»06:00″]

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

[/schedule]

[schedule on=’2018-06-19′ at=»06:00″]

Referencia

+ [Fractal sequences and restricted Nim](http://bit.ly/1WX1IjB) por Lionel Levine.
[/schedule]

Descomposiciones de N como sumas de 1, 3 ó 4.

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

Definir las funciones

tales que

  • (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

  • (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

Nota: Se puede usar programación dinámica.

Soluciones

Mayor número de atracciones visitables

En el siguiente gráfico se representa en una cuadrícula el plano de Manhattan. Cada línea es una opción a seguir; el número representa las atracciones que se pueden visitar si se elige esa opción.

El turista entra por el extremo superior izquierda y sale por el extremo inferior derecha. Sólo puede moverse en las direcciones Sur y Este (es decir, hacia abajo o hacia la derecha).

Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde a = nº de atracciones si se va hacia el sur y b = nº de atracciones si se va al este. Además, ponemos un 0 en el valor del número de atracciones por un camino que no se puede elegir. De esta forma, el mapa anterior se representa por la matriz siguiente:

En este caso, si se hace el recorrido

el número de atracciones es

cuya suma es 34.

Definir la función

tal que (mayorNumeroV p) es el máximo número de atracciones que se pueden visitar en el plano representado por la matriz p. Por ejemplo, si se define la matriz anterior por

entonces

Para los siguientes ejemplos se define un generador de mapas

Entonces,

Soluciones

Número de triangulaciones de un polígono

Una triangulación de un polígono es una división del área en un conjunto de triángulos, de forma que la unión de todos ellos es igual al polígono original, y cualquier par de triángulos es disjunto o comparte únicamente un vértice o un lado. En el caso de polígonos convexos, la cantidad de triangulaciones posibles depende únicamente del número de vértices del polígono.

Si llamamos T(n) al número de triangulaciones de un polígono de n vértices, se verifica la siguiente relación de recurrencia:

Definir la función

tal que (numeroTriangulaciones n) es el número de triangulaciones de un polígono convexo de n vértices. Por ejemplo,

Soluciones

Subconjuntos con suma dada

Sea S un conjunto finito de números enteros positivos y n un número natural. El problema consiste en calcular los subconjuntos de S cuya suma es n.

Definir la función

tal que (subconjuntosSuma xs n) es la lista de los subconjuntos de xs cuya suma es n. Por ejemplo,

Soluciones

Decidir si existe un subconjunto con suma dada

Sea S un conjunto finito de números naturales y m un número natural. El problema consiste en determinar si existe un subconjunto de S cuya suma es m. Por ejemplo, si S = [3,34,4,12,5,2] y m = 9, existe un subconjunto de S, [4,5], cuya suma es 9. En cambio, no hay ningún subconjunto de S que sume 13.

Definir la función

tal que (existeSubSuma xs m) se verifica si existe algún subconjunto de xs que sume m. Por ejemplo,

Soluciones

Alturas primas

Se considera una enumeración de los números primos:

Dado un entero x > 1, su altura prima es el mayor i tal que el primo p(i) aparece en la factorización de x en números primos. Por ejemplo, la altura prima de 3500 tiene longitud 4, pues 3500=2^2×5^3×7^1 y la de 34 tiene es 7, pues 34 = 2×17. Además, se define la altura prima de 1 como 0.

Definir las funciones

tales que

  • (alturaPrima x) es la altura prima de x. Por ejemplo,

  • (alturasPrimas n) es la lista de las altura prima de los primeros n números enteros positivos. Por ejemplo,

  • (graficaAlturaPrima n) dibuja las alturas primas de los números entre 2 y n. Por ejemplo, (graficaAlturaPrima 500) dibuja
    Alturas_primas

Soluciones

Números tetranacci

Los números tetranacci son una generalización de los números de Fibonacci definidos por

Los primeros números tetranacci son

Definir las funciones

tales que

  • (tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,

  • (graficaTetranacci n) dibuja la gráfica de los cocientes de n primeros pares de número tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja
    Numeros_tetranacci_200

Soluciones

Máxima longitud de sublistas crecientes

Definir la función

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

Soluciones