suma de los números que hacen una secuencia de

Question

Mientras observa el rugby anoche me preguntaba si alguna puntuaciones fueron imposible teniendo en cuenta que sólo se puede ganar puntos en lotes de 3, 5 o 7. No pasó mucho tiempo para saber que cualquier número mayor que 4 es alcanzable. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5 y así sucesivamente.

Extendiéndose sobre esa idea de 5, 7 y 9 se obtienen los siguientes resultados posibles:

5,7,9,10,12,14 // and now all numbers are possible. 

Para 7, 9 y 11:

7,9,11,14,16,18,20,22,23,25,27 // all possible from here 

hice esto en mi cabeza, ¿alguien puede sugieren un buen algoritmo que determinaría el puntaje más bajo posible por encima del cual todos los puntajes son alcanzables dado un conjunto de puntajes.

Modelé así:

forall a < 10: 
    forall b < 10: 
     forall c < 10: 
      list.add(3a + 5b + 7c); 
list.sort_smallest_first(); 

continuación, compruebe la lista de una secuencia más larga de 3 (el más pequeño puntuación posible). Parece bastante poco práctico y lento para cualquier cosa más allá del caso trivial.

Answer 1

Sólo hay un número inalcanzable por encima del cual todas las puntuaciones son alcanzables.

Esto se conoce como el número de Frobenius. Ver: http://en.wikipedia.org/wiki/Frobenius_number

La página wiki debe tener enlaces de algoritmos para resolverlo, por ejemplo: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Para 2 números a, b se conoce una fórmula exacta (ab-ab) (que se puede utilizar para cortar abajo de su espacio de búsqueda), y para 3 números a, b, límite inferior nítido (sqrt (3abc) -abc) y se conocen algoritmos bastante rápidos.

Si los números están en progresión aritmética, a continuación, una fórmula exacta es conocida (ver wiki). Menciono esto porque en sus ejemplos todos los números están en progresión aritmética.

Así que para responder a su pregunta, busque el número de Frobenius y añadir 1 a la misma.

Espero que ayude.