इनपुट के रूप में एक पूर्णांक संख्या दी गई है। लक्ष्य इनपुट संख्या को 1 तक कम करने के लिए आवश्यक चरणों या संचालन की न्यूनतम संख्या का पता लगाना है। जो ऑपरेशन किए जा सकते हैं वे होंगे-:
-
यदि संख्या सम है, तो उसे 2 से भाग दें।
-
यदि संख्या विषम है, तो इसे 1 से बढ़ाएँ या घटाएँ।
उदाहरण
इनपुट - संख्या=28
आउटपुट − 28 से 1:6 तक कम करने के लिए न्यूनतम कदम
स्पष्टीकरण -
28 सम है - 2 =14 से भाग दें
14 सम है - 2 =7 से भाग दें
7 विषम है - 1 =8 से वृद्धि
8 सम है - 2 =4 से भाग दें
4 सम है - 2 =2 से भाग दें
2 सम है - 2 =1 से भाग दें
इनपुट - संख्या=9
आउटपुट − 9 से 1:4 तक कम करने के लिए न्यूनतम कदम
स्पष्टीकरण -
9 विषम है - 1 =8 से कमी
8 सम है - 2 =4 से भाग दें
4 सम है - 2 =2 से भाग दें
2 सम है - 2 =1 से भाग दें
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में संख्या को 1 तक कम करने के लिए आवश्यक न्यूनतम संचालन की जांच के लिए एक पुनरावर्ती दृष्टिकोण का उपयोग करें। यदि इसे केवल 2 से विभाजित किया जाता है तो संख्या + 1 या संख्या -1 के न्यूनतम तरीकों के लिए पुनरावर्ती रूप से जांच करें, जो भी कम हो।
-
इनपुट नंबर को पूर्णांक के रूप में लें।
-
फ़ंक्शन minWays(int num) इनपुट के रूप में num लेता है और num को 1 तक कम करने के लिए आवश्यक न्यूनतम संचालन की गिनती देता है।
-
चर tmp1, tmp2 और min को पूर्णांकों के रूप में लें।
-
अगर संख्या 0 है तो वापस आएं 1.
-
अगर num%2==0 तो यह सम है तो सेट करें num=num/2
-
यदि संख्या विषम है तो tmp1=minWays(num-1) और tmp2=minWays(num+1) सेट करें।
-
न्यूनतम सेट न्यूनतम tmp1 और tmp2 है।
-
वापसी 1+मिनट।
-
अंत में हमें मनचाहा परिणाम मिलेगा।
-
मुख्य में परिणाम प्रिंट करें।
उदाहरण
#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