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

Krzywa Smoka

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!

C++C#
Python
LOGO
  1. def KrzywaSmokaNastepny(poprzedni = ""):
  2.   wynik = "1"
  3.   for i in range(len(poprzedni)):
  4.     wynik += poprzedni[i]
  5.     wynik += chr((i % 2) + 0x30);
  6.   return wynik

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:

C++C#
Python
LOGO
  1. k = int(input("Ile wyrazów wypisać?\n k = "))
  2. teraz = ""
  3. for i in range(k):
  4.   teraz = KrzywaSmokaNastepny(teraz)
  5.   print(teraz)