数字组合算法

Question

编写一个给出一串数字和目标值的函数,打印在数字之间放置+'和*的位置,使它们与目标值完全组合.请注意,可能有多个答案,您打印哪一个并不重要.

例子:

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

Answer 1

如果您有一个N位数值,则+或*运算符有N-1个可能的插槽.如此蛮力,有3 ^(N-1)种可能性.测试所有这些都是低效的.

但

你的例子都是10位数.3 ^ 9 = 19683,所以蛮力很精细!没有必要得到任何鸽友.

因此,您需要做的就是遍历所有19683个案例,每次为该案例构建一个字符串,并评估表达式.评估表达式是一项简单的任务.迭代是直截了当的(只需使用递增值,你可以通过(i%3)读取第一个槽的状态,这给你"无操作符""+"或"*",第二个槽的状态是(i/3)%3,第三个槽的状态是(i/9)%3,依此类推.)

即使使用原始解析代码,CPU也很快.

蛮力选项在大约20个数字后开始变得难看,你必须切换到更聪明.