将步数减少到1的最小步数

将步数减少到1的最小步数

有一种模式可以让您了解恒定时间的最佳下一步。实际上，在某些情况下可能存在两个同样最佳的选择-在这种情况下，可以在恒定时间内得出其中一个。

如果查看 n 的二进制表示形式及其最低有效位，则可以得出有关哪种 *** 作导致解决方案的结论。简而言之：

• 如果最低有效位为零，则除以2
• 如果 n 为3，或2个最低有效位为01，则减去
• 在所有其他情况下：添加。

证明

如果最低有效位为零，则下一个 *** 作应为2的除法。我们可以尝试先进行2次加法再除法，但是可以通过两个步骤来实现相同的结果：除法和加法。同样减去2。当然，我们可以忽略无用的后续加减步骤（反之亦然）。因此，如果最后一位为0，则除法是必须的。

那么其余的3位模式就像

**1

。有四个。让我们来写

a011

一个数字，该数字以位结尾

011

并具有一组前缀位，这些位代表值 a ：

• a001

  ：添加一个将给出

  a010

  ，然后应该进行除法

  a01

  ：：进行了2个步骤。我们现在不想减去一个，因为这将导致

  a00

  ，我们从开始就可以分两步得出（减去1并除以）。因此，我们再次加和除以获得get

  a1

  ，并且出于相同的原因，我们再次重复该 *** 作，得到：

  a+1

  。这花了6步，但得出的数字可以5步得出（减1，除3乘，加1），所以很明显，我们不应该执行加法。减法总是更好。

• a111

  ：加法等于或好于减法。在4个步骤中，我们得到

  a+1

  。减法和除法会给

  a11

  。与初始加法路径相比，现在加法效率低下，因此我们将这种减法/除法重复两次，并分

  a

  6步进行。如果

  a

  以0结尾，那么我们可以分5个步骤完成（加，除三遍，减法），如果

  a

  以1结尾，那么偶数为4。所以加法始终更好。

• a101

  ：减法和双重除法导致

  a1

  3个步骤。加法和除法导致

  a11

  。与减法路径相比，现在减法和除法效率低下，因此我们将加法和除法两次以得到

  a+1

  5步。但是通过减法路径，我们可以分4个步骤来实现。所以减法总是更好。

• a011

  ：加法和双重除法导致

  a1

  。要获得

  a

  ，还需要再执行2步（5），而要获得

  a+1

  ：还需要再执行6个步骤。减法，除法，减法，双除法导致

  a

  （5），要得到则

  a+1

  需要再执行一步（6）。因此加法至少与减法一样好。但是，有一种情况不容忽视：如果 a 为0，则减法路径将以2步的一半到达解的中点，而加法路径则需要3步。因此，加法总是导致求解，除非当 n 为3时：然后应选择减法。

因此，对于奇数，倒数第二个位决定下一步（3除外）。

Python代码

这导致以下算法（Python），该算法每个步骤都需要迭代一次，因此应具有 O（logn） 复杂度：

def stepCount(n):    count = 0    while n > 1:        if n % 2 == 0:  # bitmask: *0 n = n // 2        elif n == 3 or n % 4 == 1: # bitmask: 01 n = n - 1        else:# bitmask: 11 n = n + 1        count += 1    return count

看到它在repl.it上运行。

Javascript片段

这是一个您可以输入 n 值并让代码段生成步骤数的版本：

function stepCount(n) {    var count = 0    while (n > 1) {        if (n % 2 == 0)     // bitmask: *0 n = n / 2        else if (n == 3 || n % 4 == 1) // bitmask: 01 n = n - 1        else     // bitmask: 11 n = n + 1        count += 1    }    return count}// I/Ovar input = document.getElementById('input')var output = document.getElementById('output')var calc = document.getElementById('calc')calc.onclick = function () {  var n = +input.value  if (n > 9007199254740991) { // 2^53-1    alert('Number too large for Javascript')  } else {    var res = stepCount(n)    output.textContent = res  }}<input id="input" value="123549811245"><button id="calc">Caluclate steps</button><br>Result: <span id="output"></span>

请注意，Javascript的精度限于10 16左右，因此对于较大的数字，结果将是错误的。请改用Python脚本以获得准确的结果。