C++で最小回数の操作によって数値mをnに変換する方法

このチュートリアルでは、指定された操作を最小回数だけ使って、ある数値 m を別の数値 n に変換するプログラムについて解説します。

2つの整数 m と n が与えられ、許可された操作のみを用いて整数 m を n へ変換するとき、その操作回数をできるだけ少なくすることを目指します。

許可される操作

• 与えられた数値に2を掛ける(×2)
• 与えられた数値から1を引く(−1)

アルゴリズムの考え方

この問題は、目標値 n の側から逆算的に考えると効率的に解けます。各ケースでの処理は次の通りです。

• m == n の場合: 変換は不要なので 0 を返します。
• m > n の場合: 掛け算は数を増やす方向にしか働かないため、あとは「−1」を繰り返すしかなく、答えは m − n 回となります。
• m ≤ 0 かつ n > 0 の場合: 0以下の数に×2や−1を繰り返しても正の数 n には到達できないため、変換不可能として −1 を返します。
• n が奇数の場合: 奇数は×2では作れないため、直前の操作は必ず「−1」とみなせます。よって 1 + convert(m, n + 1) を返します。
• n が偶数の場合: 直前の操作は「×2」とみなせるため、1 + convert(m, n / 2) を返します。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;

// 必要な最小の操作回数を求める関数
int convert(int m, int n){
    if (m == n)
        return 0;
    if (m > n)
        return m - n;
    // この状況では変換できない
    if (m <= 0 && n > 0)
        return -1;
    // n が大きく、かつ奇数の場合
    if (n % 2 == 1)
        // m に対して「-1」を行う
        return 1 + convert(m, n + 1);
    // n が偶数の場合
    else
        // m に対して「*2」を行う
        return 1 + convert(m, n / 2);
}

int main(){
    int m = 5, n = 11;
    cout << "Minimum number of operations : " << convert(m, n);
    return 0;
}

出力結果

Minimum number of operations : 5

処理の流れを確認

m = 5、n = 11 の場合、実際の変換手順は次のようになります。

1. 5 → 4(−1)
2. 4 → 3(−1)
3. 3 → 6(×2)
4. 6 → 12(×2)
5. 12 → 11(−1)

合計5回の操作で 5 を 11 に変換できており、これはプログラムの出力とも一致します。

計算量

このアルゴリズムは再帰のたびに n が半分になるか1増えるだけで進むため、再帰の深さはおおむね O(log n) 程度に収まり、非常に効率的に動作します。