Page 1 of 79

Кът на програмиста...

Posted: Wed May 09, 2007 2:32 pm
by Corwin
Моридине, аз си се оправих с моя регексп, обаче кат си машина искам да се пробваш да ми обясниш как работи следното нещо, щот досега никой не е успял... ;)
sub is_prime {
my ($number) = @_;
return (1 x $number) !~ m/\A (?: 1? | (11+?) (?> \1+ ) ) \Z/xms;
}

Posted: Wed May 09, 2007 2:51 pm
by The Dragon
Не работи. Ако функцията си отговаря на името.

Posted: Wed May 09, 2007 3:13 pm
by Corwin
Работи си. :)
Връща истина ако подаденото число е просто. Писала го е Абигейл, една психопатка дето е контрибютнала милион модули в ЦПАН. Аз лично съм го виждал в "Best Perl Practices", ама май е печелила някво състезание с него...

Posted: Wed May 09, 2007 3:18 pm
by The Dragon
А дали връща само тогава?

Posted: Wed May 09, 2007 3:29 pm
by Corwin
Code:
Spoiler: show
sub is_prime {
my ($number) = @_;
return (1 x $number) !~ m/\A (?: 1? | (11+?) (?> \1+ ) ) \Z/xms;
}

for my $current_num ( 1 .. 100 ) {
if ( is_prime($current_num) ) {
print "$current_num - Prime\n";
}
}
Output:
Spoiler: show
[corwin@corwin ~/myshits/scripts]$ perl regexpr.pl
2 - Prime
3 - Prime
5 - Prime
7 - Prime
11 - Prime
13 - Prime
17 - Prime
19 - Prime
23 - Prime
29 - Prime
31 - Prime
37 - Prime
41 - Prime
43 - Prime
47 - Prime
53 - Prime
59 - Prime
61 - Prime
67 - Prime
71 - Prime
73 - Prime
79 - Prime
83 - Prime
89 - Prime
97 - Prime

Posted: Wed May 09, 2007 4:08 pm
by Corwin
* Your mom is so fat she sat on a binary tree and turned it into a linked list in constant time!
* Saying Java is good because it works on all OSes is like saying anal sex is good because it works on all genders.
* Q: "What is the object oriented way of getting rich?" A: Inheritance

Posted: Wed May 09, 2007 4:24 pm
by shayhiri
От информатика разбирам нула, но не закачайте а***ния се*с. :evil:

Posted: Wed May 09, 2007 4:35 pm
by Marfa
Ае, не че нещо, ама какво му е на секса, че се нуждае от звездичка насред себе си? :roll:

Posted: Wed May 09, 2007 4:44 pm
by shayhiri
off
Това е смокиновото листо върху голямото К в средата.

Де да знам, от приличие. :) Иначе се радвам, че си от нашта партия.
/off

Posted: Wed May 09, 2007 4:50 pm
by Morwen
[offtopic]И откога секс е неприлична дума, значи? :lol: И къде е приличието да говориш за нещо и на всички да им е ясно за какво, но да си извърташ езика, та да не могат да те кажат, че си говорел точно за него?
[/offtopic]
Не ми е ясно точно как програмистката тема успя да се оспами със сексуални спорове, но може би не е зле някой модератор да попремести в пералнята излишното...

Posted: Wed May 09, 2007 4:53 pm
by Moridin
Стига сте спамили ;р

Як изглежда изразът, ама сега съм на мийтинг :(
по-късно :)

Posted: Wed May 09, 2007 10:27 pm
by thunder
плакат е, за това в спойлерче :)
Spoiler: show
Image

Posted: Thu May 10, 2007 4:13 pm
by Moridin
Измислих го, хитричко е :) Доста нестандартен подход, макар и леко хамалски :mrgreen: Но като цяло тъмбс ъп.

Идеята е следната -
Spoiler: show
числото N, с което започваме, се преобразува в N на брой единици. Това се прави от пърл-ския код.

Самият регулярен израз прави всъщност нещо много просто - проверява дали числото има делители. Ако има делители (т.е. имаме match), числото е съставно. Ако няма (т.е. няма match - затова и условието е !~), числото е просто.

Проверката става по следния начин:
Изразът има две алтернативи - едната е частта "1?", другата е частта "(11+?)(?> \1+)". Целият израз е ограден в група, за да сложим отпред и отзад ограничителите за място \A и \Z (още известни като ^ и $). Тази група има ?: отпред, за да не се брои при номерацията на backreferences, т.е. групираме само за синтактично удобство, без да запазваме резултата, match-нат от групата.

Така. Първата част намира като съвпадение вариантите празен стринг (N=0) и една единица (N=1). Тези две числа не се броят за прости в математиката и затова трябва да се укажат тук като "съставни" (не че са и съставни).

Втората част практически обхожда числата над 1 (представени като низ от единици с "11+", т.е. с поне две единици), като за всяко проверява дали до края на низа има точен брой повторения на това число. Ако това е така - значи числото N точно се дели на число, по-голямо от 1 и по-малко от самото него, и следователно е съставно. Ако изразът фейлне при целия бектракинг - значи няма съвпадение и числото е просто.

За пример да вземем N=6. То генерира низа "111111". Първата алтернатива на израза отпада, понеже N>1. След това първата група (11+?) хваща подниза "11" в началото. Прави така, понеже имаме lazy quantifier, т.е. ще вземе най-малкия подниз, който удовлетворява израза в скобите. След това идва веселата част - търсим до края точен брой повторения (+) на запазеното в първите скоби (\1). При нас това се получава! Имаме остатък "1111", което са две повторения на низа "11", който в текущия момент се пази от първата група и към него сочи референцията "\1". Така имаме повторение и значи числото е съставно.

Сега да вземем N=5. При него това няма да стане, защото остатъкът от низа е "111". Групата "11" се повтаря веднъж и удовлетворява "\1+", но след това регулярният израз свършва, а в низа има още една единица. Съвпадението пропада и машината започва да бектраква. При това групата \1 сега ще пази "111" - следващият lazy match. Сега остатъкът е "11" и няма повторение. Пропада - пак бектрак, при който \1 става "1111" - пак същото, и при "11111" - пак. Целият израз пропада и следователно 5 е просто число.

И остана да изясня за какво служи това "?>" във вторите скоби. Ами пести доста бектракинг. При 5 и 6 това не се вижда, но да вземем за пример N=7. Тогава след провала на мачването на повторения с група \1="11", машината няма да бектрекне до това да присвои на групата "111" (следващата стъпка от lazy matching-а на първия подизраз), а първо ще се опита да намали обхвата на greedy matching-а на втория подизраз (\1+), т.е. оригинално то е намерило две повторения и се е провалило след това, сега ще счита запазеното във втората група като само едно повторение на \1 и ще започне да чете пак до края израза. В нашия случай това е безсмислено - няма значение колко са повторенията, а само дали точно изчерпват остатъка от низа, или не. При това след тази втора група от повторения няма нищо друго в израза. Ние знаем това, но машината не го знае. За това този бектракинг ни бави излишно - спестяваме го, като слагаме "?>" отпред на втората група. С този синтаксис постигаме нещо като "cut" при Prolog - забраняваме повече бектракинг ВЪТРЕ в границите на тази група, т.е. веднъж мачната, тя вече се счита за атомарен елемент, а не за подизраз, който може още да бъде мачван и бектракван.

Хм... абе май се виждаше и при 5 :mrgreen: както и да е.

п.п. опциите зад израза, както и \A и \Z би трябвало да са ясни :) Специално опцията "х" позволява да има интервали в израза и те да се игнорират от парсъра на автомата за израза.
п.п.2. По молба на Роумър слагам обяснението в спойлър, че да се мъчи грешната му душа да гадае :mrgreen:

Posted: Thu May 10, 2007 4:40 pm
by thunder
еййй, за една задача в хаккуест използвах нещо подобно, но можах да се вместя в 3-те секунди време за излисление (много голямо число беше там) :)

много яко, сега го пуснах тука :) Не е нормална тази Абигейл

Posted: Thu May 10, 2007 4:46 pm
by Moridin
А коя е Абигейл и отде знаем, че изразът е неин?