algorithm - 乘以2或除以3即可在最少的步骤中生成任何数字？

乘以2或除以3即可在最少的步骤中生成任何数字？任何想法如何有效地解决这个问题？我正在考虑动态编程，但不确定。
因此，例如，我能想到的最好的解决方案是通过2 * 2 * 2 * 2 * 2 * 2/3/3 = 7来获得7。在这里，我的意思是C++或Java中的整数除法。谢谢!

最佳答案

这是一个BFS动态编程解决方案。

#! /usr/bin/env python
wanted = 7
found = {1: None}
added = [1]
while True:
    new_added = []
    for x in added:
        if 2*x not in found:
            found[2*x] = [x, 2]
            new_added.append(2*x)
        if x/3 not in found:
            found[x/3] = [x, 3]
            new_added.append(x/3)
    if wanted in found:
        break
    # This magic line copies new_added over the added array.
    added[:] = new_added

answer = []
path = [wanted]
while path[-1] != 1:
    node = found[path[-1]]
    path.append(node[0])
    answer.append(node[1])

print([x for x in reversed(answer)])
print([x for x in reversed(path)])

这是一个解释。

BFS表示广度优先搜索。在这种情况下，我们将并行搜索长度为1、2、3等的所有路径，直到完成。

动态编程指的是多种方法来存储已完成工作的记录，以便我们既可以避免工作，又可以回头引用已经完成的工作。

在这种情况下，found记录了我们找到的所有数字的路径以及从中获得的整数以及要使用的运算。 added是我们在最后一次通过时发现的所有整数的记录。 new_added是我们在此传递中找到的所有整数。

因此，我们从一条记录开始，说我们知道如何到达1。然后在每遍中，我们取所有刚刚添加的记录，并乘以2或除以3，以查看要获得的新记录。

一旦找到目标，我们便停止。然后是通过found查找返回到1的路径的问题。这给了我们答案，但是顺序相反-路径的末尾在列表的开头。因此，扭转它，我们得到了答案。

我既显示了我们访问的所有号码的记录，又显示了操作的记录。

关于algorithm - 乘以2或除以3即可在最少的步骤中生成任何数字？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47125112/