数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用 C++ 计算将 N 缩减到 1 所需的步骤数
给定一个数字 N，目标是计算根据以下规则将该数字缩减到 1 所需的步骤数：
如果数字是 2 的幂，则将其减半。
否则，将其减去小于 N 的最接近的 2 的幂。
步骤 1：检查 N 是否为 2 的幂，方法是检查 ceil(log2(N)) 和 floor(log2(N)) 是否返回相同的结果。如果是，则 N=N/2，操作计数加 1。
如果步骤 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 -> 16 -> 8 -> 4 -> 2 -> 1)
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 -> 16 -> 8 -> 4 -> 2 -> 1)
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。
现在，当 (n!=1) 执行步骤 1 和 2，具体取决于 n 的值。
如果 n 是 2 的幂 (ceil(log2(n))==floor(log2(n)) 将为真)，则将 n 减半。计数加 1。
如果不是 2 的幂，则将 n 减去 pow(2,x)，其中 x 是 floor(log2(n))。计数加 1。
循环结束后，计数将包含已执行的操作数。
返回计数作为所需结果。
示例
#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
322 次查看
