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

Question

使用2乘以或3除以最少的步骤生成任何数字？任何想法如何有效地解决这个问题？我正在考虑动态编程，但不确定。因此，例如，我能想到的最好的解决方案是通过2 * 2 * 2 * 2 * 2 * 2/3/3 = 7来获得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 的路径的问题。这为我们提供了答案，但顺序相反-路径的末尾位于列表的开头。因此，扭转它，我们有答案。

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