Suma minimal de productos de pares de elementos consecutivos

Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:

  • 10, por ejemplo con [1,4,2,3] ya que 1×4+2×3 = 10
  • 11, por ejemplo con [1,3,2,4] ya que 1×3+2×4 = 11
  • 14, por ejemplo con [1,2,3,4] ya que 1×2+3×4 = 14

Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].

Definir las funciones

tales que

  • (minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

  • (permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

Soluciones

8 Comentarios

  1. Una primera versión (sin optimizar):

  2. El razonamiento se basa en que los números más grandes se deben unir con los más pequeños.
    Como nx = x+x…+x (n veces), es recomendable multiplicar x por el número más pequeño posible, para que x se sume el mínimo de veces.

Escribe tu solución