C++で特定のルールに従ってNを1に減らすために必要なステップ数をカウントする方法

整数 N が与えられます。この記事の目的は、以下のルールに従って数値を 1 に減らすために必要なステップ数をカウントすることです。

• 数値が 2 のべき乗である場合、その半分の値に減らします。
• それ以外の場合は、N から「N 未満で最も近い 2 のべき乗」を引いた値に減らします。

アルゴリズムの考え方

ステップ 1: まず、ceil(log2(N)) と floor(log2(N)) が同じ結果を返すかどうかを確認することで、N が 2 のべき乗かどうかを判定します。真であれば N = N / 2 とし、操作回数を 1 増やします。

ステップ 2: ステップ 1 の判定が偽であった場合、N から「N 未満で最も近い 2 のべき乗」を引きます。この値は次のように計算できます。

x = floor(log2(N)) → N が 2 のべき乗でない場合、log2(N) は浮動小数点値を返すため、floor 関数によってそれより小さい最も近い整数に丸められます。

N = N - pow(2, x) → pow(2, x) は「N 未満で最も近い 2 のべき乗」を表します。これを N から引くことで数値を減らします。

具体例で理解する

入力: N = 20

出力: 必要なステップ数 − 3

解説: N = 20 の場合

20 は 2 のべき乗ではありません。ステップ 2 を実行。N から N 未満で最も近い 2 のべき乗を引きます。N = 20 - 16 = 4。カウント = 1。
4 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 4 / 2 = 2。カウント = 2。
2 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 2 / 2 = 1。カウント = 3。
N が 1 になったので、合計ステップ数 = 3。

入力: N = 32

出力: 必要なステップ数 − 5

解説: N = 32 の場合

32 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 32 / 2 = 16。カウント = 1。
16 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 16 / 2 = 8。カウント = 2。
8 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 8 / 2 = 4。カウント = 3。
4 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 4 / 2 = 2。カウント = 4。
2 は 2 のべき乗です。ステップ 1 を実行。N を半分にします。N = 2 / 2 = 1。カウント = 5。
N が 1 になったので、合計ステップ数 = 5。

プログラムで使用するアプローチ

• 整数値を格納するための整数 N を受け取ります。
• 関数 stepCount(int n) は N を引数に取り、1 に減らすために必要なステップ数を返します。
• ステップ数の初期値を 0 に設定します。
• n != 1 の間ループを回し、n の値に応じてステップ 1 とステップ 2 を実行します。
• n が 2 のべき乗の場合(ceil(log2(n)) == floor(log2(n)) が真)、n を半分に減らし、カウントを 1 増やします。
• 2 のべき乗でない場合は、x = floor(log2(n)) を求め、n から pow(2, x) を引いてカウントを 1 増やします。
• ループが終了すると、count には実行された操作の合計回数が格納されています。
• 求めた結果として count を返します。

C++による実装例

#include <iostream>
#include <math.h>
using namespace std;
// 1 に減らすまでに必要なステップ数を返す関数
int stepCount(int n){
    int count=0;
    while(n!=1){
        if(ceil(log2(n))==floor(log2(n))) // n が 2 のべき乗の場合、この条件は真になる
        {
            n=n/2; // n を半分に減らす
            count++;
        } else {
            int x=floor(log2(n)); // floor 値を取得
            n=n-(pow(2,x)); // 2^x は n 未満で最も近い 2 のべき乗
            count++;
        }
    }
    return count;
}
int main(){
    int N = 96;
    cout <<"Count of steps required to reduce N to 1:"<<stepCount(N);
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Count of steps required to reduce N to 1:6

計算量について

このアルゴリズムでは、1 回のループごとに N の最上位ビットが取り除かれるか、値が半分になるため、ループの反復回数は最大でも log2(N) 回程度に収まります。したがって、全体の時間計算量は O(log N) となり、非常に効率的なアプローチです。補足として、浮動小数点演算を避けたい場合は、ビット操作(例えば n & (n-1) == 0 で 2 のべき乗判定)を利用する方法もあります。