ДХ
У нас просто дана последовательность, сказано что здесь 2m символов, один из которых искривлённый. Нужно определить закон формирования линейной рекуррентной последовательности
Size: a a a
2020 November 30
ДХ
Если брать не искривлённую последовательность, а обычную правильную, то из первой половины регистром должна получиться вторая половина
ДХ
я из этой логики и делал 10 разных регистров, чтобы хоть где-то из первой половины вторую получить, но этого не произошло
ДХ
Вычисления такие получились
ДХ
где-то банально регистр просто не строился, потому что полином не получался
ДХ
вот пример правильной последовательности
ВВ
Если брать не искривлённую последовательность, а обычную правильную, то из первой половины регистром должна получиться вторая половина
Ну так я о том и говорю, что если для некоторой последовательности найти регистр, то он будет выдавать эту последовательность.
ВВ
Пусть последовательность из задачи — S. Мы предполагаем, что инвертирован 1-й бит. Инвертируем его и получаем последовательность S1. Для неё находим многочлен P1. Регистр с этим характеристическим многочленом будет выдавать последовательность S1. То есть, он будет выдавать S с отличием в одном бите. Разве нет?
ДХ
Я может не правильно понимаю, но в последовательности S1 вторая половина не должна получаться из первой?
ВВ
В смысле, если задать в качестве начального состояния первую половину, то он выдаст сперва её, а потом вторую? Да, должен.
ВВ
Это и будет значить, что мы нашли P1 для S1.
ВВ
Мне условие непонятно.
ДХ
Преподаватель говорил что решается перебором
ВВ
Мы можем получить P1, P2, P3, ... А какой из них — ответ на задачу?
ДХ
В смысле, если задать в качестве начального состояния первую половину, то он выдаст сперва её, а потом вторую? Да, должен.
ну а тут такое дело получается, что по итогу никакой регистр не выдаёт вторую половину
ДХ
может ошибка в условии, я уже не знаю что думать
ВВ
@insomniaJp Вот, кстати, калькулятор для алгоритма Берлекэмпа — Месси, чтоб на бумажке не считать: https://berlekamp-massey-algorithm.appspot.com/
ДХ
@insomniaJp Вот, кстати, калькулятор для алгоритма Берлекэмпа — Месси, чтоб на бумажке не считать: https://berlekamp-massey-algorithm.appspot.com/
вообще полиномы разные вышли
в методичке один, здесь другой
в методичке один, здесь другой
ДХ
Я попытался аналогичным образом сделать другой вариант - тоже ничего не вышло.
Скорее всего у меня неправильный подход к заданию)
Скорее всего у меня неправильный подход к заданию)
DK
Переслано от Dias Kasymzhan
https://informatics.mccme.ru/mod/statements/view.php?id=30501#1
Не смог решить задачу не правильно использую Ахо Корасик
HELP PLS
Не смог решить задачу не правильно использую Ахо Корасик
HELP PLS