To tylko jedna z 2 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Opis algorytmu.
Program zaczyna z głowicą ustawioną na pierwszym znaku szukanego ciągu.
Pobieramy pierwszy znak i zapisujemy go o jeden wstecz.
Przewijamy do pierwszego znaku przeszukiwanego ciągu.
Jeżeli jest to ten sam znak to zamiast niego wstawiamy separator (głowica w prawo). W przeciwnym wypadku również wstawiamy separator, ale najpierw zapamiętujemy znak w stanie (głowica w prawo). Następnie sprawdzamy czy w obecnym miejscu znajduje się separator, jeżeli tak to kończymy program z rezultatem NIE, a w przeciwnym wypadku skaczemy do kroku 6.
Jeżeli w tym miejscu jest separator wracamy do początku i sprawdzamy czy sprawdzany znak było ostatnim z szukanego ciągu. W zależności o rezultatu sprawdzenia kończymy program TAK lub NIE.
Jeżeli znak to wracamy do początku i pobieramy następny znak przepisując go o jeden w lewo, a następnie idziemy do kroku 2.
Przewijamy do początku i sprawdzamy czy szukany znak był pierwszym z ciągu. Jeżeli tak to przepisujemy go na pierwotne miejsce i wracamy do kroku 1.
W przeciwnym wypadku wracamy do pierwszego znaku przeszukiwanego ciągu, następnie cofamy się o jeden i w miejsce separatora wpisujemy zapamiętany znak. Potem wracamy do początku, przepisujemy zapamiętywane znaki i skaczemy do kroku 1.
Napotkane problemy.
Głównym napotkanym przez nas problemem było zapamiętywanie kolejnych sprawdzanych znaków. Rozwiązaliśmy go zapisując znaki o jeden wstecz (oddzielając znaki już sprawdzane od jeszcze nie sprawdzonych). Wygląda to tak:
#abc#
#a#bc#
#ab#c#
I tak dalej, póki nie sprawdzimy wszystkich znaków. W przypadku, gdy któryś ze sprawdzanych znaków się nie zgadzał przepisujemy wszystkie zapamiętane znaki na pozycje pierwotne wracając tym samym do stanu pierwotnego.
Kolejnym problemem było sprawdzanie czy ciąg przeszukiwany lub szukany się skończył. Rozwiązanie go okazało się bardzo proste.
Ciąg przeszukiwany.
Po sprawdzeniu znaku przesuwamy głowicę w prawo i testujemy czy następny jest już separator, który oznaczałby koniec przeszukiwanego ciągu.
Ciąg szukany.
Wracając do początku po napotkaniu separatora (chodzi o separator rozdzielający ciąg szukany) przesuwamy się najpierw w lewo i sprawdzamy czy znajduje się tam separator. Jeżeli tak to znaczy, że ciąg szukany się skończył.
Najwięcej kłopotu sprawiła nam następująca sytuacja. Gdy sprawdziliśmy czy dany znak się zgadza i otrzymaliśmy negatywny wynik w miejsce testowanego znaku wstawialiśmy separator. Okazało się, że w przypadku, gdzie sprawdzany był inny niż pierwszy znak szukanego ciągu program dawał złą odpowiedź. Wynikało to z tego, że zamazany znak mógł być pierwszym znakiem. Najlepiej wyjaśnić to na przykładzie. Niech szukanym ciągiem będzie #abc#, a przeszukiwanym #dababch#. W pierwszym kroku nie ma żadnego problemu, bo otrzymujemy wynik negatywny. W drugim również, gdyż wynik jest pozytywny zatem sprawdzamy następny znak (b). Problem pojawia się, gdy chcemy sprawdzić znak trzeci (c). Wynik jest negatywny, więc zapisujemy # i wracamy do początku. Jak chcemy ponownie sprawdzić znak pierwszy (a) wynik otrzymujemy negatywny, gdyż sprawdzany ciąg wygląda tak: #####bch#. Można tu zaobserwować, że pierwszy znak ciągu został zamazany, przez co utraciliśmy możliwość uzyskania pozytywnego wyniku, mimo że ciąg ten znajduje się w szukanym.
(…)
…. Duży problem stanowi brak pamięci, przez co w celu zapamiętania każdego znaku trzeba tworzyć nowy stan.
…
... zobacz całą notatkę
Komentarze użytkowników (0)