计算达到特定数量所需的最小操作数

Question

我该如何为这一挑战实施算法？

有三个整数,A,B和C.

您的计算器从数字1开始,它必须达到C.为此,您可以执行两项操作:

您必须返回到达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步骤.

我曾经通过强制执行结果(尝试了很多组合并抓住步数最少的那个).那太傻了.

Answer 1

这可以简化为图形上的最短路径问题G=(V,E),其中顶点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*搜索算法(如果你找到一个好的启发式)或双向搜索(基本上来自目标和来自源的BFS)来完成

编辑:(
注意:原始答案包含一些不同的边缘设置,适合稍微不同的问题.无论哪种方式 - 主要想法仍然存在)