我该如何为这一挑战实施算法？
有三个整数，A，B和C.
您的计算器从数字1开始，它必须达到C.为此，您可以执行两项操作：
-
将您的数字乘以A（如果结果超过4位，结果将为1） .
-
将您的数字除以B（整数除法） .
您必须返回到达C所需的最少操作次数 .
此外，您的计算器只有四位数，因此您可以预期A，B和C输入最多为9999 .
例：
A = 2, B = 3, C = 10
1*A = 2
2*A = 4
4*A = 8
8*A = 16
16/B = 5
5*A = 10
所以结果将是 6 步 .
我曾经通过强制执行结果（尝试了很多组合并 grab 步数最少的那个） . 那太傻了 .
1 回答
这可以在图形
G=(V,E)上缩小为 shortest path problem ，其中顶点V={0,1,2,...,9999}和E = { (x,y) | y = x*a, y< 10,000 or y = x /b } U { (x,1) | x*a > 10,000 }现在，您需要找到从
1到目标的最短路径 . 它可以通过运行BFS，A* Search algorithm（如果你找到一个好的启发式）或bi-directional search（它基本上来自目标和来自源的BFS）来完成EDIT:
（注意：原始答案包含一些不同的边缘设置，适合稍微不同的问题 . 无论哪种方式 - 主要想法仍然存在）