हमें एक संख्या N दी गई है। नियमों का पालन करके संख्या को 1 तक कम करने के लिए आवश्यक चरणों की संख्या गिनना लक्ष्य है -
-
यदि संख्या 2 की घात है, तो इसे घटाकर आधा कर दें।
-
अन्यथा इसे N-(2 की निकटतम शक्ति जो N से कम है) तक कम करें।
चरण 1 के लिए, हम जाँच करेंगे कि क्या N 2 की शक्ति है, यह जाँच कर कि क्या ceil(log2(N)), floor(log2(N)) समान परिणाम देता है। यदि हाँ तो N=N/3, ऑपरेशन की वृद्धि संख्या।
यदि चरण 1 का परिणाम गलत है, तो हम चरण 2 का प्रदर्शन करेंगे और N से 2 की निकटतम घात को N से घटाएंगे। N से 2 कम की निकटतम घात की गणना -
के रूप में की जाएगी।x=floor(log2(N)) → जब N 2 की शक्ति नहीं है, log2(N) फ्लोटिंग पॉइंट मान देता है, मंजिल इसे N से कम निकटतम पूर्णांक तक कम कर देता है।
अब N=N-pow(2,x) → pow(2,x) N से 2 कम की निकटतम शक्ति देगा। N को कम करें।
आइए उदाहरणों से समझते हैं।
इनपुट -एन=20
आउटपुट -:आवश्यक चरणों की संख्या -3
स्पष्टीकरण -एन=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.
इनपुट -एन=32
आउटपुट आवश्यक चरणों की संख्या - 5
स्पष्टीकरण -एन=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 लेते हैं।
-
फ़ंक्शन स्टेपकाउंट (int n) N लेता है और इसे कम करने के लिए आवश्यक चरणों की संख्या को 1 पर लौटाता है।
-
चरणों की प्रारंभिक गणना 0 के रूप में करें।
-
अब जबकि(n!=1) n के मान के अनुसार चरण 1, और 2 दोनों को निष्पादित करें।
-
यदि n 2 की शक्ति है ( ceil(log2(n))==floor(log2(n)) सत्य होगा), n को घटाकर आधा कर दें। वेतन वृद्धि की संख्या।
-
यदि 2 की शक्ति नहीं है तो n को pow(2,x) से कम करें जहां x मंजिल है (log2(n))। वेतन वृद्धि की संख्या।
-
जब लूप खत्म हो जाएगा तो गिनती में किए गए कार्यों की संख्या होगी।
-
वांछित परिणाम के रूप में वापसी गणना।
उदाहरण
#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