如何在单位数整数上使用最少的初等算术运算(加、减、乘、除)来计算任意整数?
0-9中的数字代价为0。其它数必须用基本运算在它们的基础上建立起来。
例子:25是由5*5组成的
123可以通过许多不同的方式建立，但最理想的是5*5*5-2。
一开始我想用动态规划来解决它，但我无法克服引入乘法的障碍，我认为它对大数不实用。如果是，请告诉我怎么做。
如果有人能指导我解决类似的问题，我将不胜感激。
不幸的是，您正在寻找的答案并不像关于SO的其他问题那样直截了当。结果就是你被否决了好几次。我可能不会这么快就扣动扳机，但这是一个有效的问题。
我建议你只用一次算术运算(所有在-9到18之间的整数和出现在乘法表中的数字)确定可以到达的数字集，用两次算术运算…使用三个算术运算等等，使得给定数目的算术运算的解集中的成员关系可以确定给定目标整数x:
的语句大小的最小值。{xλ I} cA(N
);整数的单元素x是a的子集(N)，其中A(N)定义为执行N后可能解的集合可能的算术运算。(最小上界(N)定义为"1+1+1…"中的算术运算次数。+1+1"表示正数，"0-1-1…"-1-1"(负数)
则最优解集定义为:
(下确界(NN)使算术运算的次数最小化。
编辑:今天晚上我用铅笔做了进一步的粗略整理，之前我建议非质数作为A的成员(1)，对于素数因子>= 11的任何非素数都是例外。其中最小的是22，如下所示。
如果我们以A开头(0)定义为整数的闭集[0,9]然后(n+1) =u((n)、(0))，u是算术函数的集合因为除法不可能是最优解的一部分，因为对于非理性结果存在最小公倍数，那么u'(x, y) = {x + y, x - y, x * y};包含x和y为整数的最小限制集。
同样的消去法并不适用于减法，因为我们需要乘积上下的邻域。
我们也可以从所有最优解中消除零，留下A'(0) =[1,9]。因为我们注意到单例{0}εA(0)，因为根据0的定义，
0 *A(n) = 0，且
0 +A(n) =A(n)
0的最优解总是"0"，由于"+0+"的任何出现，或者乘积空间中的零抵消了整个乘积或零加法步骤，因此解不是最优的，因此可以从搜索中排除。
那么在伪代码中找到A的整个解集的一种方法(n)， n λ n(自然)，忽略运算顺序将是:**A**(n) = **A**(n-1); // n*1 is still included,
// and n+0 is by proxy included for posterity
for x ϵ **A**(n-1)
for y ϵ **A'**(0)
for u ϵ **u'**
A(n) = Union( A(n), u(x,y) );
next u
next y
next x
请注意，我不能确定输出是否排序，而且我们忽略了操作顺序，所以这还不是一个有效的，完整的算法，对于你正在寻找的解决方案，而且我还在打瞌睡，所以我将再次编辑并描述操作顺序。
编辑:操作顺序描述
首先，感谢您接受这个解决方案，正如我昨晚所说，我将描述操作顺序。
既然我们是专门处理乘法，那么我们应该首先找到语句中的乘积，这样我们就会得到一个集合p，表示隐藏在可接受语句中的一组加数和求值产品;我们不表示P
首先我们需要遍历字符串查找乘法操作这样我们就可以创建一个数组p整数的和是语句的解。在伪代码中可能像这样:
array **P** = empty // the upper limit for the bounds of **P**
// is number of operators - number of multiplications + 1
first **P** = first **d** // we can initialize the first value of **P**
for j ϵ N, j <= n // j is a natural number and 'n' is the number of operators
given u(j) ϵ **u** // **u** is the set of operations
given d(j) ϵ **d** // **d** is the set of digits of length n + 1
if u(j) is not multiplication
{
**P** = Union( **P**, d(j+1) ); // append d(j+1) to the end of **P**
if u(j) is subtraction negate last **P** // then last **P** is negative
}
else //---> u(j) is multiplication
{
last **P** *= d(j+1)
}
next j
solution = sum **P**; solution ϵ I.
现在我们有一个例程来根据操作顺序对语句求值，我们称之为eval。回到前面的循环结构，当我们尊重操作顺序时，递归属性优化就失效了。
("2+4*3" = 14 not 18)
因此，我们被困在一个例程中，它必须在可能的语句集合中搜索'n'个操作。然后我们可以通过消除加法和乘法的0来缩小语句的范围，进一步通过消除乘法的1来缩小语句的范围，看起来你也已经这样做了。我假设您提供的密码不仅在附加数字"1"之前检查前一个操作是u御{+，-}，而且在附加操作u御{*}之前检查前一个数字不是"1"。
一旦我们能够在给定长度的优化语句集中搜索目标整数，我们就可以迭代语句的length属性，直到目标整数是一个求值的解，然后我们可以开始将求值为目标整数的最小长度的语句保存到字符串数组中，并在迭代给定长度的其余语句后停止。
那将是一个详尽的搜索。即使我们要检查目标整数是否可整除为数字的乘积空间，当我们不能将其清晰地分解为单个数字的乘积空间时，会发生什么?给定一组整数，这些整数由不确定长度的个位数的乘积空间表示，并且具有表示该空间的最优解和乘积空间中乘法次数的映射，您能提出一个数论优化吗?如果没有，那么我们现在就只能进行穷举搜索了。
在阅读了@JustKevin的答案并重新思考了这个问题之后，我发现了一个启发式的方法，可能对我来说已经足够好了。
它基于动态编程，找到最短的操作序列长度来实现数字，但可以很容易地修改以创建该序列。
(如果有人可以修复格式，请，因为我从手机上写，它在我身上表现得很奇怪)
:
数组M对所有未设置的参数返回无穷大，函数c(i,x)描述了将i转换为x的代价，N是目标数。
M[0..9]=0
c(i,x) =
min(
if x==i then 0,
if x>i then M[x-i] + 1, //addition
if x<i then M[-x+i] + 1, //subtraction
min( for y=2,9 yield c(i*y,x) + 1 end) //multiplication
)
for x=10,N do
for i=1,x-1 do
M[x]= min(M[x], M[i]+c(i, x)
end
end
答案在M[N]。
如果你发现可能的错误，告诉我。