Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Цепной код

Автор: Blacksnow 5.8.2004, 16:10

Есть идеи?
Решение через граф не предлагать.

Автор: Y-Vladimir 5.8.2004, 20:55

Поясни подробнее, что такое цепной код и почему тебе графы не подходят

Автор: Blacksnow 5.8.2004, 22:32

Перебор 0-1 векторов. Цепной код.
Строиться 0-1 вектор длины 2^n, затем все 0-1 вектора длины n получаються циклическим сдвигом из построенного. Пример для n=4:
0111101011001000
0011110101100100
0001111010110010
0000111101011001.
***
Потому что я знаю как он строиться с помощь графов.

Автор: Y-Vladimir 6.8.2004, 00:38

Что-то я не совсем понимаю, в чем здесь сложность?
А что, нельзя просто пройтись в цикле по вектору и циклически сдвинуть весь входной вектор на одну озицию вправо?
Нам ведь входной вектор дан и требуется только получить (2^n)-1 сдвигов, насколько я понял задачу.

Автор: Akina 6.8.2004, 08:47

Как идея:

Код

InitVector = '0111101011001000'
TempVector = InitVector & InitVector 
For i=1 to Length(InitVector)
   Vector[i] = Mid(TempVector, i, Length(InitVector))
Next i

или я чего не так понял?

Автор: Blacksnow 6.8.2004, 10:10

Задача состоит в том, чтобы построить вектор длины 2^n.

Цитата(Y @ 6.8.2004, 00:38)

Нам ведь входной вектор дан и требуется только получить (2^n)-1 сдвигов, насколько я понял задачу.

На вход даеться число n, т.е. надо перебрать все 0-1 вектора длины n. Для решения этой задачи строиться цепной код длины 2^n, потом он циклически сдвигаеться n раз.

Автор: Y-Vladimir 6.8.2004, 16:06

Цитата

На вход даеться число n, т.е. надо перебрать все 0-1 вектора длины n.

Т.е. как я понимаю, для n=3 нужно построить следующее:

000
001
010
011
100
101
110
111

Если так, то я не совсем понимаю, причем здесь цепной код, т.к. для построения этой последовательности существует много алгоритмов.

Автор: Blacksnow 6.8.2004, 16:19

Цитата(Y @ 6.8.2004, 16:06)

Если так, то я не совсем понимаю, причем здесь цепной код, т.к. для построения этой последовательности существует много алгоритмов.

Не так их и много.
***
Меня интересует именно этот алгоритм. Я же не просил способы перебора мне сказать.
***

Цитата(Y @ 6.8.2004, 16:06)

Т.е. как я понимаю, для n=3 нужно построить следующее:
000
001
010
011
100
101
110
111

Нет, надо построить 11101000.