Задача:
Найти последовательность из 50 нулей и единиц, в которой никакой отрезок не повторяется три раза подряд или установить,что такой последовательности не существует.
Решение:
Воспользуемся уже придуманной последовательностью Туэ-Морса (вики).
История:
Последовательность была открыта в 1851 году Пруэ (P. Prouhet), который нашёл ей применение в теории чисел, однако не описал исключительные свойства последовательности. И только в 1906 году Аксель Туэ при изучении комбинаторики открыл её заново.
Публикация работы Туэ в Германии прошла бесследно, и последовательность вновь открывает Марсон Морс (Marston Morse) в 1921 году, применив её в дифференциальной геометрии.
Последовательность открывалась независимо много раз: например гроссмейстер Макс Эйве открыл её применение в шахматах, показав, как играть бесконечно, не нарушая правил ничьи.
Для нашей задачи нужно, чтобы никакой отрезок в последовательности не повторялся 3 раза подряд, как написано ниже, последовательность Туэ-Морса подходит для этого:
Свойства:
- симметрия;
- в последовательности никогда не встречаются три одинаковых подряд идущих куска, то есть невозможно встретить AAA, где под A можно подразумевать любую конечную последовательностей нулей и единиц;
- фурье-преобразование последовательности имеет одинаковые максимумы на частотах 1/3 и 2/3.
- число, двоичной записью которого является последовательность Морса-Туэ, называется числом Пруэ-Туэ-Морса.
Алгоритм:
На каждом шаге будем инвертировать всю последовательность и прибавлять к существующей:
- если начинаем с 0:
- если начинаем с 1:
шаг 1: 0
шаг 2: 01
шаг 3: 0110
шаг 4: 01101001
шаг 5: 0110100110010110 и т.д.
шаг 1: 1
шаг 2: 10
шаг 3: 1001
шаг 4: 10010110
шаг 5: 1001011001101001 и т.д.
Программирование:
Для решения задачи будем использовать тип string. Сначала напишем функцию для инвертирования строки, т.е. в строке меняем 1 на 0, 0 на 1:
1 2 3 4 5 6 7 8 | string invert_string(string str) // входной параметр str типа строка (string) { short int dlina_str = str.size(); // помещаем в переменную dlina_str длину текущей строки // цикл for (short int i=0;i<dlina_str;i++) // от начала строки до конца проверяем каждую букву str[i] = (str[i] == '1') ? '0' : '1'; // если буква равна 1, то меняем на 0. Если буква 0, то на 1 return str; // возвращаем результат в виде инвертированной строки } |
Основная программа:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include "stdafx.h" #include <iostream> //подключается библиотека ввода/вывода #include <string> using namespace std; // подключается классы для работы с консолью cin и cout // строковая функция для инвертирования строки // входная строка 1010 // выходная строка 0101 string invert_string(string str) // входной параметр str типа строка (string) int main(int argc, char *argv[]) // начало главной программы { // cout << - выводим на экран символы cout << "Najti posledovatel'nost' iz 50 nulej i edinic, v kotoroj nikakoj otrezok ne povtorjaetsja tri raza podrjad ili ustanovit',chto takoj posledovatel'nosti ne suwestvuet" << endl; // endl новая строка на экране cout << "Nachat' posledovatel'nost' s nulja? (0/1)" << endl; short int na4_posl; cin >> na4_posl; // cin >> - вводим с клавиатуры числа char buf[2]; _itoa(na4_posl,buf,10); //переводим считанное с клавы число в строку string posl = (const char*)buf; // в переменной posl текущая последовательность (начинается либо с 1 либо с 0) cout << "Vyvesti na kazhdom shage dlinu i soderzhanie posledovatel'nosti: (y/n)" << endl; char otv; cin >> otv; while(posl.size()<50) // пока последовательность не превышает 50 знаков сделать: { if (otv == 'y' || otv == 'Y') // если пользователь ответил да на вопрос о распечатке на каждом шаге событий { cout << "dlina = " << posl.size() << endl; // вывести длину последовательности cout << posl << endl; // вывести саму последовательность system("PAUSE"); // вывести на экран паузу, после которой надо нажать enter } posl += invert_string(posl); // к текущей последовательности прибавляем текущую последовательность, только // инвертированную } cout << "Poluchivshajasja posledovatel'nost':" << endl; // после того, как длина последовательности болье 50 cout << posl << endl; // прекращаем цикл и выводим последовательность system("PAUSE"); // пауза return 0; // выход из программы } |