如何使用最少的基本算术运算(add,sub,mult,div)尽可能最佳地计算单个数字整数的任意整数？
数字形式0-9有0成本.其他数字必须使用基本操作从它们构建.
示例:25从5*5构建
123可以通过许多不同的方式建立,但最优的是5*5*5-2.
起初我想通过动态编程来解决这个问题,但我无法克服引入乘法的障碍,我认为这对大数字来说并不实用.但如果是,请告诉我该怎么做.
如果有人可以指导我找到类似于此的正确问题,我将不胜感激.
不幸的是，您正在寻找的答案并不像其他问题那样简单。结果是你多次被否决。我可能不会这么快就扣动扳机，但这是一个有效的问题。
\n\n我建议您确定仅通过一次算术运算即可达到的一组数字（-9 到 18 之间的所有整数以及乘法表中出现的数字），通过两次算术运算...通过三个算术运算等等，这样给定数量的算术运算的解决方案集中的成员资格可以确定给定目标整数x的语句大小的下确界的语句大小的下确界：
\n\n{ x \xcf\xb5 I} c A ( N );
\n\n整数的单元素“x”是A ( N ) 的子集，其中A ( N ) 被定义为执行N 种可能的算术运算后可能的解决方案的集合。（上界（N）定义为正数“1+1+1...+1+1”和负数“0-1-1...-1-1”中算术运算的次数）
\n\n那么最优解集将定义为：
\n\nA ( 下确界 ( N ) )，其中下确界 ( N ) 最小化算术运算的数量。
\n\n编辑：\n今晚我用铅笔做了一些进一步的粗略处理，之前我曾建议非素数作为A的成员 (1) 的成员，这对于素数因子 >= 11 的任何非素数来说都是一个例外。其中最少的是 22，如下所示。
\n\n如果我们从定义为整数闭集 [0,9]\n的A (0) 开始，则A (n+1) = u ( A (n), A (0) ), u是算术函数集。
\n\n由于除法不能成为最优解的一部分，由于非有理结果存在最小公倍数，那么u \'(x, y) = { x + y, x - y, x * y }; 包含 x 和 y 的最小限制集是整数。
\n\n同样的消去法不适用于减法，因为我们需要乘积上方和下方的邻域。
\n\n我们也可以从所有最优解中消除零，留下A \'(0) = [1,9]。\n因为我们注意到单例 {0} \xcf\xb5 A (0) 并且根据零的定义，
0 * A (n) = 0, 且
\n0 + A (n) = A (n)
零的最佳解决方案始终是“0”，并且由于“+0+”的任何出现或乘积空间内的零抵消了整个乘积或零加法步骤，因此该解决方案不是最佳的，因此可以从该解决方案中排除搜索。
\n\n那么用伪代码找到A的整个解决方案集的一种方法 (n), n \xcf\xb5 N （自然数）的整个解决方案集的一种方法，忽略操作顺序将是：
\n\n**A**(n) = **A**(n-1); // n*1 is still included, \n // and n+0 is by proxy included for posterity \n\nfor x \xcf\xb5 **A**(n-1)\n for y \xcf\xb5 **A\'**(0)\n for u \xcf\xb5 **u\'**\n A(n) = Union( A(n), u(x,y) );\n next u\n next y\nnext x \n请注意，我无法确定输出是否已排序，而且我们忽略了操作顺序，因此对于您正在寻求的解决方案来说，这还不是一个有效、完整的算法，而且我正在打瞌睡，所以我将编辑再次说明操作顺序。
\n\n编辑：操作顺序的描述
\n\n首先，感谢您接受这个解决方案，正如我昨晚所说，我将描述操作顺序。
\n\n由于我们具体处理乘法，所以我们应该首先找到语句中的乘积，这样我们就有一个集合P，它将表示埋在可接受的语句中的加数和评估乘积的集合；我们不会代表P用字符串来
\n\n所以首先我们需要遍历字符串并查找乘法运算，这样我们就可以创建一个数组P，其总和就是该语句的解。在伪代码中，这可能看起来像这样：
\n\narray **P** = empty // the upper limit for the bounds of **P**\n // is number of operators - number of multiplications + 1\n\nfirst **P** = first **d** // we can initialize the first value of **P**\n\nfor j \xcf\xb5 N, j <= n // j is a natural number and \'n\' is the number of operators\n\n given u(j) \xcf\xb5 **u** // **u** is the set of operations\n given d(j) \xcf\xb5 **d** // **d** is the set of digits of length n + 1 \n\n if u(j) is not multiplication\n {\n **P** = Union( **P**, d(j+1) ); // append d(j+1) to the end of **P**\n if u(j) is subtraction negate last **P** // then last **P** is negative\n }\n else //---> u(j) is multiplication\n {\n last **P** *= d(j+1)\n }\n\nnext j\n\nsolution = sum **P**; solution \xcf\xb5 I. \n现在我们有一个例程来根据操作顺序评估语句，我们可以调用eval。回到前面的循环结构，当我们尊重操作顺序时，递归属性优化就会失败。
("2+4*3" = 14 not 18)\n因此，我们陷入了必须在可能的语句集中搜索\'n\'操作的例程。然后，我们可以通过消除零的加法和乘法来缩小语句集，并进一步通过消除一的乘法来缩小语句集，看来您也已经这样做了。我假设您提供的神秘内容不仅检查前一个操作是 u \xcf\xb5 { +, - } 在附加数字 \'1\' 之前，而且还检查前一个数字不是 \'1 \' 在附加操作 u \xcf\xb5 { * } 之前。
\n\n一旦我们能够在特定长度的优化语句集中搜索目标整数，我们就可以迭代语句的长度属性，直到目标整数是一个评估的解决方案，然后我们就可以开始将最小长度评估的语句保存到将目标整数放入字符串数组中，并在迭代给定大小的其余语句后停止。
\n\n这将是一次详尽的搜索。即使我们要检查目标整数是否能被数字的乘积空间整除，当我们无法将其干净地分解为单位数的乘积空间时会发生什么？您能否提出数论优化，给定一组整数，这些整数由具有不确定长度的个位数的乘积空间表示，并具有指示该空间的最佳解决方案和乘积空间中的乘法次数的映射？如果没有，那么我们现在就只能进行详尽的搜索。
\n| 归档时间： |
|
| 查看次数： |
208 次 |
| 最近记录： |