Reconocimiento de particiones

Una partición de un conjunto es una división del mismo en subconjuntos disjuntos no vacíos.

Definir la función

tal que (esParticion xss) se verifica si xss es una partición; es decir sus elementos son listas no vacías disjuntas. Por ejemplo.

Soluciones

Pensamiento

Sentía los cuatro vientos,
en la encrucijada
de su pensamiento.

Antonio Machado

Número de parejas

Definir la función

tal que (nParejas xs) es el número de parejas de elementos iguales en xs. Por ejemplo,

En el primer ejemplos las parejas son (1,1), (1,1) y (2,2). En el segundo ejemplo, las parejas son (1,1) y (2,2).

Comprobar con QuickCheck que para toda lista de enteros xs, el número de parejas de xs es igual que el número de parejas de la inversa de xs.

Soluciones

Pensamiento

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

Antonio Machado

Distancia de Hamming

La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre «roma» y «loba» es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).

Definir la función

tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,

Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad

y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.

Soluciones

Pensamiento

En mi soledad/
he visto cosas muy claras,
que no son verdad.

Antonio Machado

Listas equidigitales

Una lista de números naturales es equidigital si todos sus elementos tienen el mismo número de dígitos.

Definir la función

tal que (equidigital xs) se verifica si xs es una lista equidigital. Por ejemplo,

Soluciones

Pensamiento

Se miente más de la cuenta
por falta de fantasía:
también la verdad se inventa.

Antonio Machado

Sin ceros consecutivos

Definir la función

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

Soluciones

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

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

[/schedule]

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

[/schedule]

Subexpresiones aritméticas

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

Por ejemplo, la expresión 2*(3+7) se representa por

Definir la función

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

Soluciones

La regla de los signos de Descartes

Los polinomios pueden representarse mediante listas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -7. Llamando C(p) al número de cambios de signo en la lista de coeficientes del polinomio p(x), tendríamos entonces que en este caso C(p)=3.

La regla de los signos de Descartes dice que el número de raíces reales positivas de una ecuación polinómica con coeficientes reales igualada a cero es, como mucho, igual al número de cambios de signo que se produzcan entre sus coeficientes (obviando los ceros). Por ejemplo, en el caso anterior la ecuación tendría como mucho tres soluciones reales positivas, ya que C(p)=3.

Además, si la cota C(p) no se alcanza, entonces el número de raíces positivas de la ecuación difiere de ella un múltiplo de dos. En el ejemplo anterior esto significa que la ecuación puede tener tres raíces positivas o tener solamente una, pero no podría ocurrir que tuviera dos o que no tuviera ninguna.

Definir las funciones

tales que

  • (cambios xs) es la lista de los pares de elementos de xs con signos distintos, obviando los ceros. Por ejemplo,

  • (nRaicesPositivas p) es la lista de los posibles números de raíces positivas del polinomio p (representado mediante una lista) según la regla de los signos de Descartes. Por ejemplo,

que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 raíz positiva.

Soluciones

Representaciones de grafos

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

se puede representar por la matriz de adyacencia

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

tales que

  • (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por

se tiene que

  • (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,

Soluciones

Polinomios de Fibonacci

La sucesión de polinomios de Fibonacci se define por

Los primeros términos de la sucesión son

Definir la lista

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, …

Nota. Limitar la búsqueda a ejemplos pequeños usando

Soluciones

Sustitución de pares de elementos consecutivos iguales

Dada una lista xs se reemplaza el primer par de elementos consecutivos iguales x por x+1 y se repite el proceso con las listas obtenidas hasta que no haya ningún par de elementos consecutivos iguales. Por ejemplo, para [5,2,1,1,2,2] se tiene el siguiente proceso

Definir la función

tal que (sustitucion xs) es la lista obtenida aplicándole a xs el proceso anterior. Por ejemplo,

Soluciones

Números construidos con los dígitos de un conjunto dado

Definir las siguientes funciones

tales que

  • (numerosCon ds) es la lista de los números que se pueden construir con los dígitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,

  • (numeroDeDigitos ds k) es el número de dígitos que tiene el k-ésimo elemento (empezando a contar en 0) de la sucesión (numerosCon ds). Por ejemplo,

Soluciones

Máximos de expresiones aritméticas

Las expresiones aritméticas se pueden definir usando el siguiente tipo de datos

Por ejemplo, la expresión

se puede definir por

Definir la función

tal que (maximo e xs) es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,

Soluciones

Polinomio digital

Definir la función

tal que (polinomioDigital n) es el polinomio cuyos coeficientes son los dígitos de n. Por ejemplo,

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

Soluciones

Diccionario inverso

El inverso de un diccionario d es el diccionario que a cada valor x le asigna la lista de claves cuyo valor en d es x. Por ejemplo, el inverso de

es

Definir la función

tal que (inverso d) es el inverso del diccionario d. Por ejemplo,

Soluciones

Sumas de subconjuntos

Definir la función

tal que (sumasSubconjuntos xs) es el conjunto de las sumas de cada uno de los subconjuntos de xs. Por ejemplo,

Soluciones

Reducción de opuestos

Se considera el siguiente procedimiento de reducción de listas: busca un par de elementos consecutivos iguales pero con signos opuestos, se eliminan dichos elementos y se continúa el proceso hasta que no se encuentren pares de elementos consecutivos iguales pero con signos opuestos. Por ejemplo, la reducción de [-2,1,-1,2,3,4,-3] es

Definir la función

tal que (reducida xs) es la lista obtenida aplicando a xs el de eliminación de pares de elementos consecutivos opuestos. Por ejemplo,

Soluciones

Números superpares

Definir la función

tal que (superpar n) se verifica si n es un número par tal que todos sus dígitos son pares. 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

Ampliación de árboles binarios

Representamos los árboles binarios mediante el tipo de dato

Una forma de ampliar un árbol binario es añadiendo un nuevo nivel donde
las nuevas hojas sean iguales a la suma de los valores de los nodos
desde el padre hasta llegar a la raíz (inclusives). Por ejemplo:

Definir la función

tal que (ampliaArbol a) es el árbol a ampliado en un nivel. Por
ejemplo,

Soluciones

Operaciones binarias con matrices

Entre dos matrices de la misma dimensión se pueden aplicar distintas operaciones binarias entre los elementos en la misma posición. Por ejemplo, si a y b son las matrices

entonces a+b y a-b son, respectivamente

Definir la función

tal que (opMatriz f p q) es la matriz obtenida aplicando la operación f entre los elementos de p y q de la misma posición. Por ejemplo,

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

Suma de las alturas de los nodos de un árbol

Las árboles binarios se pueden representar con el siguiente tipo

Por ejemplo, el árbol

se representa por

La altura de cada elemento del árbol es la máxima distancia a las hojas en su rama. Por ejemplo, en el árbol anterior, la altura de 1 es 3, la de 2 es 2, la de 3 es 1, la de 4 es 1 y la de 5 es 1.

Definir la función

tal que (sumaAlturas a) es la suma de las alturas de los elementos de a. Por ejemplo,

Soluciones

La conjetura de Levy

Hyman Levy observó que

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

tales que

  • (descomposicionesLevy x) es la lista de pares de primos (p,q) tales que x = p + 2q. Por ejemplo,

  • (graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja
    La_conjetura_de_Levy-200

Comprobar con QuickCheck la conjetura de Levy.

Soluciones

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

Matrices de Pascal

El triángulo de Pascal es un triángulo de números

construido de la siguiente forma

  • la primera fila está formada por el número 1;
  • las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La matriz de Pascal es la matriz cuyas filas son los elementos de la
correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es

Definir la función

tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,

Soluciones

Cruce de listas

Definir la función

tal que (cruce xs ys) es la lista de las listas obtenidas uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

Comprobar con QuickCheck que el número de elementos de (cruce xs ys) es el producto de los números de elementos de xs y de ys.

Soluciones

Matrices centro simétricas

Una matriz centro simétrica es una matriz cuadrada que es simétrica respecto de su centro. Por ejemplo, de las siguientes matrices, las dos primeras son simétricas y las otras no lo son

Definir la función

tal que (esCentroSimetrica a) se verifica si la matriz a es centro simétrica. Por ejemplo,

Soluciones

La función de Smarandache

La función de Smarandache, también conocida como la función de Kempner, es la función que asigna a cada número entero positivo n el menor número cuyo factorial es divisible por n y se representa por S(n). Por ejemplo, el número 8 no divide a 1!, 2!, 3!, pero sí divide 4!; por tanto, S(8) = 4.

Definir las funciones

tales que

  • (smarandache n) es el menor número cuyo factorial es divisible por n. Por ejemplo,

  • (graficaSmarandache n) dibuja la gráfica de los n primeros términos de la sucesión de Smarandache. Por ejemplo, (graficaSmarandache 100) dibuja
    La_funcion_de_Smarandache_100
    (graficaSmarandache 500) dibuja
    La_funcion_de_Smarandache_500

Soluciones

Generación de progresiones geométricas

Definir la función

tal que (geometrica a b c) es la lista de los términos de la progresión geométrica cuyo primer término es a, su segundo término es b (que se supone que es múltiplo de a) y los términos son menores o iguales que c. Por ejemplo,

Soluciones

Menor potencia de 2 que comienza por n

Definir las funciones

tales que

  • (menorPotencia n) es el par (k,m) donde m es la menor potencia de 2 que empieza por n y k es su exponentes (es decir, 2^k = m). Por ejemplo,

  • (graficaMenoresExponentes n) dibuja la gráfica de los exponentes de 2 en las menores potencias de los n primeros números enteros positivos. Por ejemplo, (graficaMenoresExponentes 200) dibuja
    Menor_potencia_de_2_que_comienza_por_n

Soluciones

Representación ampliada de matrices dispersas

En el ejercicio anterior se explicó una representación reducida de las matrices dispersas. A partir del número de columnas y la representación reducida se puede construir la matriz.

Definir la función

tal que (ampliada n xss) es la matriz con n columnas cuya representación reducida es xss. Por ejemplo,

Soluciones