数字组合算法 [英] number combination algorithm

问题描述

收件，鉴于数字字符串与目标值的函数，印刷品哪里放+的和*的数字之间，这样他们恰好结合到目标值。注意可能有多个答案，这不要紧，你打印的是哪一个。

例如：

 1231231234，11353  - ＆GT; 12 * 3 + 1 + 23 * 123 * 4
3456237490，1185  - ＆GT; 3 * 4 * 56 + 2 + 3 * 7 + 490
3456237490，9191  - ＆GT; 无解
 

解决方案

如果你有一个N位数的值，有N-1个可用插槽以+或*操作符。所以蛮力，还有3 ^（N-1）的可能性。测试所有这些都是低效的。

但

您的例子都是10位数字。 3 ^ 9 = 19683，所以蛮力是好的！无需得到任何票友。

因此​​，所有你需要做的是通过所有19683箱子每次构建一个字符串的情况下，并评估前pression迭代。评估前pression是一个简单的任务。迭代非常简单（只需使用一个递增值，可以通过（i％3），它给你没有运营商+或*，第二个插槽的状态读取的第一个插槽的状态（我/ 3）％3，第三槽的状态为（i / 9）％3等等。）

即使原油解析code，处理器的速度快。

蛮力选项开始变得难看后约20个数字，你就必须要切换到更聪明。

Write a function that given a string of digits and a target value, prints where to put +'s and *'s between the digits so they combine exactly to the target value. Note there may be more than one answer, it doesn't matter which one you print.

Examples:

"1231231234",11353 -> "12*3+1+23*123*4" 
"3456237490",1185  -> "3*4*56+2+3*7+490" 
"3456237490",9191  -> "no solution"

解决方案

If you have an N digit value, there are N-1 possible slots for the + or * operators. So brute force, there are 3^(N-1) possibilities. Testing all of these are inefficient.

BUT

Your examples are all 10 digits. 3^9 = 19683, so brute force is FINE! No need to get any fancier.

So all you need to do is iterate through all 19683 cases, each time building a string for that case, and evaluating the expression. Evaluating the expression is a straightforward task. Iterating is straightforward (just use an incrementing value, you can read the state of the first slot by (i%3), which gives you "no operator" "+" or "*", the state of the second slot is (i/3)%3, the state of the third slot is (i/9)%3 and so on.)

Even with crude parsing code, CPUs are fast.

The brute force option starts becoming ugly after about 20 digits, and you'd have to switch to be more clever.

这篇关于数字组合算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！