Matrices dispersas

Una matriz es dispersa si la mayoriá de sus elementos son ceros. Por ejemplo, la primera de las siguientes matrices es dispersa y la segunda no lo es

Usando la librería Data.Matrix, las anteriores matrices se pueden definir por

La dispersión de una matriz es el cociente entre el número de ceros de la matriz y el producto de sus números de filas y de columnas.

Definir las siguientes funciones

tales que

  • (dispersion p) es la dispersión de la matriz p. Por ejemplo,

  • (esDispersa p) se verifica si la matriz p es dispersa. Por ejemplo,

Soluciones

Árboles binarios completos

Un árbol binario completo es un árbol en el que cada nodo tiene cero o dos hijos. Por ejemplo, el primero de los siguientes árboles es un árbol binario completo pero los otros no lo son

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

Por ejemplo, los árboles los árboles anteriores se puede representar por

Definir la función

tal que (esBinarioCompleto a) se verifica si a es un árbol binario completo. Por ejemplo,

Soluciones

Períodos de Fibonacci

Los primeros términos de la sucesión de Fibonacci son

Al calcular sus restos módulo 3 se obtiene

Se observa que es periódica y su período es

Definir las funciones

tales que

  • (fibsMod n) es la lista de los términos de la sucesión de Fibonacci módulo n. Por ejemplo,

  • (periodoFibMod n) es la parte perioica de la sucesión de Fibonacci módulo n. Por ejemplo,

  • longPeriodosFibMod es la sucesión de las longitudes de los períodos de las sucesiones de Fibonacci módulo n, para n > 0. Por ejemplo,

  • (graficaLongPeriodosFibMod n) dibuja la gráfica de los n primeros términos de la sucesión longPeriodosFibMod. Por ejemplo, (graficaLongPeriodosFibMod n) dibuja
    Periodos_de_Fibonacci 300

Soluciones

Huecos binarios

Los huecos binarios de un número natural n son las listas de cer0 entre dos unos en la representación binaria de n. Por ejemplo, puesto que la representación binaria de 20 es 10100 tiene dos huecos binarios de longitudes 1 y 2. La longitud del mayor hueco binario de 529 es 4 ya que la representación binaria de 529 es 1000010001.

Definir las funciones

tales que

  • (longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo,

  • (graficaLongMayorHuecoBinario n) dibuja la gráfica de las longitudes de los mayores huecos binarios de los n primeros números naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja
    Huecos_binarios_200

Soluciones

Celdas interiores de una retícula

Las celdas de una retícula cuadrada se numeran consecutivamente. Por ejemplo, la numeración de la retícula cuadrada de lado 4 es

Los números de sus celdas interiores son 6,7,10,11.

Definir la función

tal que (interiores n) es la lista de los números de las celdas interiores de la retícula cuadrada de lado n. Por ejemplo,

Comprobar con QuickCheck que el número de celdas interiores de la retícula cuadrada de lado n, con n > 1, es (n-2)^2.

Soluciones