I have this problem I need to solve and I have no idea even where to begin! Given 6 integers (int) the method I have to create shall determine wheter it exists any combination of the first 5 integers and + - * that gives the 6th argument as a result. If it does exists then the output should be an expression. Ex: java Expr 1 1 1 1 1 100 -> "no solution", java Expr 15 4 13 18 80 200 -> (18+80)*(15-13)+4. I would appreciate any tip that can help my in the process of solving this problem!
I say this look pretty easy. 0.- while there are more combinations 1.- try a combination 3.- if the result == lastArgument finish you've found the solution 4.- else try with a new combination If there's no more combinations there's no solution. Try some code with these ideas and if you have specific questions, I'll be glad to respond.
This sounds like a homework question Anyway, what you need to do, is to find all permutations of the 5 numbers and combine them with all the four-position combinations you can find of the three operators (+,-,*). To find the permutations and combinations, you can use simple recursive functions. If I've done everything correctly, the code below should print all the permutations of the 5 numbers and all the combinations of the three operators. Now all that needs to be done, is combine every permutation with every combination and check the result.
Edit: okay, so this problem is a bit trickier than I initially thought, since you also have to take into account the order in which to take the operations (the parenthesis).... (drat )... it would make a good homework assignment though [ November 03, 2003: Message edited by: Jaap van Hengstum ]
Joined: Nov 03, 2003
Thanx Jaap van Hengstum!
Jaap van Hengstum
Joined: Jul 24, 2003
If you are interested, I have made a Java program which does the job. It doesn't use the most optimal solution, but it gets all the possible answers, f.e. operating on your example numbers it gives the following solutions:
You see, it doesn't take into account the commutative and associative nature of the operators, so it gives too much solutions. To solve that, you probably need to use a totally different algorithm (than the one described above). It'll be nice to see if you or anyone else has come up with a better way though... [ November 05, 2003: Message edited by: Jaap van Hengstum ]