Strona główna » Algorytmy » Artykuły » Krzywa Smoka
 

Krzywa Smoka

https://mattomatti.com/a0245

Wstęp

Krzywa Smoka to fraktal, który generuje się na podstawie ciągu zer i jedynek. Następnie wartości zero przydziela się skręt w lewo, a wartości jeden skręt w prawo. Pomiędzy skrętami należy narysować kreskę do przodu.

Definicja

Pierwszym wyrazem ciągu smoka jest 1. Każdy następny wyraz polega na wstawieniu na początku i końcu aktualnego wyrażenia oraz pomiędzy aktualnymi znakami naprzemian wartości 1 oraz 0. Wartości te można interpretować na różne sposoby.

Przykład

Pierwszy wyraz to 1. Następny uzyskujemy poprzez dopisanie pustych pozycji _ 1 _, a następnie wpisaniu w nie naprzemian 1 i 0. Wtedy okaże się, że drugi wyraz to 110. Budowana kolejnego wyrazu polega na tym samym, ale tym razem pojawią się puste pola wewnątrz aktualnego wyrazu _ 1 _ 1 _ 0 _. Ostatecznie trzeci wyraz to 1101100. Następne wyrazy buduje się w identyczny sposób.

Wizualizacja

Poniżej została przedstawiony fraktal wygenerowany na podstawie Krzywej Smoka. Przyciski służą do wygenerowania fraktalu na podstawie poprzedniego wyrazu ciągu, albo następnego. Uwaga: dla dużych wartości generowanie będzie trawło długo.

Poprzedni Wyraz Następny Wyraz

Implementacja

Do generowania KrzywaSmokaNastepny(), która na podstawie poprzedniego wyrazu zwróci kolejny wyraz. W przypadku braku podania argumentu (poprzedniego wyrazu) funkcja zwróci pierwszy wyraz ciągu smoka. Funkcja nie sprawdza poprawności podanego wyrażenia!

  1. string KrzywaSmokaNastepny(string poprzedni = "") {
  2.   string wynik = "1";
  3.   for (int i = 0; i < poprzedni.size(); i++) {
  4.     wynik += poprzedni[i];
  5.     wynik += (char)((i % 2) + '0');
  6.   }
  7.   return wynik;
  8. }

Niezależnie, który wyraz chcemy wyznaczyć to na początku stoi zawsze wartość 1. Następnie dla każdej wartości z poprzedniego wyrazu przepisywane są kolejne znaki, a pomiędzy nie wstawiana jest na przemian wartość 1 i 0. Do tego celu wykorzystana została funkcja modulo, która na podstawie numeru iteracji zwraca potrzebne wartości. Na koniec funkcja zwraca kolejny wyraz ciągu smoka.

Testowanie funkcji

Do przetestowania napisanej funkcji można skorzystać z poniższego fragmentu programu:

  1. int main () {
  2.   int k;
  3.   cout << "Ile wyrazow wypisac?\n k = ";
  4.   cin >> k;
  5.   string teraz = "";
  6.   for (int i = 0; i < k; i++) {
  7.     teraz = KrzywaSmokaNastepny(teraz);
  8.     cout << teraz << endl;
  9.   }
  10.   system("pause");
  11.   return 0;
  12. }