algorithm - 使用乘以 2 或除以 3 以最少的步骤生成任何数字？

Question

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

Answer 1

这是一个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 的路径的问题。这给了我们答案，但顺序相反 - 路径的结尾在列表的开头。所以反过来，我们就有了答案。

我将其显示为我们访问的所有号码的记录和操作的记录。