C ++の特定のルールに従って、Nを1に減らすために必要なステップ数をカウントします。

• 数値が2の累乗の場合は、半分に減らします。

• それ以外の場合は、N-（Nよりも小さい2の最も近い累乗）に減らします。

ステップ1では、ceil（log2（N））、floor（log2（N））が同じ結果を返すかどうかを確認することにより、Nが2の累乗であるかどうかを確認します。はいの場合、N =N / 3、操作のカウントをインクリメントします。

ステップ1の結果が偽の場合、ステップ2を実行し、NからN未満の最も近い2の累乗を減算します。Nよりも小さい2の最も近い累乗は-

x =floor（log2（N））→Nが2の累乗でない場合、log2（N）は浮動小数点値を与え、floorはそれをN未満の最も近い整数に減らします。

ここで、N =N-pow（2、x）→pow（2、x）は、Nよりも2小さい最も近い累乗を与えます。Nを減らします。

例を挙げて理解しましょう。

入力 − n =20

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

説明 − n =20

20 is not power of 2. Step 2. Reduce nearest power of 2 less than N from N. N=20- 16=4. Count=1.
4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=2.
2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=3.
N is 1 total step count=3.

入力 − n =32

出力 必要なステップ数-5

説明 − n =32

32 is power of 2. Step 1. Reduce N to its half. N=32/2=16. Count=1.
16 is power of 2. Step 1. Reduce N to its half. N=16/2=8. Count=2.
8 is power of 2. Step 1. Reduce N to its half. N=8/2=4. Count=3.
4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=4.
2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=5.
N is 1 total step count=5.

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

• 整数値を格納するために整数Nを取ります。

• 関数stepCount（int n）はNを取り、それを1に減らすために必要なステップ数を返します。

• 最初の歩数を0とします。

• ここで、while（n！=1）は、nの値に従ってステップ1と2の両方を実行します。

• nが2の累乗である場合（ceil（log2（n））==floor（log2（n））はtrueになります）、nを半分に減らします。インクリメントカウント。

• 2の累乗でない場合は、nをpow（2、x）だけ減らします。ここで、xはfloor（log2（n））です。インクリメントカウント。

• ループが終了すると、カウントには実行された操作の数が含まれます。

• 希望する結果としてカウントを返します。

例

#include <iostream>
#include <math.h>
using namespace std;
// Function to return number of steps for reduction
int stepCount(int n){
   int count=0;
   while(n!=1){
      if(ceil(log2(n))==floor(log2(n))) //if n is power of 2 then this is true{
         n=n/2; //reduce n to half
         count++;
      } else {
         int x=floor(log2(n)); //floor value
         n=n-(pow(2,x)); //2^x is nearest power of 2 which is less than n
         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