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

Question

我正在做一道题，说我们必须从一个数 n 到另一个数 m，步骤越少越好，其中每个“step”可以是 1) 加倍，或 2) 减一。自然的方法是构造一棵二叉树并运行 BFS，因为我们知道 n, m 的边界是 0 ≤ n, m ≤ 10⁴/em> 所以树不会变得那么大。然而，我遇到了一个非常简短的解决方案，并且不知道它为什么有效。它基本上是从 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 的下界为零，因此树在某种意义上变得更“有限”，但是这种修改后的减半方法直到你低于这个数字，然后加起来直到你达到它，看起来它不一定总是返回正确答案，但它确实如此。为什么，以及我如何从一开始就认识到这种方法？

Answer 1

您只有 2 个可用操作:

1. 双n
2. 从n中减去1

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

如果m是偶数，那么你可以通过将 n 加倍来得到它什么时候2*n = m .否则，您也必须减去 1(如果 2*n = m + 1 则您必须将 n 加倍，然后减去 1)。

如果加倍n降落在m之上太远那么你将不得不减去两倍于你在加倍之前使用减法的次数 n .

示例: n = 12和 m = 20 .
你可以加倍 n然后减去 4 次，如 12*2 -4 = 20 . - 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
}