Strona główna » Algorytmy » Artykuły » Sprawdź Kolejność
 

Sprawdź Kolejność

https://mattomatti.com/a0270

Cel

Napisz algorytm, który sprawdzi czy znaki w obu tekstach są w takiej samej kolejności. W przypadku, gdy znak występuje kilka razy traktujemy to jakby był tylko jeden znak. Użytkownik na wejście poda jedynie dwa wyrażenia tekstowe. Wynikiem powinna być wartość logiczna czy znaki są w tej samej kolejności.

Przykład

Przykładowo wyrażenia "aabc" i "abc" mają znaki w tej samej kolejności chociaż mają ich różną ilość. Dowolny znak powtórzony x ma tę samą kolejność co wyrażenie xxxx...xxxx. Z kolei wyrażenie abcd i abc nie mają znaków w tej samej kolejności, ponieważ w tym drugim przypadku brakuje litery d.

Implementacja

Do zaimplementowania takiego algorytmu należy posiadać dwa indeksy oraz miejsce do zapisania ostatnio przeglądanego znaku. Oto przykładowy algorytm CzyZgodnaKolejnosc(), który dla dwóch wyrażeń s1 oraz s2 zwraca czy znaki są w tej samej kolejności.

  1. bool CzyZgodnaKolejnosc(string s1, string s2) {
  2.   int i1 = 0;
  3.   int i2 = 0;
  4.   char znak = '\0';
  5.   while (true) {
  6.     while (i1 < s1.size() && s1[i1] == znak) {
  7.       i1++;
  8.     }
  9.     while (i2 < s2.size() && s2[i2] == znak) {
  10.       i2++;
  11.     }
  12.     if (i1 == s1.size() || i2 == s2.size()) {
  13.       break;
  14.     }
  15.     znak = s1[i1];
  16.     if (s1[i1] != s2[i2]) {
  17.       return false;
  18.     }
  19.   }
  20.   return i1 == s1.size() && i2 == s2.size();
  21. }

Na podstawie ostatnio zapamiętanego znaku indeksy są przesuwane dopóki znak się powtarza. Następnie sprawdzane jest czy, któreś wyrażeni się skończyły - jest to przypadek, gdy któreś z wyrażeń składa się z większej ilości znaków.

Testowanie funkcji

Funkcję można przestować przy pomocy poniższego fragmentu kodu:

  1. int main () {
  2.   string s1, s2;
  3.   cout << "Podaj pierwsze slowo: ";
  4.   cin >> s1;
  5.   cout << "Podaj drugie slowo: ";
  6.   cin >> s2;
  7.   bool wynik = CzyZgodnaKolejnosc(s1, s2);
  8.   cout << (wynik ? "Ta sama" : "Inna") << " kolejnosc";
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz program, który sprawdzi czy kolejność cyfr w liczbie jest identyczna. Przykładowo liczba 1123 ma tę samą kolejność co 123. W zadaniu nie wolno zamieniać liczby na tekst.