C ++で特定の操作を実行して、数値を1に減らします。

入力として整数を指定します。目標は、入力数を1に減らすために必要な最小のステップ数または操作数を見つけることです。実行できる操作は次のとおりです-：

• 数値が偶数の場合は、2で割ります。

• Numberが奇数の場合は、1ずつインクリメントまたはデクリメントします。

例

入力 −番号=28

出力 − 28を1：6に減らすための最小ステップ

説明 −

28は偶数です-2で割る=14

14は偶数-2で割る=7

7は奇数です-1ずつインクリメント=8

8は偶数です-2で割る=4

4は偶数-2で割る=2

2は偶数です-2で割る=1

入力 −数値=9

出力 − 9を1：4に減らすための最小ステップ

説明 −

9は奇数です-1=8だけデクリメントします

8は偶数です-2で割る=4

4は偶数-2で割る=2

2は偶数です-2で割る=1

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、再帰的アプローチを使用して、Numberを1に減らすために必要な最小操作をチェックします。2で割るだけの場合は、Number +1またはNumber-1のどちらか少ない方の最小方法を再帰的にチェックします。

• 入力した数値を整数とします。

• 関数minWays（int num）は、入力としてnumを受け取り、numを1に減らすために必要な最小演算の数を返します。

• 変数tmp1、tmp2、minを整数とします。

• numが0の場合は、1を返します。

• num％2 ==0の場合は、num =num/2に設定されます

• numが奇数の場合は、tmp1 =minWays（num-1）およびtmp2 =minWays（num + 1）を設定します。

• 設定最小値は、tmp1とtmp2の最小値です。

• 1分以上戻る

• 最後に、目的の結果が得られます。

• 結果をメインに出力します。

例

#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