C++で数値を1に減らすための最小操作回数を求める方法

整数 Number が入力として与えられます。この問題の目的は、入力された数値を 1 に減らすまでに必要な最小のステップ数（操作回数）を求めることです。実行できる操作は以下の 2 種類です。

• Number が偶数の場合： 2 で割る
• Number が奇数の場合： 1 を足す、または 1 を引く

例

例 1

入力： Number = 28

出力： 28 を 1 に減らす最小ステップ数：6

説明：

• 28 は偶数 → 2 で割る = 14
• 14 は偶数 → 2 で割る = 7
• 7 は奇数 → 1 を足す = 8
• 8 は偶数 → 2 で割る = 4
• 4 は偶数 → 2 で割る = 2
• 2 は偶数 → 2 で割る = 1

例 2

入力： Number = 9

出力： 9 を 1 に減らす最小ステップ数：4

説明：

• 9 は奇数 → 1 を引く = 8
• 8 は偶数 → 2 で割る = 4
• 4 は偶数 → 2 で割る = 2
• 2 は偶数 → 2 で割る = 1

プログラムのアプローチ

このアプローチでは再帰を利用して、Number を 1 に減らすために必要な最小の操作回数を求めます。Number が偶数であれば単純に 2 で割り、奇数であれば「Number + 1」と「Number − 1」のそれぞれについて再帰的に最小回数を調べ、そのうち小さい方を採用します。

アルゴリズムの手順

1. 入力 Number を整数として受け取ります。
2. 関数 minWays(int num) は num を引数に取り、num を 1 に減らすのに必要な最小の操作回数を返します。
3. 変数 tmp1、tmp2、min を整数として用意します。
4. num が 1 であれば 0 を返します（これ以上の操作は不要なため）。
5. num % 2 == 0（偶数）の場合は、num = num / 2 として再帰的に計算します。
6. num が奇数の場合は、tmp1 = minWays(num − 1)、tmp2 = minWays(num + 1) を求めます。
7. min を tmp1 と tmp2 の小さい方に設定します。
8. 1 + min を返します。
9. 以上の手順により、最終的に目的の結果が得られます。
10. main 関数内で結果を出力します。

C++ 実装例

#include <iostream>
using namespace std;
int minWays(int num){
    int tmp1,tmp2,min;
    if (num == 1){
        return 0;
    }
    else if (num % 2 == 0){
        tmp1=minWays(num/2);
        return (1 + tmp1);
    }
    else{
        int tmp1=minWays(num - 1);
        int tmp2=minWays(num + 1);
        int min=tmp1<tmp2?tmp1:tmp2;
        return (1 + min);
    }
}
int main(){
    int Number = 21;
    cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
    return 0;
}

出力

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

Minimum steps to reduce 21 to 1: 6

まとめ

この記事では、偶数なら 2 で割り、奇数なら 1 を加減するという操作を繰り返して、整数を 1 に減らすための最小ステップ数を再帰的に求める方法を紹介しました。再帰を使うことでロジックをシンプルに記述でき、奇数の場合の 2 つの分岐（+1 と −1）それぞれの結果を比較することで、常に最適な操作を選択できます。計算量を抑えたい場合は、メモ化（動的計画法）を組み合わせることで、同じ数値に対する再計算を避け、さらに効率化することも可能です。