Chúng tôi được cung cấp một số N. Mục tiêu là đếm số bước cần thiết để giảm số xuống 1 bằng cách tuân theo các quy tắc -
-
Nếu số là lũy thừa của 2, hãy giảm nó xuống một nửa.
-
Nếu không, hãy giảm nó đến N- (lũy thừa gần nhất của 2 nhỏ hơn N).
Đối với bước 1, chúng ta sẽ kiểm tra xem N có phải là lũy thừa của 2 hay không, bằng cách kiểm tra xem ceil (log2 (N)), tầng (log2 (N)) có trả về cùng một kết quả hay không. Nếu có thì N =N / 3, số lượng hoạt động tăng dần.
Nếu kết quả của bước 1 là sai thì chúng ta sẽ thực hiện bước 2 và trừ lũy thừa gần nhất của 2 nhỏ hơn N cho N. lũy thừa gần nhất của 2 nhỏ hơn N sẽ được tính là -
x =floor (log2 (N)) → khi N không phải là lũy thừa của 2, log2 (N) cho giá trị dấu phẩy động, tầng giảm nó thành số nguyên gần nhất nhỏ hơn N.
Bây giờ N =N-pow (2, x) → pow (2, x) sẽ cho công suất gần nhất nhỏ hơn N. Giảm N.
Hãy cùng hiểu với các ví dụ.
Đầu vào - N =20
Đầu ra -:Số bước bắt buộc - 3
Giải thích - 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.
Đầu vào - N =32
Đầu ra Số bước bắt buộc - 5
Giải thích - 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.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một số nguyên N để lưu trữ một giá trị số nguyên.
-
Hàm stepCount (int n) nhận N và trả về số bước cần thiết để giảm nó xuống còn 1.
-
Tính số bước ban đầu là 0.
-
Bây giờ while (n! =1) thực hiện cả hai bước 1 và 2 theo giá trị của n.
-
Nếu n là lũy thừa của 2 (ceil (log2 (n)) ==tầng (log2 (n)) sẽ đúng), hãy giảm n xuống còn một nửa. Số lượng tăng dần.
-
Nếu không phải là lũy thừa của 2 thì giảm n bởi pow (2, x) với x là tầng (log2 (n)). Số lượng tăng dần.
-
Khi vòng lặp kết thúc thì đếm sẽ có số hoạt động được thực hiện.
-
Số lượt trả về là kết quả mong muốn.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of steps required to reduce N to 1:6