algorithm - problems - problema 1 project euler

(ProjectEuler) Combinaciones de suma

Question

De ProjectEuler.net :

Prob. 76: ¿Cuántas formas diferentes se pueden escribir cien como una suma de al menos dos enteros positivos?

No tengo idea de cómo comenzar esto ... ¿algún punto en la dirección correcta o ayuda? No estoy buscando cómo hacerlo, pero algunos consejos sobre cómo hacerlo.

Por ejemplo, 5 se puede escribir como:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Entonces 6 posibilidades totales.

Answer 1

Al igual que la mayoría de los problemas en el Proyecto Euler con grandes números, la mejor manera de pensar en ellos es no dejarse arrastrar por ese enorme límite superior, pensar en el problema en términos más pequeños y progresar gradualmente. Tal vez, en el camino, reconozca un patrón, o aprenda lo suficiente como para obtener la respuesta fácilmente.

La única otra pista que creo que puedo darte sin estropear tu epifanía es la palabra ''partición''.

Una vez que te hayas dado cuenta, lo tendrás en un santiamén :)

Answer 2

Aviso: mi matemática está un poco oxidada pero espero que esto ayude ...

Estás yendo bien con tu desglose del problema.

Piensa en general:

• Un número n se puede escribir como (n-1) +1 o (n-2) +2
• Usted generaliza esto a (nm) + m
• Recuerde que lo anterior también se aplica a todos los números (incluido m)

Entonces la idea es encontrar el primer conjunto (digamos 5 = (5-1) +1) y luego tratar (5-1) como un nuevo n ... 5 = 4 +1 ... 5 = ((4 -1) +1) +1. La que está agotada empieza nuevamente en 5 = 3 + 2 ... que se convierte en 5 = ((3-1) +1) +2 .... = 2 + 1 + 2 ... rompiendo cada uno a medida que avanza.

Answer 3

Una buena forma de abordar esto no es obsesionarse con el ''100'', pero trate de considerar cuál sería la diferencia entre sumar para una suma nyn + 1 , buscando patrones a medida que n aumenta 1,2,3 ... .

Me gustaría ir ahora, pero tengo trabajo que hacer :)

Answer 4

un enfoque es pensar la función recursiva : encontrar permutaciones de una serie numérica extraída de los enteros positivos (duplicados permitidos) que suman 100

• el cero es 1, es decir, para el número 1 hay cero soluciones
• la unidad es 2, es decir, para el número 2 solo hay una solución

Otro enfoque es pensar en la función generadora : comience con el cero y encuentre la serie de permutación hasta el objetivo, manteniendo un mapa / hash o los valores intermedios y los recuentos

puede iterar desde 1 o recurse hacia abajo desde 100; obtendrás la misma respuesta de cualquier manera. En cada punto podría (para una solución ingenua) generar todas las permutaciones de la serie de enteros positivos contando hasta el número objetivo menos 1, y contar solo los que se suman al número objetivo

¡buena suerte!

Answer 5

Partition Numbers (o Partition Functions) son la clave de este.

Problemas como estos suelen ser más fáciles si comienzas desde abajo y sigues subiendo para ver si puedes detectar algún patrón.

• P (1) = 1 = { 1 }
• P (2) = 2 = {[2], [1 + 1]}
• P (3) = 3 = {[3], [2 + 1], [1 + 1 + 1]}
• P (4) = 5 = {[4], [3 + 1], [2 + 2], [2 + 1 + 1], [1 + 1 + 1 + 1]}
• P (5) = 7 ...
• P (6) = 11 ...
• P (7) = 15 ...
• P (8) = 22 ...
• P (9) = 30 ...

Sugerencia: vea si puede construir P ​​(N) desde alguna combinación de los resultados anteriores a P (N).

Answer 6

Muchos problemas matemáticos se pueden resolver por inducción . Conoce la respuesta para un valor específico, y puede encontrar la respuesta para cada valor, si encuentra algo que vincule n con n+1 .

Por ejemplo, en su caso, usted sabe que la respuesta para ¿De cuántas maneras diferentes se puede escribir una suma de al menos dos enteros positivos? es solo 1.

¿Qué quiero decir con el enlace entre n y n+1 ? Bueno, quiero decir exactamente que debes encontrar una fórmula que, si conoces la respuesta para n , encontrarás la respuesta para n+1 . Luego, llamando recursivamente a esa fórmula, sabrá la respuesta y lo habrá hecho (nota: esta es solo la parte matemática de ella, en la vida real puede encontrar que este enfoque le daría algo demasiado lento para ser práctico, por lo que aún no lo ha hecho, en este caso, creo que habrá terminado).

Ahora, supongamos que sabe que n se puede escribir como una suma de al menos dos enteros positivos. en k formas diferentes, una de las cuales sería:

n = a1 + a2 + a3 + ... am (esta suma tiene m términos)

¿Qué puedes decir sobre n+1 ? Ya que solo le gustaría dar pistas, no estoy escribiendo la solución aquí, sino solo lo que sigue. Seguramente tienes las mismas k maneras diferentes, pero en cada una de ellas habrá el término +1 , uno de los cuales sería:

n + 1 = a1 + a2 + a3 + ... am + 1 (esta suma tiene m + 1 términos)

Entonces, por supuesto, tendrá otras k posibilidades, como aquellas en las que el último término de cada suma no es el mismo, pero se incrementará en una, como:

n + 1 = a1 + a2 + a3 + ... (am + 1) (esta suma tiene m términos)

Por lo tanto, hay al menos 2k formas de escribir n+1 como una suma de al menos dos enteros positivos . Bueno, hay otros. Descúbrelo, si puedes :-) Y disfruta :-))

Answer 7

La solución se puede encontrar usando un algoritmo de corte.

Use por ejemplo el 6. Entonces tenemos:

6
5+1
4+2
3+3

pero aún no hemos terminado

Si tomamos el 5 + 1, y consideramos que la parte +1 está terminada, todas las demás combinaciones finales son manejadas por 4 + 2 y 3 + 3. Entonces tenemos que aplicar el mismo truco al 5.

4+1+1
3+2+1

Y podemos continuar Pero no sin pensar. Porque, por ejemplo, 4 + 2 produce 3 + 1 + 2 y 2 + 2 + 2. Pero no queremos el 3 + 1 + 2 porque tendremos un 3 + 2 + 1. Entonces solo usamos todas las producciones de 4 donde el número más bajo es mayor o igual que 2.

6
5+1
  4+1+1
    3+1+1+1
      2+1+1+1+1
        1+1+1+1+1+1
    2+2+1+1
  3+2+1
4+2
  2+2+2
3+3

El siguiente paso es poner esto en un algoritmo.

Ok, necesitamos una función recursiva que tome dos parámetros. El número a cortar y el valor mínimo:

func CountCombinations(Number, Minimal)
  temp = 1
  if Number<=1 then return 1
  for i = 1 to Floor(Number/2)
    if i>=Minimal then
      temp := temp + CountCombinations(Number-i, i)
  end for
  return temp
end func

Para verificar el algoritmo:

C(6,1) = 1 + C(5,1) + C(4,2) + C(3,3) = 11, which is correct.
C(5,1) = 1 + C(4,1) + C(3,2) = 7
C(4,1) = 1 + C(3,1) + C(2,2) = 5
C(3,1) = 1 + C(2,1) = 3
C(2,1) = 1 + C(1,1) = 2
C(1,1) = 1
C(2,2) = 1
C(3,2) = 1
C(4,2) = 1 + C(2,2) = 2
C(3,3) = 1

Por cierto, la cantidad de combinaciones de 100:

CC(100) = 190569292
CC(100) = 190569291 (if we don''t take into account 100 + 0)