Strona główna » Algorytmy » Artykuły » Dodatkowy Znak
x
 

Dodatkowy Znak

https://mattomatti.com/a0229

Cel

Dany jest pewne wyrażenie złożone z małych liter alfabetu łacińskiego. Drugie wyrażenie jest złożone z tych samych liter co pierwsze, ale zawiera dodatkowy znak. Znajdź go i wypisz odpowiedź!

Przykład

Przykładowo ciąg "abc" i "abcd" różnią się literą "d". Oczywiście dodatkowy znak może wystąpić na dowolnej pozycji, a litery w każdym wyrażeniu są ustawione w sposób losowy. Przykładowo "rqywtew" oraz rqywetew". Tym razem obydwa wyrażenia różnią się o dodatkową literę "e".

Implementacja

Przez Sortowanie

Jeden ze sposobów na rozwiązanie tego problemu wykorzystuje sortowanie. Mianowicie, aby znaleźć dodatkowy znak wpierw sortujemy obydwa wyrażenia. Wtedy zagwarantowane jest to, że na któreś pozycji znaki będą różne, albo dodatkowy znak będzie znajdować się na końcu. Wykorzystując najlepsze możliwe sortowanie złożoność takiego rozwiązania to O(nlog(n)).

Oto przykładowy kod:

  1. char DodatkowyZnak(string s1, string s2) {
  2.   sort(s1.begin(), s1.end());
  3.   sort(s2.begin(), s2.end());
  4.   for (int i = 0; i < s1.length(); i++) {
  5.     if (s1[i] != s2[i]) {
  6.       return s2[i];
  7.     }
  8.   }
  9.   return s2[s2.length() - 1];
  10. }

Najpierw sortowane są wyrażenia, a potem w pętli wyszukiwana jest para różnych znaków. Jeśli jednak taka para się nie znajdzie to znaczy, że dodatkowy znak jest na końcu i należy go zwrócić.

Przez XOR

Optymalnym rozwiązaniem jest wykorzystnie operacji bitowej XOR. Mianowicie XOR dla dwóch takich samych wartości zwraca 0 i dodatkowo jest operacją przemienną tj. a XOR b = b XOR a itd. Jeśli zostanie obliczony XOR wszystkich znaków to na końcu zostanie dodatkowy znak. Wynika to z faktu, że wszystkie znaki prócz niego zostaną wyzerowane. Zaletą takiego rozwiązanie jest złożoność liniowa O(n) Oto kod szukający dodatkowego znaku wykorzystując operacje XOR:

  1. char DodatkowyZnak(string s1, string s2) {
  2.   char c = 0;
  3.   for (int i = 0; i < s1.length(); i++) {
  4.     c ^= s1[i];
  5.     c ^= s2[i];
  6.   }
  7.   return c ^ s2[s2.length() - 1];
  8. }

Początkowo szukany znak należy ustawić na 0, a potem obliczyć XOR wszystkich znaków. Wynik takiej sumy jest szukanym znakiem.

Testowanie funkcji

W celu przetestowania napisanych funkcji można posłużyć się fragmentem poniższego programu:

  1. int main() {
  2.   string s1, s2;
  3.   cout << "Podaj wyrazenie:" << endl;
  4.   getline(cin, s1);
  5.   cout << "Podaj wyrazenie i dodatkowy znak:" << endl;
  6.   getline(cin, s2);
  7.   char wynik = DodatkowyZnak(s1, s2);
  8.   cout << "Nadmiarowy znak to: " << wynik;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz program, który znajdzie dodatkowy znak wykorzystując operacje arytmetyczne tj. dodawanie i odejmowanie. Wskazówka: różnica sumy znaków jednego oraz drugiego znaku wynosi dokładnie tyle co dodatkowy znak.