Nada, ni una respuesta. Pues toca explicarlo, pero vamos a simplificar un poquito. Vamos a poner que nuestro objetivo es el numero 20 y que tenemos que hallar las combinaciones usando los numeros del 1 al 10.
Pues empezamos. Prefiero empezar de mayor a menor, porque es mas sencillo. El numero de combinaciones original es de 1024, lo que son bastantes.
Empezamos a mirar, cogemos el primer numero, 10. No suma 20, asi que necesitamos mas numeros en el conjunto, entonces sumamos el siguiente numero. Tenemos 10+9, que suma 19 y sigue siendo inferior a 20. Tenemos que seguir probando, por tanto. Sumamos ahora el 8 y nos encontramos que 10+9+8 suman 27. No suma 20 tampoco. Pero si sumasemos mas, todavia nos alejariamos aun mas del numero objetivo, el 20. Podemos por tanto descartar todas las sumas que incluyan 10+9+8, porque siempre superaran 20.
Volvemos atras. El 10+9 era un paso correcto, podemos seguir intentando con el siguiente numero, el 8. No me extendere, sino que lo pondre en la siguiente tabla.
10: NO LLEGA A 20. Continuamos.
10+9 = 19: NO LLEGA A 20. Continuamos.
10+9+8 = 27: SE PASA. No continuamos agregando mas numeros.
10+9+7 = 26: SE PASA. No continuamos.
10+9+6 = 25: SE PASA. No continuamos.
10+9+5 = 24: SE PASA. No continuamos.
10+9+4 = 23: SE PASA. No continuamos.
10+9+3 = 22: SE PASA. No continuamos.
10+9+2 = 21: SE PASA. No continuamos.
10+9+1 = 20: RESULTADO CORRECTO.
Hemos encontrado uno de los resultados correctos, pero queremos encontrar todos los que sumen 20, asi que seguimos avanzando. Intentamos continuar, pero como hemos descartado todas las combinaciones con el 9 al no haber numeros menores que el 1, pasamos al 8.
10+8 = 18: NO LLEGA.
10+8+7 = 25: SE PASA. No continuamos.
10+8+6 = 24: SE PASA. No continuamos.
10+8+5 = 23: SE PASA. No continuamos.
10+8+4 = 22: SE PASA. No continuamos.
10+8+3 = 21: SE PASA. No continuamos.
10+8+2 = 20: RESULTADO CORRECTO.
Despues de este resultado seguimos, y lo hacemos usando el siguiente elemento de la lista.
10+8+1 = 19. NO LLEGA.
Hemos vuelto a llegar a un resultado que no nos permite agregar un numero menor que 1 a la suma. Debemos seguir con la siguiente combinacion:
10+7 = 17. NO LLEGA.
10+7+6 = 23. SE PASA. No continuamos.
Podria seguir, pero es tedioso. Como ya imaginais llegaremos al 10+1, y a ese seguira el 9, y a ese el 9+8, y a ese el 9+8+7, y a ese el 9+8+6...
El algoritmo es bastante simple, por tanto.
Cogemos un conjunto de numeros (empezamos por un conjunto vacio). Se le agrega el numero mas alto disponible. Si la suma es inferior al numero buscado, volvemos a agregar el numero mas alto disponible. Si la suma es mayor, descartamos todas las combinaciones que incluyan esos numeros y sustituimos el ultimo numero agregado por el siguiente numero mayor. Si no nos quedan numeros menores, retiramos el ultimo numero añadido y el anterior lo sustituimos por el siguiente numero menor.
Es un galimatias, ya lo se.
En cuanto a las otras preguntas que hice, el numero de combinaciones es el mismo (lo demostrare con el propio programa) en el orden que sea. Eso si, la velocidad a la hora de encontrar resultados validos si cambiara junto con el orden.
Lo siguiente que toca ya es programacion pura y dura. Pero ire explicandola paso a paso.
Mientras tanto, si quereis seguir este experimento desde casa, podeis ir descargando el JDK (Java Development Kit) y el Eclipse desde estas dos paginas: http://www.oracle.com/technetwork/java/javase/downloads/index.html y https://www.eclipse.org/downloads/
Debereis instalar el JDK primero. El Eclipse no requiere instalacion.
No hay comentarios:
Publicar un comentario