Интересная регулярка

[desTiny]

//Решил не писать в вопросы по чему бы то ни было,
//так как там точно сразу не ответят,
//и вопрос затеряется в глубинах топика

Задачка была предложена когда-то на олимпиаде по информатике - я что-то тогда примерно придумал, но, вроде, неправильно.

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

Что-то вдруг захотелось придумать к ней решение :)

//решено: ответ дан мной ниже в теме

[xcedz]

проще простого: делим или складываем числа, при сложении получается число делящеяся на три без остатка.... (математика какой то клас... правило такое)
напрмер: 93- 9+3=12
12\3= 4 ))) вот как то так вроде

[Евгений Минаев]

Очень интересная задача, пока пришел только к такому выводу - сумма цифр, полученная от деления числа в двоичном виде при делении на тройку дает остаток 0. Но это пока все догадки. Цель задачи - найти признак делимости на тройку в двоиной системе счисления


6 = 110, 110 / 3 ~ 36 ( 3 + 6 = 9 ) делится
7 = 111, 111 / 3 ~ 37 ( 3 + 7 = 10 ) не делится
9 = 1001, 1001 / 3 ~ 333 ( 3 + 3 + 3 = 9 ) делится
11 = 1011, 1011 / 3 ~ 337 ( 3 + 3 + 7 = 13 ) не делится
15 = 1111, 1111 / 3 ~ 370 ( 3 + 7 + 0 + 10 ) делится

Между прочим выше я лоханулся, надо деление доводить до конца. Мне тут подсказали про перемену знаков. Рассмотрим на тех же числах

6 = 110, 1 - 1 + 0 = 0
7 = 111, 1 - 1 + 1 = 1
9 = 1001, 1 - 0 + 0 - 1 = 0
11 = 1011, 1 - 0 + 1 - 1 = 1
15 = 1111, 1 - 1 + 1 + 1 = 0

Не уверен что PCRE такое может xD

[KSURi]

Ну если регулярки ничем не ограничены то можно "прочитерить")

# 13 (не делится, остаток = 1)
C:\>perl -e"$_='1101';s/[10]+/oct(qq{0b$_})%3/e;print"
1

# 12 (делится, остаток 0):
C:\>perl -e"$_='1100';s/[10]+/oct(qq{0b$_})%3/e;print"
0
C:\>


третий раз поправил) все

[desTiny]

На самом деле, всё что я понял - даже с доказательством, нетрудным - это то, что в этом двоичном числе

Остаток от деления суммы цифр на чётных позициях на 3 равен остатку от деления суммы цифр на нечётных позициях на 3

Иначе говоря,

Сумма цифр на чётных позициях сравнима с суммой цифр на нечётных позициях по модулю 3

И это как-то точно можно реализовать - говорю - задачка с олимпиады.

2Евгений Минаев:
Что-то я плохо понял твою идею...

2xcedz - не то... переводить нельзя. Всё, что можно - проверить строку с двоичной записью на регулярке.
2KSURi - хитрить нельзя :) По оригинальному условию - всё, что у нас есть - это строка и регулярка :)

[KSURi]

Ну хорошо-хорошо, чит был в том, что кроме регулярки (левая часть оператора s///) был использован простой код для замены (правая часть оператора s///).
Вот вариант с чистой регуляркой, только динамической)

C:\>perl -e"$_='1100';/(??{$_=oct(qq{0b$_})%3})/;print"
0
C:\>perl -e"$_='1101';/(??{$_=oct(qq{0b$_})%3})/;print"
1
C:\>

Небольшое док-во, что используется именно регулярка, т.е. встроенные возможности библиотеки PCRE:

C:\>perl -e"$_=qr/(??{$_=oct(qq{0b$_})%3})/;print ref"
Regexp
C:\>

[desTiny]

Ну хорошо-хорошо, чит был в том, что кроме регулярки (левая часть оператора s///) был использован простой код для замены (правая часть оператора s///).
Вот вариант с чистой регуляркой, только динамической)

C:\>perl -e"$_='1100';/(??{$_=oct(qq{0b$_})%3})/;print"
0
C:\>perl -e"$_='1101';/(??{$_=oct(qq{0b$_})%3})/;print"
1
C:\>

Небольшое док-во, что используется именно регулярка, т.е. встроенные возможности библиотеки PCRE:

C:\>perl -e"$_=qr/(??{$_=oct(qq{0b$_})%3})/;print ref"
Regexp
C:\>


KSURi, нет.
В регулярке можно использовать только конкатенацию, выбор, повторения и скобки.

[KSURi]

значит это не регулярка, а "кастрат".

[desTiny]

значит это не регулярка, а "кастрат".
Задачка от этого менее интересной не становится :)

[desTiny]

короче, правильный ответ был найден (методом пинания одного из оргов олимпиады:)):

(0|1(01*0)*1)*