Изменения

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

====Почему алгоритм работает?====

Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.