स्वैपिंग से अधिकतम संख्या

इस समस्या में, एक पॉजिटिव इंटीजर स्ट्रिंग दी गई है, हमें उस परम्यूटेशन को ढूंढना है जिसका मान k बार अंकों को स्वैप करके, अलग-अलग स्थानों पर अधिकतम हो।

हम एक अंक चुनकर और उसे उसके बाद के अंकों के साथ एक-एक करके स्वैप करके अधिकतम संख्या ढूंढकर इस समस्या को हल करेंगे। हम इस प्रक्रिया को k बार दोहराते हैं। बैकट्रैकिंग रणनीति यहां काम कर रही है क्योंकि जब हमें कोई संख्या मिलती है जो पिछले मान से अधिक नहीं होती, तो हम पुराने मान पर वापस जाते हैं और फिर से जांचते हैं।

इनपुट और आउटपुट

इनपुट: कई अंकों की एक संख्या। इनपुट है: 129814999 आउटपुट: इन अंकों को स्वैप करके अधिकतम मान। आउटपुट है: 999984211

एल्गोरिदम

maxNum(number, swaps, maxNumber)

इनपुट - स्ट्रिंग के रूप में संख्या, स्वैप की संख्या और maxNumber स्ट्रिंग

आउटपुट - सबसे बड़ा मान प्राप्त करने के लिए maxNumber को अपडेट करें

Begin 
  if swaps = 0, then 
    return 
  n := number of digits in the number 
  for i := 0 to n-2, do 
    for j := i+1 to n-1, do 
      if number[i] < number[j], then 
        exchange number[i] and number[j] 
        if number is greater than maxNumber, then 
          maxNumber := number 
        maxNum(number, swaps-1, maxNumber) 
        exchange number[i] and number[j] again for backtrack 
    done 
  done 
End

उदाहरण

#include  using namespace std; void maxNum(string str, int swaps, string &max) { if(swaps == 0) //when no swaps are left return; int n = str.length(); for (int i = 0; i < n - 1; i++) { //for every digits og given number for (int j = i + 1; j < n; j++) { if (str[i] < str[j]) { //when ith number smaller than jth number swap(str[i], str[j]); if (str.compare(max) > 0) //when current number is greater, make it maximum max = str; maxNum(str, swaps - 1, max); //go for next swaps swap(str[i], str[j]); //when it fails, reverse the swapping } } } } int main() { string str = "129814999"; int swapNumber = 4; string max = str; maxNum(str, swapNumber, max); cout <<"The given number is: " <

आउटपुट
The given number is: 129814999 The maximum number is: 999984211