हमें एक संख्या N दी गई है। लक्ष्य संख्या को 1 तक कम करने के लिए आवश्यक चरणों की संख्या गिनना है निम्नलिखित नियमों का पालन करके -
यदि संख्या 2 की घात है, तो इसे आधा कर दें।
अन्यथा इसे N - (N से कम 2 की निकटतम घात) से कम करें।
चरण 1 के लिए, हम जांचेंगे कि N 2 की घात है या नहीं, यह जांचकर कि क्या ceil(log2(N)), floor(log2(N)) समान परिणाम लौटाते हैं। यदि हां तो N=N/2, ऑपरेशन की गिनती बढ़ाते हैं।
यदि चरण 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, 2 की घात नहीं है। चरण 2. N से कम 2 की निकटतम घात को N से घटाएं। N=20-16=4. काउंट=1. 4, 2 की घात है। चरण 1. N को आधा करें। N=4/2=2. काउंट=2. 2, 2 की घात है। चरण 1. N को आधा करें। N=2/2=1. काउंट=3. N 1 है कुल चरण काउंट=3।
इनपुट - N=32
आउटपुट - आवश्यक चरणों की संख्या: 5
व्याख्या - N=32
32, 2 की घात है। चरण 1. N को आधा करें। N=32/2=16. काउंट=1. 16, 2 की घात है। चरण 1. N को आधा करें। N=16/2=8. काउंट=2. 8, 2 की घात है। चरण 1. N को आधा करें। N=8/2=4. काउंट=3. 4, 2 की घात है। चरण 1. N को आधा करें। N=4/2=2. काउंट=4. 2, 2 की घात है। चरण 1. N को आधा करें। N=2/2=1. काउंट=5. N 1 है कुल चरण काउंट=5।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम एक पूर्णांक N लेते हैं पूर्णांक मान स्टोर करने के लिए।
फंक्शन stepCount(int n) N लेता है और इसे 1 तक कम करने के लिए आवश्यक चरणों की गिनती लौटाता है।
प्रारंभिक चरणों की गिनती को 0 के रूप में लेते हैं।
अब while(n!=1) दोनों चरण 1, और 2 को n के मान के अनुसार करते हैं।
यदि n 2 की घात है (ceil(log2(n))==floor(log2(n)) सही होगा), 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))) //यदि n 2 की घात है तो यह सही है{ n=n/2; //n को आधा करें count++; } else { int x=floor(log2(n)); //फ्लोर मान n=n-(pow(2,x)); //2^x, n से कम 2 की निकटतम घात है count++; } } return count; } int main(){ int N = 96; cout <<"N को 1 तक कम करने के लिए आवश्यक चरणों की संख्या: "<<stepCount(N); return 0; } आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
N को 1 तक कम करने के लिए आवश्यक चरणों की संख्या: 6
