La solución se puede encontrar usando un algoritmo de corte.
uso, por ejemplo, el 6. Entonces tenemos:
6
5+1
4+2
3+3
pero no hemos terminado todavía.
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. Por lo que sólo utilizamos 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
siguiente paso es poner esto en un algoritmo.
Ok, necesitamos una función recursiva que tenga dos parámetros.El número a ser cortado 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 comprobar 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, el número de combinaciones de 100:
CC(100) = 190569292
CC(100) = 190569291 (if we don't take into account 100 + 0)
En realidad, tengo una idea, pero no sé cómo poner esa idea en una forma programable. – Devoted
Parece que ya has encontrado una forma. Intuitivamente has determinado un método recursivamente enumerable. En realidad, usar recursividad te daría una solución bastante elegante. Tenga en cuenta que al concatenar todas las formas en que puede agregar 3 y todas las formas de sumar 2, ha determinado varias formas de agregar 5 – BobbyShaftoe
, el título podría ser un poco más específico :-) –