Strona główna » Algorytmy » Artykuły » Podwójna Zamiana
 

Podwójna Zamiana

https://mattomatti.com/a0259

Zadanie

Zadanie polega na napisaniu algorytmu, który w podanym tekście podmieni pewien fragment na inny oraz wykona to w drugą stronę, ale nie będzie używać tymczasowej zawartości, aby uniknąć komfliktu. Przyjmujemy, że zamieniane fragmenty tekstu są tej samej długości.

Przykład

Weźmy przykładowo tekst "123412". Chcemy zamienić w nim fragment 12 na 34, a 34 na 12. Czyli ostatecznie chcemy osiągnąć "341234". Zadanie można rozwiązać wykonując kolejno trzy operacje zamiany na całym tekście tj. 12 na 00, potem 34 na 12, a potem 00 na 34. Oznaczałoby to, że kolejne przekształcenia zwracałyby: 123412 - 003400 - 001200 - 341234. Jest to poprawne podejście analogiczne do wymiany wartości dwóch zmiennych. W tym jednak zadaniu chcemy, aby algorytm TYLKO RAZ przejrzał cały tekst.

Uwaga

Podczas zamiany trzeba uwzględnić sytuację, gdy dany znak może zostać zastąpiony dwa razy. Przykładowo weźmy 12221, gdzie będziemy zastępować 12 przez 21. Pierwszy fragment występuje na początku 12221 - 21221. Po zamianie kolejna ramka również wychwytuje 12 do zamiany, ale 1 już raz została zamieniona, więc taka zamiana jest niepoprawna! Wynikiem końcowym powinno być 21212.

Implementacja

Oto przykładowy algorytm realizujący przedstawione wyżej zadanie:

  1. string PodwojnaZamiana(string tekst, string zam1, string zam2) {
  2.   int dl = zam1.length();
  3.   for (int i = 0; i < tekst.length() - dl + 1;) {
  4.     string fragment = tekst.substr(i, dl);
  5.     if (fragment == zam1) {
  6.       for (int j = 0; j < dl; j++) {
  7.         tekst[i + j] = zam2[j];
  8.       }
  9.       i += dl;
  10.     }
  11.     else if (fragment == zam2) {
  12.       for (int j = 0; j < dl; j++) {
  13.         tekst[i + j] = zam1[j];
  14.       }
  15.       i += dl;
  16.     } else {
  17.       i++;
  18.     }
  19.   }
  20.   return tekst;
  21. }

Algorytm przegląda kolejne litery tekstu. Jeśli od i-tej litery zaczyna się któryś z fragmentów to zastępuje tym drugim, a następnie zwiększa indeks i o długość zastępowanego fragmentu. Ma to na celu uniknięcie sytuacji, że dany znak zostanie zastąpiony dwukrotnie choć nie powinien.

Testowanie funkcji

Do przetestowania napisanych funkcji można skorzystać z poniższego fragmentu programu, który wczyta potrzebne wartości od użytkownika i wypisze wynik na konsole.

  1. int main() {
  2.   string tekst, zam1, zam2;
  3.   cout << "Podaj tekst: ";
  4.   getline(cin, tekst);
  5.   cout << "Podaj pierwszy zamieniany fragment: ";
  6.   cin >> zam1;
  7.   cout << "Podaj drugi zamieniany fragment: ";
  8.   cin >> zam2;
  9.   string wynik = PodwojnaZamiana(tekst, zam1, zam2);
  10.   cout << "Po zamianie: " << wynik;
  11.   system("pause");
  12.   return 0;
  13. }