时间戳

首页 > 解决方案 > 我的问题可以用 Python 解决吗？是这样，怎么样？

python - 我的问题可以用 Python 解决吗？是这样，怎么样？

问题描述

我需要能够准确地输入两个部分已知的因子，每个因子都精确到小数点后 15 位，并且产品答案精确到小数点后 29 位。在程序运行期间，两个因子的起始数字（0.199848... 和 4.97438...）必须保持不变。每个因素中的零是 Python 必须使用的并且“在数值上改变”。当因子相乘时，这种“数值变化”必须产生 0.99412293432154732337566954206 到小数点后 29 位的乘积，以匹配我的产品输入。我想知道 Python 完成运行后与匹配产品的最终因素是什么。

例子：

我的输入因子 1 0.199848000000000 因子 2 4.974380000000000 产品 0.99412293432154732337566954206

输出：输出应该是 0.199848442087413 X 4.974384208042620 = 0.99412293432154732337566954206

因此，总而言之，Python 会找出与我输入的已知产品 0.99412293432154732337566954206 的输入相匹配的因素。我认为 Python 可能会在零上使用组合/排列，直到找到产生我输入产品的组合。

标签： python

解决方案

一些指针；

  • 您不能使用浮点数。那些只有大约 17 个十进制数字的精度，从十进制到二进制浮点的转换本质上是不精确的。
  • 一个好的起点是decimal模块。

例如：

In [1]: import decimal as dm

In [2]: dm.getcontext().prec = 29

In [3]: factor1 = dm.Decimal('0.199848')
Out[3]: Decimal('0.199848')

In [4]: factor2 = dm.Decimal('4.97438')
Out[4]: Decimal('4.97438')

In [5]: desired = dm.Decimal('0.99412293432154732337566954206')
Out[5]: Decimal('0.99412293432154732337566954206')

In [6]: factor1*factor2 > desired
Out[6]: False
  • 正如 Błotosmętek 在评论中指出的那样，组合的数量太大而无法进行蛮力搜索。所以你必须以另一种方式。

请记住，产品可以；

  • 小于要求的结果，
  • 等于要求的结果或
  • 大于要求的结果。

在第一种情况下，其中一个因素必须变得更大。在最后一种情况下，其中一个因素必须变得更小。

由于第二个因素是最大的，我会从factor1. 将 9 附加到小数（可能的最大增加），并检查乘积是否大于目标。

In [7]: new1 = dm.Decimal('0.1998489')
Out[7]: Decimal('0.1998489')

In [8]: new1*factor2 > desired
Out[8]: True

所以这个数字太大了。小于 9/2 的最大整数是 4，所以尝试一下。

In [9]: new1 = dm.Decimal('0.1998484')
Out[9]: Decimal('0.1998484')

In [10]: new1*factor2 > desired
Out[10]: False

现在将 0.1998489 和 0.1998484 之间的距离减半。并再次检查。你会发现 0.1998487 太大了，但 0.1998486 不是。

现在继续寻找 的下一位数字factor1，依此类推，直到找到 的正确位数factor1。

然后对 做同样的事情factor2，但现在还要测试是否相等。

编辑：关于蛮力所需的时间。

在我的机器上将两个 s 相乘Decimal并将其与三分之一进行比较大约需要 119 ns。有人可能认为这还不算太糟糕。

In [2]: from decimal import Decimal

In [3]: f1 = Decimal('0.199848')
Out[3]: Decimal('0.199848')

In [4]: f2 = Decimal('4.97438')
Out[4]: Decimal('4.97438')

In [6]: result = Decimal('0.99412293432154732337566954206')
Out[6]: Decimal('0.99412293432154732337566954206')

In [7]: %timeit f1*f2 == result
119 ns ± 0.0114 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

但考虑最坏的情况，我们必须进行 10^19 次计算。让我们看看这需要多长时间：

In [9]: round(119e-9*1e19/3600/24/365.25, 0)
Out[9]: 37709

因此，检查整个问题域至少需要38000 年。

当然，您可以幸运地在几次尝试后找到正确的结果。但不要指望这一点。如果事先不知道去哪里寻找，您可以合理地期望需要检查一半的问题域。那大约是19000年。因此，Błotosmętek 说暴力搜索是不可行的。

推荐阅读