Conway Sequence


Conway Sequence


Conway Sequence — седьмая по счету игра уровня сложности medium, основанная на свойствах последовательности Конвея (правильнее было бы назвать её look-and-say sequence). Последовательность рекурсивна, но в более широком понимании: предыдущая строка полностью характеризует текущую. Изучение последовательности Конвея приводит к занятным открытиям, включая так называемую космологическую теорему, но лучше меня об этом расскажет лично Джон Хортон Конвей. Но начиная с определенного номера получить новую строку становится непросто даже на бумаге. Авторы просят нас помочь математикам и составить программу, которая по заданным значениям выводит определенную строку последовательности.

Алгоритм вывода следующей строки уместно проиллюстрировать на примере:
Sequence seed: 3
Строка №1 имеет вид: «3»
В ней записана одна тройка.
Следовательно, строка №2 запишется как: «1 3».
В ней записаны одна единица и одна тройка
Следовательно, строка №3 выглядит так: «1 1 1 3».
В ней содержатся три единицы и одна тройка,
потому строка №4 имеет вид: «3 1 1 3» et cetera.

Входные данные:

  • [latex]R[/latex] — основание последовательности («sequence seed»)
  • [latex]L[/latex] — номер последней строки

Выходные данные:
Строка №[latex]L[/latex], все элементы которой разделены пробелами.

Код программы:

Алгоритм решения:

  1. Начать просмотр содержимого строки слева направо. Если подряд идут несколько одинаковых чисел, запомнить их количество.
  2. Если следующее число в строке отлично от предыдущего записать в новую строку количество повторов предыдущего числа и само это число.
  3. Если строка подошла к концу, дописать к новой строке количество повторений последнего элемента и сам этот элемент.
  4. Если номер полученной строки меньше [latex]L[/latex], повторить процедуру для новой строки.

Эффективность алгоритма:
Программа успешно проходит все данные тесты.

conway_result

Технические детали реализации:

  • Для удобства работы с строками произвольной длины использована библиотека vector, в частности функции .clear(), .push_back(), .size(), .swap()
  • Так как принципиальное значение имеют только три факта: значение текущего элемента последовательности, значение предыдущего и количество подряд идущих одинаковых элементов, стоящих за ним — достаточно завести три переменные типа int для их хранения.
  • На каждой итерации вектор [latex]next\_line[/latex] копируется в вектор [latex]current\_line[/latex] и очищается. Переменной [latex]previous[/latex] присваивается значение первого элемента вектора [latex]current\_line[/latex].

Related Images:

2 thoughts on “Conway Sequence

  1. Отлично! Зачёл.
    Не самая простая задачка!
    Нужно в начале попытаться описать правила построения последовательности. Как-то так:
    1. Начало: «1»
    2. Вижу одну (1) единицу (1). Код — «11»
    3. Вижу две (2) единицы (1) . Код — «21»
    4. Вижу одну (1) двойку (2) и одну (1) единицу (1). Код «1211»
    И т.д.

    • Добавил алгоритм построения следующей строки, спасибо.

Добавить комментарий