Mój problem jest następujący: mam dużą sekwencję liczb. Wiem, że po pewnym czasie staje się okresowy - to znaczy, że na początku sekwencji są liczby k, a następnie jest ich więcej, które powtarzają się do końca sekwencji. Jako przykład, aby to wyjaśnić, sekwencja może wyglądać następująco: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ...], gdzie k wynosi 5 im wynosi 4, a powtarzający się blok to [2, 1, 1, 3]. Jak wynika z tego przykładu, mogę mieć powtarzające się bity wewnątrz większego bloku, więc nie pomaga po prostu szukać pierwszych przypadków powtarzania.

Nie wiem jednak, czym są k lub m - moim celem jest przyjęcie sekwencji [a_1, a_2, ..., a_n] jako wejścia i wyprowadzenie sekwencji [a_1, ..., a_k, [a_ (k +1), ..., a_ (k + m)]] - zasadniczo obcina dłuższą sekwencję, wymieniając jej większość jako powtarzający się blok.

Czy istnieje skuteczny sposób na rozwiązanie tego problemu? Ponadto, prawdopodobnie trudniejsze, ale bardziej idealne obliczeniowo - czy można to zrobić, gdy generuję daną sekwencję, tak że muszę wygenerować minimalną kwotę? Zajrzałem do innych, podobnych pytań na tej stronie, ale wszystkie wydają się radzić sobie z sekwencjami bez początkowego nie powtarzającego się bitu, a często bez konieczności martwienia się o wewnętrzne powtórzenie.

Jeśli to pomoże / byłoby użyteczne, mogę również wejść w to, dlaczego patrzę na to i do czego go użyję.

Dzięki!

EDYTOWANIE: Po pierwsze, powinienem był wspomnieć, że nie wiem, czy sekwencja wejściowa kończy się dokładnie na końcu powtarzanego bloku.

Rzeczywistym problemem, nad którym próbuję pracować, jest pisanie ładnego wyrażenia w zamkniętej formie dla ciągłych rozszerzeń frakcji (CFE) kwadratowych irracjonalnych (właściwie ujemnych CFE). Bardzo łatwo jest wygenerować częściowe ilorazy * dla tych CFE z jakimkolwiek stopniem dokładności - jednak w pewnym momencie ogon CFE dla kwadratowej irracjonalnej staje się powtarzającym się blokiem. Muszę pracować z częściowymi ilorazami w tym powtarzającym się bloku.

Moje obecne przemyślenia są następujące: być może uda mi się dostosować niektóre algorytmy sugerujące, że działają z prawa do pracy z jedną z tych sekwencji. Alternatywnie, być może jest coś w dowodzie, dlaczego kwadratowe irracjonalne są okresowe, co pomoże mi zrozumieć, dlaczego zaczynają się powtarzać, co pomoże mi wymyślić kilka łatwych kryteriów do sprawdzenia.

* Jeśli piszę dalszy rozwój frakcji jako [a_0, a_1, ...], odnoszę się do a_i jako częściowych ilorazów.

Niektóre informacje podstawowe można znaleźć tutaj dla zainteresowanych:http://en.wikipedia.org/wiki/Periodic_continued_fraction