数を1に減らすための最小手順数 質問する

定数時間で最適な次のステップを知ることができるパターンがあります。実際、2 つの最適な選択肢が存在する場合があります。その場合、そのうちの 1 つは定数時間で導き出されます。

バイナリ表現を見てみるとんとその最下位ビットから、どの演算が解を導くかについていくつかの結論を導き出すことができます。簡単に言うと、

• 最下位ビットがゼロの場合は2で割ります
• もしんが3、または最下位2ビットが01の場合、減算する
• それ以外の場合は追加します。

証拠

最下位ビットがゼロの場合、次の演算は 2 で割る必要があります。代わりに 2 回の加算と 1 回の除算を試すこともできますが、その場合、同じ結果は除算と加算の 2 つの手順で達成できます。2 回の減算でも同様です。もちろん、その後の無駄な加算と減算の手順は無視できます (またはその逆)。したがって、最終ビットが 0 の場合、除算が正しい方法です。

残りの3ビットパターンは のようになります**1。 4つあります。a011ビットで終わり011、値を表すプレフィックスビットのセットを持つ数値を表すために と書きましょう。1つの:

• a001: 1 を加えると になりa010、その後に割り算が行われる必要があります: a01: 2 ステップかかります。ここで 1 を引くのは避けたいところです。そうすると になりa00、これは最初から 2 ステップ (1 を引いて割る) で到達できたはずのものです。そこで、もう一度足して割ると になりa1、同じ理由でこれをもう一度繰り返すと になります。a+1これは 6 ステップかかりましたが、5 ステップ (1 を引いて、3 回割って、1 を足す) で到達できる数値になるので、明らかに加算を行うべきではありません。減算は常に優れています。

• a111: 加算は減算と同等かそれ以上です。4 ステップで が得られますa+1。減算と除算を行うと が得られますa11。ここで加算を行うと、最初の加算パスに比べて効率が悪くなるため、この減算/除算を 2 回繰り返してa6 ステップで を得ます。 がa0 で終わる場合は、これを 5 ステップ (加算、3 回の除算、減算) で実行できますが、 がa1 で終わる場合は 4 ステップでも実行できます。したがって、加算の方が常に優れています。

• a101: 減算と二重除算により、3 ステップで に到達しますa1。加算と除算により に到達しますa11。減算パスと比較すると、減算と除算は非効率的であるため、5 ステップで に到達するように 2 回加算して除算しますa+1。ただし、減算パスを使用すると、4 ステップでこれに到達できます。したがって、減算は常に優れています。

• a011: 加算と二重除算で になりますa1。 を得るにはaさらに 2 ステップ (5)、 を得るにはa+1さらに 1 ステップ (6) かかります。 減算、除算、減算、二重除算で (5) になりa、 を得るにはa+1さらに 1 ステップ (6) かかります。 つまり、加算は減算と同じくらい優れています。 ただし、見落としてはならないケースが 1 つあります。1つのが0の場合、減算パスは2ステップで解の途中まで到達しますが、加算パスは3ステップかかります。したがって、次の場合を除き、加算は常に解に至ります。ん3: 減算を選択する必要があります。

したがって、奇数の場合は、最後から 2 番目のビットによって次のステップが決まります (3 を除く)。

Python コード

これにより、次のアルゴリズム (Python) が生まれます。このアルゴリズムでは、各ステップで 1 回の反復が必要となり、反復回数は O(log��) になります。大きな整数に対する基本的な算術演算の複雑度が log�� であることを考慮すると、時間の複雑度は O(log²��) になります。

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

function stepCount(n) {
    var count = 0n;
    while (n > 1n) {
        if (n % 2n == 0) {                    // bitmask: *0
            n /= 2n;
        } else if (n == 3n || n % 4n == 1n) { // bitmask: 01
            n--;
        } else {                              // bitmask: 11
            n++;
        }
        count++;
    }
    return count;
}

// I/O
var input = document.getElementById('input');
var output = document.getElementById('output');
var calc = document.getElementById('calc');

calc.onclick = function () {
  var n = BigInt(input.value);
  var res = stepCount(n);
  output.textContent = res;
}

<input id="input" value="123549811245">
<button id="calc">Calculate steps</button><br>
Result: <span id="output"></span>