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

Question

我得到了整数X、Y和Z。在每一步中，我可以乘或除，2或3。我需要将X转换成Z，精确地Y步。。。或者确定这是不可能的。你知道吗

例如：

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

9可以通过：9/3/3x2x2x2/2/2=4变为4 你可以看到我做了8次手术。你知道吗

如何在Python中实现这一点？你知道吗

Answer 1

只是为了好玩，这里有一个蛮力的方法，它可以可怕地扩展到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

会因为浮点不准确而出错。。。你知道吗

Answer 2

首先使用描述性变量名，例如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），所以可以进行转换。你需要去掉2/3的因子，再加上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。这是四个步骤；您可以像以前一样调整到所需的数字。你知道吗

这是你的攻击，你能编码吗？你知道吗