Ответ

Следующие ошибки возникли при попытке отправки сообщения:
Предупреждение: в этой теме не было сообщений более 120 дней.
Возможно, будет лучше создать новую тему.
Обратите внимание: данное сообщение не будет отображаться, пока модератор не одобрит его.
Вложения и другие параметры
Вложения:
Перетащите файлы сюда или используйте кнопку для добавления файлов
Доступные типы файлов: doc, gif, jpg, mpg, pdf, png, txt, zip
Ограничения: максимум вложений в сообщении — 4 (4 осталось), максимальный размер всех файлов — 2 МБ, максимальный размер одного файла — 1 МБ
Обратите внимание: вложения не будут видны, пока модератор не одобрит их.
ALT+S — отправить
ALT+P — предварительный просмотр

Сообщения в этой теме

Автор Hellerick
 - 20 марта 2024, 14:26
Я банально перебрал варианты.

for halflength in range(1, 21):
    binaryformat = '{:0'+str(halflength)+'b}'
    combinations = set()
    for i in range(2**halflength):
        code = binaryformat.format(i)
        code = code+''.join(['1' if c=='0' else '0' for c in code])
        normalizedcode = min([code[j:]+code[:j] for j in range(len(code))])
        combinations |= {normalizedcode}
    combinations = sorted(list(combinations))
    print(f'Length {halflength}, combinations {len(combinations)}')
    #print(combinations)

ЦитироватьLength 1, combinations 1
Length 2, combinations 1
Length 3, combinations 2
Length 4, combinations 2
Length 5, combinations 4
Length 6, combinations 6
Length 7, combinations 10
Length 8, combinations 16
Length 9, combinations 30
Length 10, combinations 52
Length 11, combinations 94
Length 12, combinations 172
Length 13, combinations 316
Length 14, combinations 586
Length 15, combinations 1096
Length 16, combinations 2048
Length 17, combinations 3856
Length 18, combinations 7286
Length 19, combinations 13798
Length 20, combinations 26216
Автор Toman
 - 20 марта 2024, 13:57
Что касается самой формулировки задачки - то "двойной" код длиной 2n, состоящий из "ритмически одинаковых", просто побитово инвертированных половинок длины n, можно представить проще - как двоичный код длины n, где каждый разряд соответствует месту, где состояние сигнала меняется или не меняется (соотв. 1 или 0), тогда условие, что половины именно инвертированы, преобразуется в то, что в дифференциальном коде должно быть всегда нечётное число единиц.
Дальше нам надо по-прежнему собрать все возможные такие коды в кучки таких, которые переходят друг в друга при циклическом сдвиге, и пересчитать эти кучки - в чём и состоит суть задачи.
Автор Hellerick
 - 20 марта 2024, 12:09
Хорошее приближение дает формула a(n) = 2^n/(2*n).
Автор Hellerick
 - 20 марта 2024, 11:51
Как это теоритечески объясняется, я не уверен, но вообще вот эта последовательность: https://oeis.org/A000016/list

n    a(n)
0    1
1    1
2    1
3    2
4    2
5    4
6    6
7    10
8    16
9    30
10    52
11    94
12    172
13    316
14    586
15    1096
16    2048
17    3856
18    7286
19    13798
20    26216
21    49940
22    95326
23    182362
24    349536
25    671092
26    1290556
27    2485534
28    4793492
29    9256396
30    17895736
31    34636834
32    67108864
33    130150588
34    252645136
35    490853416
Автор Toman
 - 20 марта 2024, 04:03
Чисто практическая задачка. Информация о состоянии некого объекта передаётся при помощи двоичного кода (например, включением-выключением некоторого сигнала по границам некоторых периодов равной продолжительности, которую можно считать единичной). Код является периодическим и циклическим, т.е. постоянно повторяется, и начало/конец кодовой комбинации никак не обозначены, т.е. всё, что получается друг из друга циклической перестановкой, считается одним и тем же кодом. При этом длина кодового цикла заранее задана, и кроме того, задано, что цикл обязан состоять из двух половин, являющихся побитной инверсией друг друга.
Вопрос: как посчитать число различимых кодовых комбинаций для любой заданной длины половины цикла (натурального числа)?