我一直在研究Hackerearth问题。这是问题陈述： 我们有三个变量a，b和c。我们需要将a转换为b并允许以下操作： 1.可减1。 2.可减2。 3.可以乘以c。 将a转换为b所需的最小步骤。 这是我提出的算法： 递增计数为0。 循环直到a === b： 1.执行（x = a * c），（y = a-1）和（z = a-2）。 2.在x，y和z中，选择与b的绝对差值最小的那个。 3.将a的值更新为x，y和z中选择的值。 4.将计数增加1。 我可以通过基本的测试用例，但我所有的先遣案例都失败了。我想我的逻辑是正确的，但由于复杂性似乎失败了。 有人可以建议更优化的解决方案。 编辑1 示例代码
function findMinStep(arr) {
let a = parseInt(arr[0]);
let b = parseInt(arr[1]);
let c = parseInt(arr[2]);
let numOfSteps = 0;
while(a !== b) {
let multiply = Math.abs(b - (a * c));
let decrement = Math.abs(b - (a - 1));
let doubleDecrement = Math.abs(b - (a - 2));
let abs = Math.min(multiply, decrement, doubleDecrement);
if(abs === multiply) a = a * c;
else if(abs === decrement) a -= 1;
else a -= 2;
numOfSteps += 1;
}
return numOfSteps.toString()
}
样本输入：a = 3，b = 10，c = 2 说明：将3乘以2得到6，从6减去1得到5，将5与2相乘得到10。 标记Python和JS的原因：两者兼容，但我不是在寻找代码，只是优化算法和分析思维。 编辑2：
function findMinStep(arr) {
let a = parseInt(arr[0]);
let b = parseInt(arr[1]);
let c = parseInt(arr[2]);
let depth = 0;
let queue = [a, 'flag'];
if(a === b ) return 0
if(a > b) {
let output = Math.floor((a - b) / 2);
if((a - b) % 2) return output + 1;
return output
}
while(true) {
let current = queue.shift();
if(current === 'flag') {
depth += 1;
queue.push('flag');
continue;
}
let multiple = current * c;
let decrement = current - 1;
let doubleDecrement = current -2;
if (multiple !== b) queue.push(multiple);
else return depth + 1
if (decrement !== b) queue.push(decrement);
else return depth + 1
if (doubleDecrement !== b) queue.push(doubleDecrement);
else return depth + 1
}
}
还有一段时间。还有什么建议吗？ Link为您提供的问题参考。
贪婪的方法在这里不起作用。
但它已经走上正轨。考虑图G，其中每个节点表示一个值，每个边表示一个操作并连接由该操作相关的两个值（例如：4和3通过“减1”连接）。使用此图表，我们可以轻松执行BFS-search以找到最短路径：
def a_to_b(a, b, c):
visited = set()
state = {a}
depth = 0
while b not in state:
visited |= state
state = {v - 1 for v in state if v - 1 not in visited} | \
{v - 2 for v in state if v - 2 not in visited} | \
{v * c for v in state if v * c not in visited}
depth += 1
return 1
该查询系统地测试所有可能的操作组合，直到通过逐步测试到达b。即生成可以通过a中的单个操作到达的所有值，然后测试可以通过两个操作等达到的所有值，直到b是生成的值中。
（假设c >= 0，但可以推广）
到目前为止，标准方法很少用于分析。该方法的优点在于它适用于任何此类问题并且易于实现。然而，一旦数字增长，它的效率并不高，并且会很快达到它的极限。因此，我将展示一种深入分析问题的方法，并获得一个（远）更高性能的解决方案：
在第一步，这个答案将分析问题：
我们需要操作-->op，使a -->op b和-->op是一个序列
c首先，如果我们先减去然后再乘以会发生什么？
(a - x) * c = a * c - x * c
接下来会发生什么，如果我们先加倍然后减去？
a * c - x'
定位系统
嗯，这没有简化的转变。但是我们已经有了分析更复杂的操作链的基本部分。让我们看看当我们交替地进行减法和乘法时会发生什么：
(((a - x) * c - x') * c - x'') * c - x'''=
((a * c - x * c - x') * c - x'') * c - x''' =
(a * c^2 - x * c^2 - x' * c - x'') * c - x''' =
a * c^3 - x * c^3 - x' * c^2 - x'' * c - x'''
看起来很熟悉？我们距离在a基地b中定义positional system和c之间的差异只有一步之遥：
a * c^3 - x * c^3 - x' * c^2 - x'' * c - x''' = b
x * c^3 + x' * c^2 + x'' * c + x''' = a * c^3 - b
不幸的是，上述仍然不是我们所需要的。我们所能知道的是，等式的LHS将始终为>=0。一般来说，我们首先需要推导出适当的指数n（上例中为3），s.t。它是最小的，非负的和a * c^n - b >= 0。对于各个系数（x，x'，...）求解这一点，其中所有系数都是非负的是一个相当简单的任务。
我们可以从上面展示两件事：
a < b和a < 0，没有解决方案最优性证明
上面的第二个陈述可以通过对n的归纳来证明。
n = 0：在这种情况下a - b < c，所以只有一个-->op
n + 1：让d = a * c^(n + 1) - b。让d' = d - m * c^(n + 1)，选择m，使d'是最小的和非负的。每个诱导假设d'可以通过位置系统最佳地生成。留下恰好m * c^n的差异。通过低阶项比m / 2减法更有效地覆盖这种差异。
算法（TLDR部分）
将a * c^n - b视为数字基础c并尝试找到它的数字。最终的数字应该有n + 1数字，其中每个数字代表一定数量的减法。通过添加相减的值，多个减法由单个数字表示。例如。 5意味着-2 -2 -1。从最重要的数字到最不重要的数字，算法操作如下：
c并从下一个数字开始重复例如：
a = 3，b = 10，c = 2 选择n = 2 a * c ^ n - b = 3 * 4 - 10 = 2 二进制2是执行010步：3 - 0 = 3,3 * 2 = 6,6 - 1 = 5,5 * 2 = 10
要么
a = 2，b = 25，c = 6 选择n = 2 a * c ^ n - b = 47 47基地6是115 执行的步骤：2 - 1 = 1,1 * 6 = 6,6 - 1 = 5,5 * 6 = 30,30 - 2 - 2 - 1 = 25
在python中：
def a_to_b(a, b, c):
# calculate n
n = 0
pow_c = 1
while a * pow_c - b < 0:
n += 1
pow_c *= 1
# calculate coefficients
d = a * pow_c - b
coeff = []
for i in range(0, n + 1):
coeff.append(d // pow_c) # calculate x and append to terms
d %= pow_c # remainder after eliminating ith term
pow_c //= c
# sum up subtractions and multiplications as defined by the coefficients
return n + sum(c // 2 + c % 2 for c in coeff)