Naiwne k Zamian Cyfr

Treść

Zadanie polega na zamienieniu miejscami cyfr liczby tak, aby była jak największa. Jedna zamiana to zamienienie pozycjami dwóch dowolnych cyfr na różnych pozycjach.. Jednak ograniczona została ilość zamian cyfr jakie można wykonać. Przyjmujemy, że liczba składa się z n cyfr i wykonujemy k operacji zamian.

Analiza problemu

Mając do dyspozycji n cyfr chcemy uzyskać jak największą wartość. Bez tego ograniczenia największa możliwa liczba byłaby wtedy, gdy cyfry zostałyby ustawione w porządku malejącym (a najmniejsza, gdy w rosnącym). Ten fakt należy wykorzystać, aby rozwiązać zadanie. Otóż każda kolejna zamiana musi postawić największy cyfry z przodu, a te najmniejsze zostawić na końcu liczby. Oczywiście należy pamiętać, że czasem liczba jest już największa możliwa.

Przykład

Weźmy przykładowo liczbę a = 1234. Największa liczba do uzyskania przy jednej zmianie (tj. k = 1) to 4231. Maksymalna liczba jest już możliwa do uzyskania w dwóćh zamianach k = 2 - będzie to oczywiście liczba 4321. Jednak nie zawsze zamiana każdej kolejnej liczby na największą jest najbardziej efektywna.

Dla liczby a = 971239 zamiana cyfry 7 oraz 9 nie da największej możliwej liczby do uzyskania jaką jest 979231. W takim przypadku najprościej będzie wykonać sprawdzenie wszystkich możliwości zamian. Taki algorytm nie będzie zbyt efektywny, ponieważ jego złożoność wynosi O(n²k).

Implementacja

Przedstawiony algorytm nie jest najszybszym algorytmem, ale jest w stanie znaleźć bezbłędnie najbardziej optymalne rozwiązanie przedstawionego problemu. Efektywność tego algorytmu wzrasta im mniej jest możliwych par do zamiany. Liczba a jest przechowywana jako tekst. Funkcja znajdzMaksimum() prócz liczby a jeszcze liczbę k - maksymalną ilość zamian.

1. string znajdzMaskimum(string a, int k) {
2.   string max = a;
3.   znajdzMaskimum_pom(a, k, max);
4.   return max;
5. }
7. void znajdzMaskimum_pom(string a, int k, string& max) {
8.   if (k == 0)
9.     return;
10.   for (int i = 0; i < a.length(); i++) {
11.     for (int j = i + 1; j < a.length(); j++) {
12.       if (a[i] < a[j]) {
13.         swap(a[i], a[j]);
14.         if (a.compare(max) > 0)
15.           max = a;
16.         znajdzMaskimum_pom(a, k - 1, max);
17.         swap(a[i], a[j]);
18.       }
19.     }
20.   }
21. }

(1.) Funkcja znajdzMaksimum() (2.) określa, że maksimum to początkowa wartosć a. Następnie (3.) rozpoczyna wyszukiwanie. Maksymalna wartość znaleziona będzie aktualizowana w zmiennej max.

(8. - 9.) Warunkiem stopu rekurencji jest to, że k wynosi 0. Można to odczytać jako brak dostępnych zamian. Do wybierania par (10. - 11.) potrzebne są dwie pętle. W celu ograniczenia wyborów poprzez wybór każdej pary tylko raz to indeks j należy do zakresu [i + 1, n], gdzie n to długość liczby a. (12.) Jesli zamiana cyfr jest możliwa to: (13.) dokonujemy jej, (14. - 15.) sprawdzy czy nie jest to nowe maksimum, (16.) na podstawie nowej wartości próbujemy dalej modyfikować liczbę, a na koniec (17.) należy wycofać zmiany.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniszego kodu, który wczytuje od użytkownika liczbę oraz ile jest możliwych kroków, a następnie wypisuje największą znalezioną liczbę.

1. int main () {
2.   string a; int k;
3.   cout << "Podaj liczbę kroków\n k = ";
4.   cin >> k;
5.   cout << "Podaj liczbę\n a = ";
6.   cin >> a;
7.   string b = znajdzMaskimum(a, k);
8.   cout << "Maksymalna wartosc to: " << b;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja