algorithm - 使用给定规则将 x,y 从 1,1 更改为 p,q

Question

给定 a = p, b = q 在一个循环中，a 可以变为 a = a + b 或 b = b + a 在任何循环中，两者中的任何一个都可以执行，但不能同时执行。

从 a = 1 开始，b = 1

使用上述规则计算将 (x, y) 从 (1, 1) 转换为 (p,q) 所需的迭代次数。

如果无法完成，则无法退货

谁能告诉如何解决这个问题。

标签： algorithmdata-structures

Answer 1

正如评论中已经提到的，您可以倒退。较大的元素必须是执行计算的元素。所以你可以对较大的元素做相反的事情，看看你是否最终得到 (1, 1)。或者更好地直接从较大的元素中减去较小的元素，使其变得比另一个小：

function steps(a, b) {
  let count = 0
  while (a != b) {
    console.log('(' + a + ', ' + b + ')')
    let t
    if (a > b) {
      t = a % b == 0 ? a / b - 1 : Math.floor(a / b)
      a -= t * b 
    } else {
      t = b % a == 0 ? b / a - 1 : Math.floor(b / a)
      b -= t * a
    }
    count += t
  }
  if (a == 1)
    return count
  return -1
}

console.log(steps(87, 13))
console.log(steps(23, 69))