给我们一个数字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