在这个问题中,给出了一个正整数字符串,我们必须通过将数字的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