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], все элементы которой разделены пробелами.

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

#include <iostream>
#include <vector>

using namespace std;
int main()
{
    int R; //первое число
    cin >> R; cin.ignore();
    int L; //номер целевой строки
    cin >> L; cin.ignore();

    vector<int>current_line (1, R); //вектор для хранения текущей строки
    vector<int> next_line; //вектор для хранения следующей строки
    int previous = R; //предыдущий элемент строки (необходим для сравнения)
    int counter = 0; //инициализация счетчика
    for(int step = 0; step < L - 1; step++)
    {
        int length = current_line.size(); //длина строки
        for(int i = 0; i < length; i++)
        {
            int current = current_line[i]; //текущее число
            if(current == previous) //если подряд идут одинаковые элементы
            {
                counter++; //посчитать их количество
                if(i + 1 == length) //для последнего элемента
                {
                    next_line.push_back(counter); //количество подряд идущих чисел
                    next_line.push_back(current); //число
                }
            }
            else
            {
                next_line.push_back(counter); //количество одинаковых подряд идущих чисел
                counter = 1; //сбросить счетчик
                next_line.push_back(previous); //число
                previous = current; //назначить текущее число в качестве предыдущего

                if(i + 1 == length) //для последнего элемента
                {
                    next_line.push_back(counter);
                    next_line.push_back(current);
                }
            }
        }
        current_line.clear(); //очистить текущую строку
        current_line.swap(next_line); //обменять значение векторов
        previous = current_line[0]; //назначить новый элемент для сравнения на старте
        counter = 0; //обнулить счетчик
    }

    int length =  current_line.size() - 1;
    for(int i = 0; length > i; i++) //вывести на экран элементы строки, разделенные пробелами
    {
            cout << current_line[i] << " ";
    }
    cout << current_line[length] << endl; //за последним символом не должно следовать пробела
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int R; //первое число

cin >> R; cin.ignore();

int L; //номер целевой строки

cin >> L; cin.ignore();

vector<int>current_line (1, R); //вектор для хранения текущей строки

vector<int> next_line; //вектор для хранения следующей строки

int previous = R; //предыдущий элемент строки (необходим для сравнения)

int counter = 0; //инициализация счетчика

for(int step = 0; step < L - 1; step++)

{

int length = current_line.size(); //длина строки

for(int i = 0; i < length; i++)

{

int current = current_line[i]; //текущее число

if(current == previous) //если подряд идут одинаковые элементы

{

counter++; //посчитать их количество

if(i + 1 == length) //для последнего элемента

{

next_line.push_back(counter); //количество подряд идущих чисел

next_line.push_back(current); //число

}

else

{

next_line.push_back(counter); //количество одинаковых подряд идущих чисел

counter = 1; //сбросить счетчик

next_line.push_back(previous); //число

previous = current; //назначить текущее число в качестве предыдущего

if(i + 1 == length) //для последнего элемента

{

next_line.push_back(counter);

next_line.push_back(current);

}

current_line.clear(); //очистить текущую строку

current_line.swap(next_line); //обменять значение векторов

previous = current_line[0]; //назначить новый элемент для сравнения на старте

counter = 0; //обнулить счетчик

}

int length = current_line.size() - 1;

for(int i = 0; length > i; i++) //вывести на экран элементы строки, разделенные пробелами

{

cout << current_line[i] << " ";

}

cout << current_line[length] << endl; //за последним символом не должно следовать пробела

}

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

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

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

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

Для удобства работы с строками произвольной длины использована библиотека 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”

Мазурок Игорь Евгеньевич says: 16/10/2014 at 00:14

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

Войдите, чтобы ответить
- Іванов Вячеслав Володимирович says: 16/10/2014 at 17:34
  
  Добавил алгоритм построения следующей строки, спасибо.