遵循C ++中的某些规则，将N减少为1所需的步数

给我们一个数字N。目标是通过遵循以下规则来计算将数字减少为1所需的步骤数-

• 如果该数字为2的幂，则将其减小为一半。

• 否则将其减小到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)给出浮点值，下限将其减小为小于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;
//返回减少步数的功能
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 <<"将N减少为1所需的步骤数："<<stepCount(N);
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出-

将N减少为1所需的步骤数：6