Послідовність Морзе — Туе

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Послідовність Морзе - Туе)
Перейти до навігації Перейти до пошуку
Анімація демонструє генерацію послідовності Морсе-Туе.

В математиці, послідовністю Морсе-Туе, називають двійкову послідовність яка починається так:

0 1 10 1001 10010110 1001011001101001....

Замість символів 1 та 0 можна використати будь-яку іншу пару, логічна структура послідовності Морсе-Туе не залежить від символів що використовуються для її представлення.

Задання[ред. | ред. код]

Існує кілька способів задати послідовність Морсе-Туе:

Пряме задання[ред. | ред. код]

Щоб обчислити n-тий елемент , запишіть номер в двійковій формі. Якщо число одиниць в цьому двійковому записі непарне, тоді , якщо ж парне, то .

Рекурсивне задання[ред. | ред. код]

Послідовність можна задати так:

L-система[ред. | ред. код]

Послідовність Морсе-Туе - це вивід наступної системи Лінденмаєра:

  Змінні  0  1
  Константи  немає
  Аксіома      0
  Правила      (0 → 01), (1 → 10)

Конкатенація з результатом побітового "не"[ред. | ред. код]

Послідовність Морсе-Туе, у формі що дається вище як послідовність бітів, може описуватись рекурсивно з використанням оператора побітового заперечення.

Перший елемент - 0. Якщо перших елементів визначені, і формують послідовність , тоді наступні елементів є побітовим запереченням . Таким чином ми описали перших елементів, і продовжимо рекурсію для них.

Якщо розписати кілька перших кроків:

  1. Починаємо з нуля. Отримуємо 0
  2. Побітовим запереченням нуля є 1. Отримуємо 01
  3. Побітовим запереченням 01 є 10. Отримуємо 0110
  4. Побітовим запереченням 0110 є 1001. Отримуємо 01101001
  5. І так далі. Дивіться анімацію на початку статті.


Деякі властивості[ред. | ред. код]

Фрактали та черепашача графіка[ред. | ред. код]

Черепашача графіка - це крива, що генерується автоматом, який керується послідовністю команд.

Якщо елементи послідовності Морсе-Туе інтерпретувати так:

  • Якщо t(n) = 0, переміститись вперед на одиницю,
  • Якщо t(n) = 1, повернутись проти годинникової стрілки на кут π/3,

Крива яку отримуємо в результаті збігається до сніжинки Коха, фрактальної кривої нескінченної довжини, що міститься в скінченній площі. Це ілюструє фрактальну природу послідовності Морсе-Туе.

Посилання[ред. | ред. код]