Ciąg Thue-Morse

Wstęp

Ciąg Thue-Morse to ciąg składających się z samych zer i jedynek. Powstaje on poprzez ciągłe dopisywanie 0 i 1 na podstawie wcześniej ustalonego fragmentu ciągu.

Definicja

Ciąg Thue-Morse to ciąg składający się początkowo z 0. W każdym następnym kroku dotychczasowy kod jest negowany zgodnie z algebrą Boole'a, a następnie dopisywany na końcu obecnie wyznaczonej części ciągu. Proces ten jest powtarzany w nieskończoność.

Pierwsze 64 wyrazy ciągu to: 0110100110010110100101100110100110010110011010010110100110010110..

Wyznaczanie

Rekurencyjne

Pierwszym wyrazem ciągu jest zawsze 0. W celu wyznaczenia następnego wyrazu dopisujemy zanegowaną część wyznaczonego ciągu. Oto kolejne etapy powstawanie ciągu:

W każdy kolejnym kroku należy wyznaczyć negację ciągu, a następnie dołączyć ją na koniec aktualnego ciągu i czynność tę powtórzyć. W teorii proces ten powinien trwać w nieskończoność, ale możliwe jest wcześniejsze zatrzymanie generowania ciągu.

Przez Zastępowanie

Przyglądając się dokładnie w jaki sposób zmienia się ciąg można zauważyć, że każde 0 zamienia się na parę 01, a z kolei każda 1 na 10. Umożliwia to generowanie ciągu w sposób, który nie wymaga stosowania negacji. Pierwszy etap jest trywialny, ponieważ 0 przechodzi na 01. Oto jak można generować ciąg dalej:

Proces ten oczywiście można kontynuować dalej.

Kwestie techniczne

Warto zauważyć, że ciąg po każdej kolejnym etapie jego rozszerzenia jest 2 razy dłuższy. Oznacza to, że do wygenerowanie n jego kolejnych wartości potrzeba zaledwie lg(n) powtórzeń. Z punktu widzenia implementacji na komputerze problemem będzie pomieszczenie wszystkich danych niż ich wyznaczenie, ponieważ złożoność czasowa jest relatywnie znikoma względem złożoności pamięciowej.

Ciekawostka

Co drugie wyznaczenie kolejnego fragmentu ciągu Thue-Morse jest palindromem. Patrząc kolejno są to następujące fragmenty: '0', '0110', '0110100110010110', ..

Zadanie

Napisz program, który wczyta od użytkownika ile pierwszych cyfr ciągu Thue-Morse ma zostać wypisanych, a następnie wypisz je na ekran. Przetestuj działanie programu.

Strategia

W celu uproszczenia zapisu dane będą przetrzymywane w postaci zmiennych typu int. Oczywiście nie jest to optymalna metoda, ponieważ cyfry 0 i 1 można przechowywać chociażby na pojedynczych bitach. Strategia wyznacznia polegałaby na sprawdzeniu ile zostało wyznaczonych liczb i uruchomić pętle dla tych wszystkich cyfr. Jeśli zostaną zamienione i dopisane wszystkie to proces powtarzamy.

Rozwiązanie

Poniższa funkcja generujCiag() przyjmuje jeden argument n i zwraca wygenerowany ciąg jako tablice liczb całkowitych.

1. int* generujCiag(int n) {
2.   int* tab = new int[n];
3.   tab[0] = 0;
4.   int limit = 1;
5.   int k = 0;
6.   for (int i = 1; i < n; i++) {
7.     if (i == limit) {
8.       limit *= 2;
9.       k = 0;
10.     }
11.     tab[i] = (tab[k++] + 1) % 2;
12.   }
13.   return tab;
14. }

(2.) Zainicjalizuj tablicę pod wynik i (3.) umieść na niej pierwszy wyraz. Następnie (4.) określ, że aktualnie jest jeden element i (5.) aktualnie ma zostać przepisany pierwszy element z listy. (6.) W pętli dopóki nie osiągniemy odpowiedniego rozmiaru: (7.) sprawdź czy jest jakiś element do przepisania z aktualnie wyznaczonego ciągu. Jeśli tak to (8.) zwiększ limit i (9.) wróć do przepisywania od początku. (11.) Niezależnie od warunku dopisz na odpowiednim miejscu następny element. Na koniec (13.) zwróć obliczoną tablicę danych.

Testowanie funkcji

Działanie funkcji można sprawdzić przy pomocy poniższego fragmentu kodu, który wczyta od użytkownika ile pierwszych cyfr ciągu ma zostać wypisanych.

1. int main () {
2.   int n;
3.   cout << "Ile wyrazow ciagu wypisac?\n n = ";
4.   cin >> n;
5.   int* tab = generujCiag(n);
6.   for (int i = 0; i < n; i++)
7.     cout << tab[i];
8.   delete tab;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Rozwiązanie

Zadania

Zadanie 1

Napisz funkcję generujCiag(), która wykorzystując metodę Wyznaczania Przez Zastępowanie obliczy n pierwszych wyrazów ciągu. Przetestuj działanie napiasnego programu. Wskazówka: nie trzeba zastępować cyfry, a można dostawić odpowiednią cyfrę.

• Kod źródłowy Zadanie 1