将步数减少到1的最小步数 [英] minimum number of steps to reduce number to 1

问题描述

给出任意数字n，并对n进行三个操作:

Given any number n, and three operations on n:

1. 添加1
2. 减去1
3. 如果数字是偶数除以2

我想找到上述操作的最小数目，以将n减少为1.我尝试了动态编程方法，也对BFS进行了修剪，但是n可能非常大(10 ^ 300)，我不知道该怎么做.使我的算法更快.贪婪方法(如果是偶数则除以2，如果是奇数则除以1)也无法得出最佳结果.是否存在其他解决方案?

I want to find the minimum number of the above operations to reduce n to 1. I have tried dynamic progamming approach, also BFS with pruning, but n can be very large (10^300) and I do not know how to make my algorithm faster. The greedy approach (divide by 2 if even and subtract 1 if odd) also does not give the optimal result. Is another solution exists?

推荐答案

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

There is a pattern which allows you to know the optimal next step in constant time. In fact, there can be cases where there are two equally optimal choices -- in that case one of them can be derived in constant time.

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

If you look at the binary representation of n, and its least significant bits, you can make some conclusions about which operation is leading to the solution. In short:

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

• if the least significant bit is zero, then divide by 2
• if n is 3, or the 2 least significant bits are 01, then subtract
• In all other cases: add.

如果最低有效位为零，则下一个操作应为2的除法.我们可以尝试2次加法，然后进行除法，但是可以通过两个步骤来实现相同的结果:除法和加法.同样减去2次.当然，我们可以忽略无用的后续添加&减去步数(反之亦然).因此，如果最后一位为0，则除法是必经之路.

If the least significant bit is zero, the next operation should be the division by 2. We could instead try 2 additions and then a division, but then that same result can be achieved in two steps: divide and add. Similarly with 2 subtractions. And of course, we can ignore the useless subsequent add & subtract steps (or vice versa). So if the final bit is 0, division is the way to go.

然后其余的3位模式类似于**1.有四个.让我们写a011来表示一个数字，该数字以位011结尾，并且具有一组前缀位，这些前缀位表示值 a :

Then the remaining 3-bit patterns are like **1. There are four of them. Let's write a011 to denote a number that ends with bits 011 and has a set of prefixed bits that would represent the value a:

• a001:加1将得到a010，之后应进行除法:a01:已执行2个步骤.我们现在不希望减去一个，因为这将导致a00，我们可以从开始就分两步得出(减1和除法).因此，我们再次相加并除以得到a1，并且出于相同的原因，我们再次重复该操作，得到:a+1.这花了6步，但得出的数字可以5步得出(减1，除3乘，加1)，所以很明显，我们不应该执行加法.减法总是更好.

• a001: adding one would give a010, after which a division should occur: a01: 2 steps taken. We would not want to subtract one now, because that would lead to a00, which we could have arrived at in two steps from the start (subtract 1 and divide). So again we add and divide to get a1, and for the same reason we repeat that again, giving: a+1. This took 6 steps, but leads to a number that could be arrived at in 5 steps (subtract 1, divide 3 times, add 1), so clearly, we should not perform the addition. Subtraction is always better.

a111:加法等于或好于减法.在4个步骤中，我们得到a+1.减法和除法将得到a11.与初始加法路径相比，现在加法效率低下，因此我们重复此减法/除法两次​​，并分6步获得a.如果a以0结尾，那么我们可以分5个步骤完成(加，除三遍，相减)，如果a以1结尾，那么偶数为4.所以加法总是更好的.

a111: addition is equal or better than subtraction. In 4 steps we get a+1. Subtraction and division would give a11. Adding now would be inefficient compared to the initial addition path, so we repeat this subtract/divide twice and get a in 6 steps. If a ends in 0, then we could have done this in 5 steps (add, divide three times, subtract), if a ends in a 1, then even in 4. So Addition is always better.

a101:减法和双除法导致分三个步骤产生a1.加法和除法得出a11.与减法路径相比，现在减法和除法效率低下，因此我们将加法和除法两次以分5步获得a+1.但是通过减法路径，我们可以分4个步骤来实现.所以减法总是更好.

a101: subtraction and double division leads to a1 in 3 steps. Addition and division leads to a11. To now subtract and divide would be inefficient, compared to the subtraction path, so we add and divide twice to get a+1 in 5 steps. But with the subtraction path, we could reach this in 4 steps. So subtraction is always better.

a011:加法和双除会导致a1.要获得a，还需要再执行2个步骤(5)，而要获得a+1:还需要再执行6个步骤.减法，除法，减法，双除法导致a(5)，要获得a+1，则需要再执行一步(6).因此加法至少与减法一样好.但是，有一种情况不容忽视:如果 a 为0，则减法路径将以2步的一半到达解的中点，而加法路径将以3步的形式到达.因此，加法总是导致求解，除非 n 为3时，然后应选择减法.

a011: addition and double division leads to a1. To get a would take 2 more steps (5), to get a+1: one more (6). Subtraction, division, subtraction, double division leads to a (5), to get a+1 would take one more step (6). So addition is at least as good as subtraction. There is however one case not to overlook: if a is 0, then the subtraction path reaches the solution half-way, in 2 steps, while the addition path takes 3 steps. So addition is always leading to the solution, except when n is 3: then subtraction should be chosen.

因此对于奇数，倒数第二位决定下一步(3除外).

So for odd numbers the second-last bit determines the next step (except for 3).

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

This leads to the following algorithm (Python), which needs one iteration for each step and should thus have O(logn) complexity:

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 上运行.

这里是一个版本，您可以在其中输入 n 的值，然后让代码段生成步数:

Here is a version where you can input a value for n and let the snippet produce the number of steps:

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/O
var 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 ¹⁶ 左右，因此对于较大的数字，结果将是错误的.请改用Python脚本以获得准确的结果.

Please be aware that the accuracy of JavaScript is limited to around 10¹⁶, so results will be wrong for bigger numbers. Use the Python script instead to get accurate results.

这篇关于将步数减少到1的最小步数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！