Задача №1 на последовательность ТуЭ-Морса

Задача:

Найти последовательность из 50 нулей и единиц, в которой никакой отрезок не повторяется три раза подряд или установить,что такой последовательности не существует.


Решение:

Воспользуемся уже придуманной последовательностью Туэ-Морса (вики).

  1. История
  2. Свойства
  3. Алгоритм
  4. Программирование
  5. Скриншоты
  6. Скачать

История:

Последовательность была открыта в 1851 году Пруэ (P. Prouhet), который нашёл ей применение в теории чисел, однако не описал исключительные свойства последовательности. И только в 1906 году Аксель Туэ при изучении комбинаторики открыл её заново.

Публикация работы Туэ в Германии прошла бесследно, и последовательность вновь открывает Марсон Морс (Marston Morse) в 1921 году, применив её в дифференциальной геометрии.

Последовательность открывалась независимо много раз: например гроссмейстер Макс Эйве открыл её применение в шахматах, показав, как играть бесконечно, не нарушая правил ничьи.

Для нашей задачи нужно, чтобы никакой отрезок в последовательности не повторялся 3 раза подряд, как написано ниже, последовательность Туэ-Морса подходит для этого:

Свойства:

  • симметрия;
  • в последовательности никогда не встречаются три одинаковых подряд идущих куска, то есть невозможно встретить AAA, где под A можно подразумевать любую конечную последовательностей нулей и единиц;
  • фурье-преобразование последовательности имеет одинаковые максимумы на частотах 1/3 и 2/3.
  • число, двоичной записью которого является последовательность Морса-Туэ, называется числом Пруэ-Туэ-Морса.

Алгоритм:

На каждом шаге будем инвертировать всю последовательность и прибавлять к существующей:

  1. если начинаем с 0:
  2. шаг 1: 0

    шаг 2: 01

    шаг 3: 0110

    шаг 4: 01101001

    шаг 5: 0110100110010110 и т.д.

  3. если начинаем с 1:
  4. шаг 1: 1

    шаг 2: 10

    шаг 3: 1001

    шаг 4: 10010110

    шаг 5: 1001011001101001 и т.д.

Программирование:

Для решения задачи будем использовать тип string. Сначала напишем функцию для инвертирования строки, т.е. в строке меняем 1 на 0, 0 на 1:

Основная программа:

Скриншоты работы программы:

Ссылки для скачивания:

Thue-Morse_Sequence.cpp

Thue-Morse_Sequence.rar

Оцените статью
В коробке инженера
Добавить комментарий

Нажимая на кнопку "Добавить комментарий", я даю согласие на обработку персональных данных и принимаю политику конфиденциальности