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
От информатика разбирам нула, но не закачайте а***ния се*с.
Posted: Wed May 09, 2007 4:35 pm
by Marfa
Ае, не че нещо, ама какво му е на секса, че се нуждае от звездичка насред себе си?
Posted: Wed May 09, 2007 4:44 pm
by shayhiri
off
Това е смокиновото листо върху голямото
К в средата.
Де да знам, от приличие.
Иначе се радвам, че си от нашта партия.
/off
Posted: Wed May 09, 2007 4:50 pm
by Morwen
[offtopic]И откога секс е неприлична дума, значи?
И къде е приличието да говориш за нещо и на всички да им е ясно за какво, но да си извърташ езика, та да не могат да те кажат, че си говорел точно за него?
[/offtopic]
Не ми е ясно точно как програмистката тема успя да се оспами със сексуални спорове, но може би не е зле някой модератор да попремести в пералнята излишното...
Posted: Wed May 09, 2007 4:53 pm
by Moridin
Стига сте спамили ;р
Як изглежда изразът, ама сега съм на мийтинг
по-късно
Posted: Wed May 09, 2007 10:27 pm
by thunder
плакат е, за това в спойлерче
- Spoiler: show
-
Posted: Thu May 10, 2007 4:13 pm
by Moridin
Измислих го, хитричко е
Доста нестандартен подход, макар и леко хамалски
Но като цяло тъмбс ъп.
Идеята е следната -
- 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 както и да е.
п.п. опциите зад израза, както и \A и \Z би трябвало да са ясни Специално опцията "х" позволява да има интервали в израза и те да се игнорират от парсъра на автомата за израза.
п.п.2. По молба на Роумър слагам обяснението в спойлър, че да се мъчи грешната му душа да гадае
Posted: Thu May 10, 2007 4:40 pm
by thunder
еййй, за една задача в хаккуест използвах нещо подобно, но можах да се вместя в 3-те секунди време за излисление (много голямо число беше там)
много яко, сега го пуснах тука
Не е нормална тази Абигейл
Posted: Thu May 10, 2007 4:46 pm
by Moridin
А коя е Абигейл и отде знаем, че изразът е неин?