20
правок
Изменения
→Алгоритм получения цепного кода для двоичного вектора
== Алгоритм получения цепного кода для двоичного вектора ==
Для получения цепного кода используется жадный алгоритм. Первое слово кода — слово, полностью состоящая состоящее из нулей. Образуя каждое следующее слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль. Повторяем, пока снова не вернемся к первому слову
====Почему алгоритм работает?====
Требуется доказать, что алгоритм не повторит 2 слова в коде до того, как закончит цикл и то, что он переберет все возможные варианты.
