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

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>

Diagonales invertidas

Definir la función

tal que (diagonalesInvertidas q) es la matriz obtenida invirtiendo el orden de los elementos de la diagonal principal y de la diagonal secundaria de q. Por ejemplo,

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>

Soluciones

Pensamiento

«No estamos muy contentos cuando nos vemos obligados a aceptar una verdad matemática en virtud de una complicada cadena de conclusiones formales y cálculos, que atravesamos a ciegas, eslabón por eslabón, sintiendo nuestro camino por el tacto. Queremos primero una visión general del objetivo y del camino; queremos entender la idea de la prueba, el contexto más profundo.»

Hermann Weyl.

Producto de Kronecker

Si A es una matriz m \times n y B es una matriz p \times q, entonces el producto de Kronecker A \otimes B es la matriz bloque mp \times nq

Más explícitamente, tenemos

Por ejemplo,

Definir la función

tal que (kronecker a b) es el producto de Kronecker de las matrices a y b. 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>

Pensamiento

«La resolución de problemas es una habilidad práctica como, digamos, la natación. Adquirimos cualquier habilidad práctica por imitación y práctica. Tratando de nadar, imitas lo que otras personas hacen con sus manos y pies para mantener sus cabezas sobre el agua, y, finalmente, aprendes a nadar practicando la natación. Al intentar resolver problemas, hay que observar e imitar lo que hacen otras personas al resolver problemas y, finalmente, se aprende a resolver problemas haciéndolos.»

George Pólya.

Matriz girada 180 grados

Definir la función

tal que (matrizGirada180 p) es la matriz obtenida girando 180 grados la matriz p. Por ejemplo,

Soluciones

Pensamiento

Bueno es recordar
las palabras viejas
que han de volver a sonar.

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

Diagonales invertidas

Definir la función

tal que (diagonalesInvertidas q) es la matriz obtenida invirtiendo el
orden de los elementos de la diagonal principal y de la diagonal
secundaria de q. Por ejemplo,

Soluciones

Pensamiento

Despertad, cantores:
acaben los ecos,
empiecen las voces.

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

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

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

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

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