计算达到某一数目所需的最小操作数
计算达到某一数目所需的最小操作数
提问于 2014-04-09 18:16:48
我应该如何为这个挑战实现一个算法？
有三个整数，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步骤。
我曾经用暴力强迫结果(尝试很多组合，抓住一个步骤最少的一个)。那太傻了。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-04-09 18:24:43
这可以简化为图G=(V,E)上的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、搜索算法 (如果您找到了一个很好的启发)或双向搜索 (基本上是来自目标和源的BFS )来实现。
编辑：
(注:原来的答案包含了一些不同的边缘集，这符合一个稍微不同的问题。不管是哪种方式--主要的想法依然存在)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22970764
复制相关文章
相似问题
腾讯云开发者
