python - 如何在乘法和除以 2 个不同的数字之间进行交换？

Question

我得到整数X、Y和Z。在每一步中，我可以乘以或除以 2 或 3。我需要以Y步将X转换为Z ......或者确定这是不可能的。

例如：

X is 9,
Y is 8,
Z is 4.

9 可以通过以下方式变为 4：9/3/3x2x2x2x2/2/2 = 4 如您所见，我进行了 8 次操作。

如何在 Python 中做到这一点？

Answer 1

首先使用描述性变量名称，例如start、target和steps。

不，没有简单的方法可以做到这一点，但有直接的方法。

首先，您需要找到必要的更改。将开始和目标分解为 2 的因数、3 的因数以及其他任何因素。如果这个“任何其他”不匹配，那么你根本无法解决问题。

例如，看看你给定的问题：从 9 到 4。分解每个数字：

9 = 3*3    # no 2's, no other stuff
4 = 2*2    # no 3's, no other stuff

由于“其他”内容匹配（即 1），您可以进行转换。您需要删除 3 的 2 个因数，并添加 2 的 2 个因数。这是 4 个步骤。从那里，您所要做的就是添加成对的 *3/3 或 *2/2，直到您有 8 个步骤。

让我们尝试将 56 更改为 126：

 56 = 2*2*2*7   # no 3's, other = 7
126 = 2*3*3*7   # other = 7

要进行转换，您需要删除两个 2 并添加两个 3。那是四个步骤；您像以前一样调整到所需的数字。

这是你的攻击；你能编码吗？

Answer 2

只是为了好玩，这里有一个可怕的扩展方法——O (y^4)，

def bruteforce(x, y, z, acc="", accv=None):
    if accv == z and len(acc) == y*2:
        return acc
    if accv is None:
        accv = x
    if len(acc) == y*2:
        return
    m2 = bruteforce(x, y, z, acc+'*2', accv*2)
    m3 = bruteforce(x, y, z, acc+'*3', accv*3)
    d2 = bruteforce(x, y, z, acc+'/2', accv/2)
    d3 = bruteforce(x, y, z, acc+'/3', accv/3)
    return m2 or m3 or d2 or d3

在行动：

In [49]: exp = bruteforce(9, 8, 4)

In [50]: exp
Out[50]: '*2*2*2*2/2/2/3/3'

In [51]: eval('9'+exp)
Out[51]: 4.0

In [52]: exp = bruteforce(13, 8, 4)

In [53]: exp

In [54]: exp = bruteforce(9, 7, 2)

In [55]: exp
Out[55]: '*2*2*2/2/2/3/3'

In [56]: eval('9'+exp)
Out[56]: 2.0

会因为浮点数不准确而出错...