тут же изобретается какая-то своя терминология, за которой непонятно как следить
Да, но эта терминология здесь опирается на идеи и действия, которые мы реализуем. Я понимаю, что в математике важен формализм, но точные формулировки усложняют именно восприятие идеи, но зато не имеют иных трактовок. А как мне кажется Хабр - портал с публицистической напрвленностью, в котором эту проблему можно решать с помощью диалога или комментариев для конкретизации того, что хочет донести автор. Надеюсь примерами и обсуждением мы добьемся понимания темы)
Совершенно неочевидно как делить произвольное число на эти запчасти.
Поймали) - я не описал нормально правило формирования таких слов-блоков. И стоит начать с источника проблем:
Блок чередующихся нулей и единиц, длиной k (c_k)
Здесь стоит сказать, что для нас интересно чередование вида 01 = С, так как при умножении на 3, 01 превращается в 11 (если с прошлых разрядов не пришла единица) или 00 (если она пришла). С примером 101(5) не С2 (особенно если перед стоит блок с единицей). Но вот число 101 (5) является С2, так как впереди точно стоит ноль (вторая справа единица - последняя).
Стоит ещё акцентировать внимание на том, что изначально мы представляли любое двоичное число как чередующийся блок нулей и единиц (которое наверное стоило описать).
Но мы заметили, что чередующиеся блоки нулей и единиц (каждая длиной 1) при умножении удваивают число единиц: 01 01 0* 11 = 11 11 0 (Как видите 01 чередование нам интереснее, нежели 10)
Вот для этого и ввели c - блок. Он по сути занимает 2 позиции и описывает их поведение после преобразования. А поскольку такой переход можно найти только при переходе с a-блока на b-блок (даже если их длины единичные), но не при переходе с b-блока на a -блок. Надеюсь идея стала более понятна.
не знаю что в этом наглядного, но даже если начать скармливать это в некоторый regexp движок кажется оно ни разу не наглядно ..
Возможно... Соглашусь с первой регуляркой (там надо было исключать пустые a и b блоки, а мне сильно усложнять регулярку не хотелось, поэетому и не является правильной регуляркой), но вот вторая - она правильно захватывает области с корректным представлением. Поскольку всё это базировалось на неоднозначном представлении, то попробую привести пример правильного и неправильное представления одного и того же числа и проверить правильность на регулярке:
Число: 6805
Регулярка: (cb*a*)+
Двоичное представление: 1101010010101.
Неправильное представление: bb ab ca c ab c
Результат регулярки:
Как видим полная комбинация не соответствует нашему представлению
Правильное представление: cb c ca c c c (в 1-ой нотации это было бы [c1] [b1] [c2] [a1] [c3] c группами [cb] [c2a] [c3])
Результат регулярки:
Как видим все слово попадает
Как видим здесь в слове нет ab перехода, а слово начинается с C так как впереди нули находятся, которые мы не записываем.
Теперь про:
то куда кого инвертор? Вы хоть бы стейт машину какую нарисовали чтобы понимать кто кого куда и чем инвертировал.
Для двоичной записи 1 которая переходит на следующий разряд - это такой же по функциональности инвертор (меняет 0 на 1, а 1 на 0), но поскольку он в записи числа в нашей записи косвенно влияет (только на тот разряд, который является предыдущим для данного блока - мы читаем слева направо), то и b-блоком не является (и не должен, потому что является вспомогательным числом).
Сожалею о том, что получилось немного сумбурно и запутанно... Старался больше акцент делать на идеях для того, чтобы почувствовали какие параметры могут помочь с пониманием проблемы и возможностями решения)
В математике (особенно в теории чисел) вопрос зачем - неактуален (яркий пример с Великой Теоремой Ферма - бесполезная с такой точки зрения задача, но само решение и математические конструкции, которые открыл Эндрю Уайлз оказались намного интереснее и полезнее). Да и мы не знаем где эта задача может встретиться. Зерно проблемы заключается в простоте формулировке - по своей сути школьной задачи, где все упрощают до невозможности конкретными числами и значениями, а вот решить математические лбы до сих пор не могут)
Не отрицаю - это интересный вариант. Особенно если представить эту матрицу в виде блоков размеров 2x2, 2x3(с переменными расстояний) и 3x3(та самая матрица Герона)
Можно поподробнее объясните что подразумеваете под "последовательностью нулей и единиц"?
Да, но эта терминология здесь опирается на идеи и действия, которые мы реализуем. Я понимаю, что в математике важен формализм, но точные формулировки усложняют именно восприятие идеи, но зато не имеют иных трактовок. А как мне кажется Хабр - портал с публицистической напрвленностью, в котором эту проблему можно решать с помощью диалога или комментариев для конкретизации того, что хочет донести автор. Надеюсь примерами и обсуждением мы добьемся понимания темы)
Поймали) - я не описал нормально правило формирования таких слов-блоков. И стоит начать с источника проблем:
Здесь стоит сказать, что для нас интересно чередование вида 01 = С, так как при умножении на 3, 01 превращается в 11 (если с прошлых разрядов не пришла единица) или 00 (если она пришла). С примером 101(5) не С2 (особенно если перед стоит блок с единицей). Но вот число 101 (5) является С2, так как впереди точно стоит ноль (вторая справа единица - последняя).
Стоит ещё акцентировать внимание на том, что изначально мы представляли любое двоичное число как чередующийся блок нулей и единиц (которое наверное стоило описать).
Но мы заметили, что чередующиеся блоки нулей и единиц (каждая длиной 1) при умножении удваивают число единиц: 01 01 0* 11 = 11 11 0 (Как видите 01 чередование нам интереснее, нежели 10)
Вот для этого и ввели c - блок. Он по сути занимает 2 позиции и описывает их поведение после преобразования. А поскольку такой переход можно найти только при переходе с a-блока на b-блок (даже если их длины единичные), но не при переходе с b-блока на a -блок. Надеюсь идея стала более понятна.
Возможно... Соглашусь с первой регуляркой (там надо было исключать пустые a и b блоки, а мне сильно усложнять регулярку не хотелось, поэетому и не является правильной регуляркой), но вот вторая - она правильно захватывает области с корректным представлением. Поскольку всё это базировалось на неоднозначном представлении, то попробую привести пример правильного и неправильное представления одного и того же числа и проверить правильность на регулярке:
Число: 6805
Регулярка: (cb*a*)+
Двоичное представление: 1101010010101.
Неправильное представление: bb ab ca c ab c
Результат регулярки:
Правильное представление: cb c ca c c c (в 1-ой нотации это было бы [c1] [b1] [c2] [a1] [c3] c группами [cb] [c2a] [c3])
Результат регулярки:
Как видим здесь в слове нет ab перехода, а слово начинается с C так как впереди нули находятся, которые мы не записываем.
Теперь про:
Для двоичной записи 1 которая переходит на следующий разряд - это такой же по функциональности инвертор (меняет 0 на 1, а 1 на 0), но поскольку он в записи числа в нашей записи косвенно влияет (только на тот разряд, который является предыдущим для данного блока - мы читаем слева направо), то и b-блоком не является (и не должен, потому что является вспомогательным числом).
Сожалею о том, что получилось немного сумбурно и запутанно... Старался больше акцент делать на идеях для того, чтобы почувствовали какие параметры могут помочь с пониманием проблемы и возможностями решения)
В математике (особенно в теории чисел) вопрос зачем - неактуален (яркий пример с Великой Теоремой Ферма - бесполезная с такой точки зрения задача, но само решение и математические конструкции, которые открыл Эндрю Уайлз оказались намного интереснее и полезнее). Да и мы не знаем где эта задача может встретиться. Зерно проблемы заключается в простоте формулировке - по своей сути школьной задачи, где все упрощают до невозможности конкретными числами и значениями, а вот решить математические лбы до сих пор не могут)
Не отрицаю - это интересный вариант. Особенно если представить эту матрицу в виде блоков размеров 2x2, 2x3(с переменными расстояний) и 3x3(та самая матрица Герона)