Задачка

[gul_tech]

Напишите регулярное выражение (обычное, работающее для egrep), которое определяет числа, записанные в двоичной системе, кратные трём (и только их). Или докажите, что это невозможно.
Мне понадобилось несколько заходов для решения, но всё-таки решил. :)

Comments

[muwlgr.livejournal.com]

Использованные матерьялы :
http://geeki.wordpress.com/2008/01/03/fsa-to-find-whether-a-binary-number-is-divisible-by-3/

результирующий регексп (исправил коммент, дописав 0* после ^):

^0*((1(0(00)*(1(00)*)*0)?1)0*)*$

тестик на ruby :

(1..100000).each {|i|
s=i.to_s(2)
z=i%3
m=/^0*((1(0(00)*(1(00)*)*0)?1)0*)*$/.match(s)
if (z==0 and m==nil) or (z!=0 and m!=nil)
p [i, s.sub(/0*$/,''), m]
end
}

(распечатка должна быть пустой, возвращаемое значение each - исходный диапазон итерации)

[gul-kiev.livejournal.com]

Да, всё правильно.
Конечно, задачки лучше решать без помощи гугля, но в данном случае это именно помощь, а не готовый ответ, так что засчитывается. :)
Ну и мне кажется корректнее вариант "либо ноль, либо число, не начинающееся с нуля", но это уже мелочи.
И это выражение можно оптимизировать, как минимум на пару скобок. Хотя справедливости ради скажу, что у меня получилось более громоздко.
Ещё можно заодно сформулировать признак делимости на три в двоичной системе. У меня получилось даже два разных варианта.

[muwlgr.livejournal.com]

Тут прислали ваще ломовое решение - ^(0*|(1(01*0)*1)*)*$

http://groups.google.com/group/soft_rd_dp_ua/browse_thread/thread/6ed158fee28cbef5