20
правок
Изменения
Нет описания правки
== Алгоритм получения цепного кода для двоичного вектора ==
Для получения цепного кода используется жадный алгоритм. Первон Первое слово кода — слово, полностью состоящая из нулей. Образуя каждое следующее слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль.Повторяем, пока снова не вернемся к первому слову
====Почему алгоритм работает?====
Требуется доказать, что алгоритм не повторит 2 слова в коде до того, как закончит цикл и то, что он переберет все возможные варианты.
Во-первых, в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление 0 или 1) уже были использованы.
Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
Во-вторых, мы не сможем снова вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Чтобы снова получить нулевую строкуДопустим, мы должны будем перебрать всё же получили слово из всех нулей раньше, чем перебрали все строкислова. Тогда разобьём слова, которые не попали в которых есть код на две группы: кончающиеся на 1и кончающиеся на 0.Докажем, тк мы по возможности добавляем именно что 2-й группы нет.Рассмотрим слово {хх..хх}0. Раз его нет в коде, то его конец {х..хх}0 встречается в коде не более одного раза, а следовательно слова {x..xx}00 тоже нет в коде. Так эту цепочку можно продолжить до слова 00..000 и прийти к противоречию.А раз 2-й группы нет, то не может быть и 1-й, так как если в коде есть слово, а кончающееся на 0 только , то мы не можем получить его, если такое число уже не былослова с таким же началом, но с единицей в конце.
