На главнуюКонтактыКарта сайта
В коробке инженера
В коробке инженера
Обзоры программ, интересных блогов и программирование
Заметки о Rastrwin, Matlab
  • Twitter Colee

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

Автор: colee | Рубрика: Алгоритмы
Вторник, 18 января 2011 г.
Теги: , Просмотров: 7085

Задача:

Найти последовательность из 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:

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;    // возвращаем результат в виде инвертированной строки
}

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

#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; // выход из программы
}

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

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

Thue-Morse_Sequence.cpp 1

Thue-Morse_Sequence.rar 0


Поделиться с друзьями:
twitter.com facebook.com vkontakte.ru odnoklassniki.ru mail.ru ya.ru digg.com blogger.com livejournal.ru google.com yandex.ru del.icio.us
Оставьте комментарий!

Используйте нормальные имена

Ваш E-mail не публикуется, используется для обратной связи и для выбора аватара с сайта gravatar.com

Публикуется вместе с комментарием

усмешка LOL сыр улыбка подмигнуть ухмылка глаза в сторону в тупике удивление большое удивление малинка пустое лицо сдвинутая бровь Оо гррр ох ох неудачник смущенный больной Тау хммм бешенный злой клевый поцелуй шок крутой недовольный

Запрещается оскорблять окружающих и использовать ненормативную лексику

Вы должны включить JavaScript, чтобы оставить сообщение