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,

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,

Soluciones

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

Suma de las sumas de los cuadrados de los divisores

La suma de las sumas de los cuadrados de los divisores de los 6 primeros números enteros positivos es

Definir la función

tal que (sumaSumasCuadradosDivisores n) es la suma de las sumas de los cuadrados de los divisores de los n primeros números enteros positivos. Por ejemplo,

Soluciones

Nodos con máxima suma de hijos

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

Por ejemplo, los árboles

se representan por

Definir la función

tal que (nodosSumaMaxima a) es la lista de los nodos del árbol a cuyos hijos tienen máxima suma. 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

Ceros con los n primeros números

Los números del 1 al 3 se pueden escribir de dos formas, con el signo más o menos entre ellos, tales que su suma sea 0:

Definir la función

tal que (ceros n) son las posibles formas de obtener cero sumando los números del 1 al n, con el signo más o menos entre ellos. 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

Vértices de un cuadrado

Definir la función

tal que (esCuadrado p q r s) se verifica si los puntos p, q, r y s son los vértices de un cuadrado. 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

Dígitos iniciales

Definir las funciones

tales que

  • digitosIniciales es la lista de los dígitos iniciales de los números naturales. Por ejemplo,

  • (graficaDigitosIniciales n) dibuja la gráfica de los primeros n términos de la sucesión digitosIniciales. Por ejemplo, (graficaDigitosIniciales 100) dibuja
    Digitos_iniciales_100
    y (graficaDigitosIniciales 1000) dibuja
    Digitos_iniciales_1000

Soluciones

Exponentes de Hamming

Los números de Hamming forman una sucesión estrictamente creciente de números que cumplen las siguientes condiciones:

  • El número 1 está en la sucesión.
  • Si x está en la sucesión, entonces 2x, 3x y 5x también están.
  • Ningún otro número está en la sucesión.

Los primeros números de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, …

Los exponentes de un número de Hamming n es una terna (x,y,z) tal que n = 2^x*3^y*5^z. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z.

Definir la sucesión

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

Soluciones

Recorrido del robot

Los puntos de una retícula se representan mediante pares de enteros

y los movimientos de un robot mediante el tipo

donde (N x) significa que se mueve x unidades en la dirección norte y análogamente para las restantes direcciones (S es sur, E es este y O es oeste).

Definir la función

tal que (posicion ms) es la posición final de un robot que inicialmente está en el el punto (0,0) y realiza los movimientos ms. Por ejemplo,

Soluciones

Sucesión de Lichtenberg

La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados Los primeros términos de ambas sucesiones son

Definir las funciones

tales que

  • lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo,

  • (graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja
    Sucesion_de_Lichtenberg

Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.

Soluciones

Sumas parciales de Juzuk

En 1939 Dov Juzuk extendió el método de Nicómaco del cálculo de los cubos. La extensión se basaba en los siguientes pasos:

  • se comienza con la lista de todos los enteros positivos

  • se agrupan tomando el primer elemento, los dos siguientes, los tres
    siguientes, etc.

  • se seleccionan los elementos en posiciones pares

  • se suman los elementos de cada grupo

  • se calculan las sumas acumuladas

Las sumas obtenidas son las cuantas potencias de los números enteros positivos.

Definir las funciones

tal que

  • (listasParcialesJuzuk xs) es lalista de ls listas parciales de Juzuk; es decir, la selección de los elementos en posiciones pares de la agrupación de los elementos de xs tomando el primer elemento, los dos siguientes, los tres siguientes, etc. Por ejemplo,

  • (sumasParcialesJuzuk xs) es la lista de las sumas acumuladas de los elementos de las listas de Juzuk generadas por xs. Por ejemplo,

Comprobar con QuickChek que, para todo entero positivo n,

  • el elemento de (sumasParcialesJuzuk [1..]) en la posición (n-1) es n^4.
  • el elemento de (sumasParcialesJuzuk [1,3..]) en la posición (n-1) es n^2*(2*n^2 - 1).
  • el elemento de (sumasParcialesJuzuk [1,5..]) en la posición (n-1) es 4*n^4-3*n^2.
  • el elemento de (sumasParcialesJuzuk [2,3..]) en la posición (n-1) es n^2*(n^2+1).

Soluciones

Complemento potencial

Complemento potencial

El complemento potencial de un número entero positivo x es el menor número y tal que el producto de x por y es un una potencia perfecta. Por ejemplo,

  • el complemento potencial de 12 es 3 ya que 12 y 24 no son potencias perfectas pero 36 sí lo es;
  • el complemento potencial de 54 es 4 ya que 54, 108 y 162 no son potencias perfectas pero 216 = 6^3 sí lo es.

Definir las funciones

tales que

  • (complemento x) es el complemento potencial de x; por ejemplo,

  • (graficaComplementoPotencial n) dibuja la gráfica de los complementos potenciales de los n primeros números enteros positivos. Por ejemplo, (graficaComplementoPotencial 100) dibuja
    Complemento_potencial_100
    y (graficaComplementoPotencial 500) dibuja
    Complemento_potencial_500

Comprobar con QuickCheck que (complemento x) es menor o igual que x.

Soluciones

Sumas parciales de Nicómaco

Nicómaco de Gerasa vivió en Palestina entre los siglos I y II de nuestra era. Escribió Arithmetike eisagoge (Introducción a la aritmética) que es el primer trabajo en donde se trata la Aritmética de forma separada a la Geometría. En el tratado se encuentra la siguiente proposición: «si se escriben los números impares

entonces el primero es el cubo de 1; la suma de los dos siguientes, el cubo de 2; la suma de los tres siguientes, el cubo de 3; y así sucesivamente.»

Definir las siguientes funciones

tales que

  • (listasParciales xs) es la lista obtenido agrupando los elementos de la lista infinita xs de forma que la primera tiene 0 elementos; la segunda, el primer elemento de xs; la tercera, los dos siguientes; y así sucesivamente. Por ejemplo,

  • (sumasParciales xs) es la lista de las sumas parciales de la lista infinita xs. Por ejemplo,

Comprobar con QuickChek la propiedad de Nicómaco; es decir, que para todo número natural n, el término n-ésimo de (sumasParciales [1,3..]) es el cubo de n.

Soluciones

El problema 3SUM

El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se pueden elegir los elementos 7, -9 y 2 que suman 0.

Definir las funciones

tales que
+ (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,

  • (pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,

Soluciones

De hexadecimal a decimal

El sistema hexadecimal es el sistema de numeración posicional que tiene como base el 16.

En principio, dado que el sistema usual de numeración es de base decimal y, por ello, sólo se dispone de diez dígitos, se adoptó la convención de usar las seis primeras letras del alfabeto latino para suplir los dígitos que nos faltan. El conjunto de símbolos es el siguiente: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. En ocasiones se emplean letras minúsculas en lugar de mayúsculas. Se debe notar que A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15.

Como en cualquier sistema de numeración posicional, el valor numérico de cada dígito es alterado dependiendo de su posición en la cadena de dígitos, quedando multiplicado por una cierta potencia de la base del sistema, que en este caso es 16. Por ejemplo, el valor decimal del número hexadecimal 3E0A es

Definir la función

tal que (hexAdec cs) es el valor decimal del número hexadecimal representado meiante la cadena cs. Por ejemplo,

Soluciones

Sucesión de raíces enteras de los números primos

Definir las siguientes funciones

tales que

  • raicesEnterasPrimos es la sucesión de las raíces enteras (por defecto) de los números primos. Por ejemplo,

  • (posiciones x) es el par formado por la menor y la mayor posición de x en la sucesión de las raíces enteras de los números primos. Por ejemplo,

  • (frecuencia x) es el número de veces que aparece x en la sucesión de las raíces enteras de los números primos. Por ejemplo,

  • (grafica_raicesEnterasPrimos n) dibuja la gráfica de los n primeros términos de la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_raicesEnterasPrimos 200) dibuja
    Sucesion_de_raices_enteras_de_primos_1
  • (grafica_posicionesIniciales n) dibuja la gráfica de las menores posiciones de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_posicionesIniciales 200) dibuja
    Sucesion_de_raices_enteras_de_primos_2
  • (grafica_frecuencia n) dibuja la gráfica de las frecuencia de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_frecuencia 200) dibuja
    Sucesion_de_raices_enteras_de_primos_3

Soluciones

Cadenas opuestas

La opuesta de una cadena de letras es la cadena obtenida cambiando las minúsculas por mayúsculas y las minúsculas por mayúsculas. Por ejemplo, la opuesta de «SeViLLa» es «sEvIllA».

Definir la función

tal que (esOpuesta s1 s2) se verifica si las cadenas de letras s1 y s2 son opuestas. Por ejemplo,

Soluciones

Número de viajeros en el autobús

Un autobús inicia su recorrido con 0 viajeros. El número de viajeros que se suben y bajan en cada parada se representa por un par (x,y) donde x es el número de las que suben e y el de las que bajan. Un recorrido del autobús se representa por una lista de pares representando los números de viajeros que suben o bajan en cada parada.

Definir la función

tal que (nViajerosEnBus ps) es el número de viajeros en el autobús tras el recorrido ps. Por ejemplo,

Soluciones

Caminos minimales en un árbol 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

Conjunto de funciones entre dos conjuntos

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

  • [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
  • [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
  • [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir las funciones

tales que

  • (funciones xs ys) es el conjunto de las funciones del conjunto xs en el conjunto ys. Por ejemplo,

  • (nFunciones xs ys) es el número de funciones del conjunto xs en el conjunto ys. Por ejemplo,

Soluciones

Reconocimiento de relaciones funcionales entre dos conjuntos

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Una relación R entre A y B es funcional si cada elemento de A está relacionado mediante R como máximo con un elemento de B. Por ejemplo, [(2,4),(1,5),(3,4)] es funcional, pero [(3,4),(1,4),(1,2),(3,4)] no lo es.

Definir la función

tal que (esFuncional r) se verifica si la relación r es funcional. Por ejemplo,

Soluciones

Sumas de dos cuadrados

Definir la función

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

Soluciones

[/schedule]

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