同时使A和B平等的操作数量最少

Question

给定两个非负整数A和B，请找到最小数量的操作，以同时使它们同样。在一个操作中，您可以：

• 将A更改为2*A
• 或更改B为2*B
• 或将A和B更改为A-1，B-1

：A = 7，B = 25

操作序列将为：

1. 6 24
2. 12 24 24
3. 24 24

我们不能在少于3个操作中使它们相等

我们不能在一周前的测试中提出这个编码问题， 。无法想到一个解决方案，它被卡在我的头上。输入A和B略高于10^12，因此很明显，我不能使用循环否则会超过时间限制。

Answer 1

缓慢但有效的解决方案：

1. 如果它们相等，请停止。
2. 如果其中一个是0，则停止故障（如果不允许负数，则没有解决方案）。
3. 虽然两者都大于1，但两者都减少。
4. 现在较小的是1，另一个更大。
5. 虽然较小的二元表示较短，但较小。
6. 继续在步骤1。

在步骤4中，最大减少。在步骤5中，绝对差减小。因此，最终该算法终止。

Answer 2

这应该给出最佳解决方案。我们必须比较几种不同的方法并采用最佳解决方案。

1. 一种工作解决方案是将较小数量的数量加倍，因为它停留在较大数字以下（可能为零倍）。然后计算（可能多次）的双重差异较小的数字和较大的数字之间的差异。并减少数量多次。然后再将较小的时间加倍。 [如果数字从开始时相等，则解决方案是微不足道的。]这给出了步骤的上限。

2. 现在尝试以下优化：

2a）选择一个数字n在0到迄今为止最佳解决方案的步骤数之间。

2b）选择一个数字作为A，一个数字作为B（两个可能性）。

2C）现在计算以下过程的应用步骤。

3. 双n次。

4. 计算2（= m）的最小功率，使用b * 2^m＆gt; = a。 m至少应为1。

5. 。 1 ，它是左侧最不重要的右数字：1、3、7、15、31、63，...从所有可能的表示形式中，数字必须具有最小的十字架，例如7正确，021不。旁注：最少的校验和最多的数字为1，最多只有一个数字2，没有其他数字。 2的数字1的权利将是2的。）

6. 将数字表示为M数字，通过填充左位为零。如果数字不合适，请返回步骤2进行其他选择。

7. 从步骤6中获取最重要的未处理数字，并执行许多减少步骤。

8. 双b。

9. 重复7。使用下一个数字；如果不再剩下数字，则数字相等。

10. 如果步骤数小于到目前为止的最佳解决方案，请选择作为建议的解决方案。

11. 返回步骤2进行其他选择。

12. 从2中进行所有选择后，我们应该具有最低数量的最佳解决方案。

以下示例来自答案的较早版本，其中A始终是较大的数字和n = 0，因此我们仅测试一个选择。

示例17和65

Power of 2: 2^2=4; 4x17=68
Difference: 68-65=3
3 = 010=10 in base 7/3/1

Start => 17/65
Decrease. Double. => 32/64
Double. => 64/64

示例18和67

Power of 2: 2^2=4; 4x18=72
Difference: 72-67=5
5 = 012=12 in base 7/3/1

Start => 18/67
Decrease. Double. => 34/66
Decrease. Decrease. Double. => 64/64

示例10和137

Power of 2: 2^4=16; 16*10=160
Difference: 160-137=23
23 = 1101 in base 15/7/3/1

Start => 10/137
Decrease. Double. => 18/136
Decrease. Double. => 34/135
Double. => 68/135
Decrease. Double. => 134/134

Answer 3

这是一个广度优先的搜索，确实返回正确的答案，但可能不是找到它的最佳方法。也许它可以帮助他人检测模式。
Javasscript代码：

function f(a, b) {
  const q = [[a, b, [a, b]]];
  
  while (true){
    const [x, y, path] = q.shift();
    if (x == y) {
      return path;
    }
    if (x > 0 && y > 0) {
      q.push([x-1, y-1, path.concat([x-1, y-1])]);
    }
    q.push([2*x, y, path.concat([2*x, y])]);
    q.push([x, 2*y, path.concat([x, 2*y])]);
  }
  
  return [];
}

function showPath(path) {
  let out1 = "";
  let out2 = "";
  for (let i = 0; i < path.length; i += 2) {
    const s1 = path[i].toString(2);
    const s2 = path[i+1].toString(2);
    const len = Math.max(s1.length, s2.length);
    out1 += s1.padStart(len, "0");
    out2 += s2.padStart(len, "0");
    if (i < path.length - 2) {
      out1 += " --> ";
      out2 += " --> ";
    }
  }
  console.log(out1);
  console.log(out2);
}

showPath(f(89, 7));