資料結構
網路
關係型資料庫管理系統 (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 次檢視
