스왑에 의한 최대 수

이 문제에서 하나의 양의 정수 문자열이 주어졌을 때, 우리는 숫자를 'k번 교환하여 다른 위치로 값이 최대인 순열을 찾아야 합니다.

우리는 숫자를 선택하고 최대 숫자를 찾기 위해 한 번에 하나씩 뒤따르는 숫자로 바꿔 이 문제를 해결할 것입니다. 이 과정을 k번 반복합니다. 역추적 전략이 여기에서 작동하는 이유는 이전 값보다 크지 않은 숫자를 찾으면 이전 값으로 역추적하고 다시 확인하기 때문입니다.

입력 및 출력

Input:
A number of multiple digits.
The input is: 129814999
Output:
The maximum value from these digits by swapping them.
The output is: 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 <iostream>
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: " <<str << endl;
   cout <<"The maximum number is: "<< max << endl;
}

출력

The given number is: 129814999
The maximum number is: 999984211