How to check whether it is possible to make the number 23 from the five given digits by the operations: + , - , * ?

  • if the number is 5, then it can be done in about 5! * 4 ^ 4 and without DP. - pavel
  • can you find out exactly how? - user209702
  • brute force You try, if something is not clear, ask, show the code, we will help. And for someone here do not do the job. - pavel
  • In fact, Knut in Volume 4 slipped that such problems are solved by brute force. Frankly, dynamic programming is not my thing, I am weak in it, so my opinion here is inexpensive ... but I don’t know how to apply it to this task. - Harry

1 answer 1

Very simple (in theory). Imagine that the problem has already been solved for 4 digits out of 5. That is, you know all the possible numbers that only can be obtained with 4 digits and the indicated operations. Now you need to "attach" the 5th digit to all these combinations with all possible operations. Accordingly, in order to solve a problem with four digits, it is necessary to solve first with three ... and so on up to one digit. With one digit, everything is trivial (although, here you need to look at whether unary minus is allowed).

This strategy, as it may seem, is not much different from the full search, but all such are simpler. Brute force results in hyperexponential complexity, and this method is only exponential. The only problem is how to correctly program it, but that is another question.

  • How to get the number 23 with one digit and unary minus? - αλεχολυτ
  • do you count multiply sign? it affects the order of operations and therefore we cannot get the value from the value in the previous step. More precisely, we can, but this is an extra parameter (then there will be parameters of the PD: [mask, value, value of the last block]) and for 5 elements I personally don’t see it. Now, if there were 10-15 of them :) - pavel
  • No I say that if the unary minus is resolved, instead of 5 starting options there will be 10. This complicates the task. - Zealint
  • @Zealint but not really, just 2 times more options, it's not so scary. - pavel
  • @pavel, notice that I am not saying HOW to implement it, but expressed an idea. The author asked the DP, here is his DP. - Zealint