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

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的下界为零，所以树在某种意义上变得更加“有限”，但是这种修改减半的方法直到你低于这个数字，然后加起来直到你达到它，似乎它不一定总是返回正确的答案，但确实如此。为什么，以及我如何从一开始就认识到这种方法？

标签： c++algorithmmathbinary-treebreadth-first-search

Answer 1

您只有 2 个可用的操作：

1. 双倍的n
2. 减去 1n

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

如果m是一个偶数，那么你可以通过加倍nwhen来获得它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类的值。换句话说，您想要达到...，而做到这一点的最短方法是达到诸如or之类的值。v = m/2v = (m+1)/2nvv'v' = v/2v' = (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
}