Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   PHP, PERL, MySQL, JavaScript (https://forum.antichat.xyz/forumdisplay.php?f=37)
-   -   Интересная регулярка (https://forum.antichat.xyz/showthread.php?t=69605)

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

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

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

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

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

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

Евгений Минаев 06.05.2008 23:17
Очень интересная задача, пока пришел только к такому выводу - сумма цифр, полученная от деления числа в двоичном виде при делении на тройку дает остаток 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 06.05.2008 23:38
Ну если регулярки ничем не ограничены то можно "прочитерить")
Код:
# 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 07.05.2008 17:23
На самом деле, всё что я понял - даже с доказательством, нетрудным - это то, что в этом двоичном числе

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

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

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

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

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

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

KSURi 07.05.2008 20:42
Ну хорошо-хорошо, чит был в том, что кроме регулярки (левая часть оператора 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 10.05.2008 17:40
Цитата:
Сообщение от 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:\>
KSURi, нет.
В регулярке можно использовать только конкатенацию, выбор, повторения и скобки.

KSURi 11.05.2008 03:14
значит это не регулярка, а "кастрат".

desTiny 11.05.2008 09:12
Цитата:
Сообщение от KSURi
значит это не регулярка, а "кастрат".
Задачка от этого менее интересной не становится :)

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

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


Время: 23:50