仅使用两个操作遍历二叉树以从一个数字获取另一个数字

Question

我正在做一道题，说我们必须从一个数字 n 到另一个 m，在尽可能少的步骤，其中每个“步骤”可以是 1) 加倍，或 2) 减去一个。自然的方法是构造一个二叉树和运行 BFS，因为我们得到 n, m 受 0 ≤ n, m ≤ 10⁴ 所以树没有那么大。然而，我运行进入了一个非常简短的解决方案，并且不知道它为什么有效。它基本上从 m … n 相反，根据需要减半或增加一个以减少 m 直到它小于 n，然后相加得到 n。这是代码：

    while(n<m){
        if (m%2) m++;
        else m /= 2;
        count++;
    }

    count  = count  + n - m;
    return count;

为什么这是必然最短路径是否显而易见？我从 m … n 是自然的，因为 n 的下界为零，因此树在某种意义上变得更“有限”，但是这种修改减半直到你低于这个数字，然后加起来直到你达到它的方法，似乎并不一定应该总是return正确答案，但是确实如此。为什么，以及我如何从一开始就认识到这种方法？

Answer 1

您只有 2 个可用操作：

双倍n
从 n

这意味着上升的唯一方法是加倍，下降的唯一方法是减去 1。

如果m是偶数，那么当2*n = m时，你可以通过将n加倍来实现它。否则，您也必须减去 1（如果 2*n = m + 1 那么您将不得不加倍 n，然后减去 1）。

如果加倍 n 落在 m 之上太多，那么与加倍 n.

之前使用减法相比，你必须减去两倍的次数

示例： n = 12 和 m = 20。
您可以将 n 加倍，然后像 12*2 -4 = 20 那样减去 4 次。 - 5 个步骤
或者，您可以减去两次，然后将 n 加倍，如 (12-2)*2 = 20 中那样。 - 3 个步骤

您可能想知道“当 n < m/2 时，我应该如何选择加倍或减去 ？”。

我们的想法是使用基于递归的方法。您知道您希望 n 达到 v 的值，例如 v = m/2 或 v = (m+1)/2。换句话说，您希望 n 达到 v... 而最短的方法是达到 v' 的值，例如 v' = v/2 或 v' = (v+1)/2等等。

示例： n = 2 和 m = 21.
您希望 n 达到 (21+1)/2 = 11，这意味着您希望达到 (11+1)/2 = 6，从而达到 6/2=3，从而达到 (3+1)/2 = 2。
由于 n=2 你现在知道最短路径是：(((n*2-1)*2)*2-1)*2-1.

其他例子： n = 14 和 m = 22.
您希望 n 达到 22/2 = 11。
n 已经大于 11 所以最短路径是：(n-1-1-1)*2.

从这里可以看出，不用二叉树也可以推导出最短路径。最重要的是，您必须考虑从 m 开始，然后向下延伸到 n 的明显路径。这意味着编写从 m 到 n 的算法比相反的算法更容易。

使用递归，此函数实现相同的结果：

function shortest(n, m) {
    if (n >= m) return n-m; //only way to go down

    if(m%2==0) return 1 + shortest(n, m/2); //if m is even => optimum goal is m/2
    else       return 2 + shortest(n, (m+1)/2);//else optimum goal is (m+1)/2 which necessitates 2 operations
}

仅使用两个操作遍历二叉树以从一个数字获取另一个数字

Traversing a binary tree to get from one number to another using only two operations

c++

algorithm

math

binary-tree

breadth-first-search