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.

C++C#
Python
  1. def CzyZgodnaKolejnosc(s1, s2):
  2.   i1 = 0
  3.   i2 = 0
  4.   znak = '\0'
  5.   while (True):
  6.     while (i1 < len(s1) and s1[i1] == znak):
  7.       i1 += 1
  8.     while (i2 < len(s2) and s2[i2] == znak):
  9.       i2 += 1
  10.     if (i1 == len(s1) or i2 == len(s2)):
  11.       break
  12.     znak = s1[i1]
  13.     if s1[i1] != s2[i2]:
  14.       return False
  15.   return i1 == len(s1) and i2 == len(s2)

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:

C++C#
Python
  1. s1 = input("Podaj pierwsze słowo: ")
  2. s2 = input("Podaj drugie słowo: ")
  3. wynik = CzyZgodnaKolejnosc(s1, s2)
  4. print(("Ta sama" if wynik else "Inna") + " kolejnosc");

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.