एक पूर्णांक Number इनपुट के रूप में दिया गया है। लक्ष्य है इनपुट Number को 1 तक कम करने के लिए आवश्यक न्यूनतम चरणों या संक्रियाओं की संख्या ढूंढना। की जा सकने वाली संक्रियाएँ हैं-:
यदि Number सम है, तो इसे 2 से विभाजित करें।
यदि Number विषम है, तो इसे 1 से बढ़ाएं या घटाएं।
उदाहरण
इनपुट - Number=28
आउटपुट - 28 को 1 तक कम करने के लिए न्यूनतम चरण: 6
व्याख्या-
28 सम है - 2 से विभाजित करें = 14
14 सम है - 2 से विभाजित करें = 7
7 विषम है - 1 से बढ़ाएं = 8
8 सम है - 2 से विभाजित करें = 4
4 सम है - 2 से विभाजित करें = 2
2 सम है - 2 से विभाजित करें = 1
इनपुट - Number=9
आउटपुट - 9 को 1 तक कम करने के लिए न्यूनतम चरण: 4
व्याख्या -
9 विषम है - 1 से घटाएं = 8
8 सम है - 2 से विभाजित करें = 4
4 सम है - 2 से विभाजित करें = 2
2 सम है - 2 से विभाजित करें = 1
उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में Number को 1 तक कम करने के लिए आवश्यक न्यूनतम संक्रियाओं की जांच के लिए पुनरावर्ती दृष्टिकोण का उपयोग करें। यदि यह सम है तो बस 2 से विभाजित करें अन्यथा Number+1 या Number-1 के लिए न्यूनतम तरीकों की पुनरावर्ती जांच करें, जो भी कम हो।
इनपुट Number को पूर्णांक के रूप में लें।
फ़ंक्शन minWays(int num) num को इनपुट के रूप में लेता है और num को 1 तक कम करने के लिए आवश्यक न्यूनतम संक्रियाओं की गिनती लौटाता है।
पूर्णांक के रूप में tmp1, tmp2 और min वेरिएबल लें।
यदि num 1 है तो 0 लौटाएं।
यदि num%2==0 तो यह सम है तो num=num/2 सेट करें
यदि num विषम है तो tmp1=minWays(num-1) और tmp2=minWays(num+1) सेट करें।
min को tmp1 और tmp2 के न्यूनतम के रूप में सेट करें।
1+min लौटाएं।
अंत में हमें वांछित परिणाम मिलेगा।
main में परिणाम प्रिंट करें।
उदाहरण
#include <iostream> using namespace std; int minWays(int num){ int tmp1,tmp2,min; if (num == 1){ return 0; } else if (num % 2 == 0){ tmp1=minWays(num/2); return (1 + tmp1); } else{ int tmp1=minWays(num - 1); int tmp2=minWays(num + 1); int min=tmp1<tmp2?tmp1:tmp2; return (1 + min); } } int main(){ int Number = 21; cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number); return 0; } आउटपुट
उपरोक्त कोड चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:
Minimum steps to reduce 21 to 1: 6