Maszyna Turinga

pytanie zadane 6 grudnia 2016 w Algorytmy przez Josi Nowicjusz (190 p.)

Jak za pomocą maszyny Turinga przesunąć cyklicznie w lewo znaki. Dla przykładu:

100111101 --> 001111011. Ma ktoś pomysł na algorytm do tego zadania?

2 odpowiedzi

odpowiedź 6 grudnia 2016 przez CzikaCarry Szeryf (75,340 p.)

No to możesz zapisać to jako tablicę charów o rozmiarze 1 większym niż długość liczby, z pierwszego elementu tablicy wyjąć cyfrę, i wstawić do ostatniego, pustego elementu tablicy, a następnie wyświetlić tą tablicę.

komentarz 6 grudnia 2016 przez Josi Nowicjusz (190 p.)

Bardziej zależy mi na algorytmie. Potrzebuje go użyć do zapisu w maszynie Turinga.

komentarz 7 grudnia 2016 przez CzikaCarry Szeryf (75,340 p.)

No ale to co napisałem dla Ciebie to nie jest algorytm?

wyobraź sobie, że chcesz użyć algorytmu na takim przykładzie:

załóżmy, że każda przestrzeń oddzielona znakiem | jest komórką w tablicy charów.

Krok 1: zapisz liczbę do tablicy charów o wielkości o jeden większej od długości liczby:

|1|0|1|1|1|0|0| |

Krok drugi: przemieść pierwszą liczbę do ostatniego elementu tablicy:

|1|0|1|1|1|0|0|1|

W wyniku czego powstaje coś takiego:

| |0|1|1|1|0|0|1|

Teraz tylko wystarczy wyświetlić tą tablicę.

Jeśli sądzisz, że ktoś tu poda Ci gotowy kod, to jesteś w błędzie.

komentarz 7 grudnia 2016 przez Josi Nowicjusz (190 p.)

Oczywiście nie chciałem gotowego kodu, tylko pomysł jak to rozwiązać. Dzięki za odpowiedź!

odpowiedź 6 grudnia 2016 przez erx700 Gaduła (3,430 p.)

Począwszy od prawej strony wszystko przesunąć o jeden w lewo (to chyba proste), a następnie gdy się dojdzie do elementu pustego, cofnąć się do znaku i "pamiętając" w swoim stanie znak przesunąć znak na pierwsze pole. Tzn trzeba mieć osobną gałąź stanów do przesuwania jedynki na pierwsze pole i osobną gałąź stanów na przesuwanie zera.

komentarz 6 grudnia 2016 przez Josi Nowicjusz (190 p.)

Właśnie nie mam pomysłu jak ustawić ostatni znak na początek. Po przejściu przez cały ciąg znaków musiałbym wrócić na początek z zapamiętanym ostatnim znakiem. Pytanie, jak to zrobić?

komentarz 7 grudnia 2016 przez erx700 Gaduła (3,430 p.)

Po prostu musisz iść cały czas w prawo nic nie zmieniając, a na końcu wstawić znak zapamiętany w stanie. Kluczowe jest abyś zrozumiał koncepcje zapamiętywania w stanie. Jak już wcześniej tłumaczyłem musisz utworzyć specjalną gałąź stanów dla przenoszenia 1 i osobną gałąź dla przenoszenia 0. Fizycznie tych liczb nie masz zapamiętanych ale masz osobną gałąź dla ich przenoszenia.