 |
06.05.2008, 22:02
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
С нами:
10139366
Репутация:
1502
|
|
Интересная регулярка
//Решил не писать в вопросы по чему бы то ни было,
//так как там точно сразу не ответят,
//и вопрос затеряется в глубинах топика
Задачка была предложена когда-то на олимпиаде по информатике - я что-то тогда примерно придумал, но, вроде, неправильно.
Итак, задачка:
Есть строка из нулей и единиц - запись какого-то числа X в двоичной системе.
Надо составить регулярку, определяющую, делится ли это число X на 3.
Что-то вдруг захотелось придумать к ней решение 
//решено: ответ дан мной ниже в теме
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
Последний раз редактировалось desTiny; 15.05.2008 в 23:05..
|
|
|
06.05.2008, 22:14
|
|
Познавший АНТИЧАТ
Регистрация: 14.01.2008
Сообщений: 1,165
С нами:
9644006
Репутация:
3099
|
|
проще простого: делим или складываем числа, при сложении получается число делящеяся на три без остатка.... (математика какой то клас... правило такое)
напрмер: 93- 9+3=12
12\3= 4 ))) вот как то так вроде
Последний раз редактировалось xcedz; 07.05.2008 в 06:34..
|
|
|
|
06.05.2008, 23:17
|
|
Познающий
Регистрация: 12.11.2007
Сообщений: 69
С нами:
9734726
Репутация:
676
|
|
Очень интересная задача, пока пришел только к такому выводу - сумма цифр, полученная от деления числа в двоичном виде при делении на тройку дает остаток 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
Последний раз редактировалось Евгений Минаев; 06.05.2008 в 23:32..
|
|
|
|
06.05.2008, 23:38
|
|
Постоянный
Регистрация: 06.06.2006
Сообщений: 515
С нами:
10489346
Репутация:
963
|
|
Ну если регулярки ничем не ограничены то можно "прочитерить")
Код:
# 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:\>
третий раз поправил) все
Последний раз редактировалось KSURi; 07.05.2008 в 00:17..
|
|
|
|
07.05.2008, 17:23
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
С нами:
10139366
Репутация:
1502
|
|
На самом деле, всё что я понял - даже с доказательством, нетрудным - это то, что в этом двоичном числе
Остаток от деления суммы цифр на чётных позициях на 3 равен остатку от деления суммы цифр на нечётных позициях на 3
Иначе говоря,
Сумма цифр на чётных позициях сравнима с суммой цифр на нечётных позициях по модулю 3
И это как-то точно можно реализовать - говорю - задачка с олимпиады.
2Евгений Минаев:
Что-то я плохо понял твою идею...
2xcedz - не то... переводить нельзя. Всё, что можно - проверить строку с двоичной записью на регулярке.
2KSURi - хитрить нельзя По оригинальному условию - всё, что у нас есть - это строка и регулярка
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
07.05.2008, 20:42
|
|
Постоянный
Регистрация: 06.06.2006
Сообщений: 515
С нами:
10489346
Репутация:
963
|
|
Ну хорошо-хорошо, чит был в том, что кроме регулярки (левая часть оператора 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:\>
|
|
|
|
10.05.2008, 17:40
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
С нами:
10139366
Репутация:
1502
|
|
Сообщение от 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, нет.
В регулярке можно использовать только конкатенацию, выбор, повторения и скобки.
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
11.05.2008, 03:14
|
|
Постоянный
Регистрация: 06.06.2006
Сообщений: 515
С нами:
10489346
Репутация:
963
|
|
значит это не регулярка, а "кастрат".
|
|
|
|
11.05.2008, 09:12
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
С нами:
10139366
Репутация:
1502
|
|
Сообщение от KSURi
значит это не регулярка, а "кастрат".
Задачка от этого менее интересной не становится
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
15.05.2008, 20:47
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
С нами:
10139366
Репутация:
1502
|
|
короче, правильный ответ был найден (методом пинания одного из оргов олимпиады ):
(0|1(01*0)*1)*
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
Последний раз редактировалось desTiny; 16.05.2008 в 08:00..
|
|
|
|
|
|
Предыдущая тема
Следующая тема
Похожие темы
|
| Тема |
Автор |
Раздел |
Ответов |
Последнее сообщение |
|
Интересная игра
|
z01b |
Болталка |
1 |
02.02.2008 17:30 |
|
Интересная идея
|
cmex |
Болталка |
3 |
30.12.2007 00:20 |
|
Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
|
|
|
|
Линейный вид
