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

За коментари и излияния от всякакъв род, число, спрежение и залог

Moderator: Moridin

Post Reply
User avatar
Corwin
Archmage
Posts: 2002
Joined: Fri Mar 26, 2004 3:41 pm
Location: Land of Supidity

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

Post by Corwin » Wed May 09, 2007 2:32 pm

Моридине, аз си се оправих с моя регексп, обаче кат си машина искам да се пробваш да ми обясниш как работи следното нещо, щот досега никой не е успял... ;)
sub is_prime {
my ($number) = @_;
return (1 x $number) !~ m/\A (?: 1? | (11+?) (?> \1+ ) ) \Z/xms;
}
I like rusty spoons....
I like to touch them...
It's almost orgasmic...

User avatar
The Dragon
Elder God
Posts: 9053
Joined: Wed Jan 14, 2004 9:03 pm

Post by The Dragon » Wed May 09, 2007 2:51 pm

Не работи. Ако функцията си отговаря на името.
The sinking of the Titanic was a miracle to the lobsters in the ship's kitchen.

User avatar
Corwin
Archmage
Posts: 2002
Joined: Fri Mar 26, 2004 3:41 pm
Location: Land of Supidity

Post by Corwin » Wed May 09, 2007 3:13 pm

Работи си. :)
Връща истина ако подаденото число е просто. Писала го е Абигейл, една психопатка дето е контрибютнала милион модули в ЦПАН. Аз лично съм го виждал в "Best Perl Practices", ама май е печелила някво състезание с него...
I like rusty spoons....
I like to touch them...
It's almost orgasmic...

User avatar
The Dragon
Elder God
Posts: 9053
Joined: Wed Jan 14, 2004 9:03 pm

Post by The Dragon » Wed May 09, 2007 3:18 pm

А дали връща само тогава?
The sinking of the Titanic was a miracle to the lobsters in the ship's kitchen.

User avatar
Corwin
Archmage
Posts: 2002
Joined: Fri Mar 26, 2004 3:41 pm
Location: Land of Supidity

Post by Corwin » Wed May 09, 2007 3:29 pm

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
I like rusty spoons....
I like to touch them...
It's almost orgasmic...

User avatar
Corwin
Archmage
Posts: 2002
Joined: Fri Mar 26, 2004 3:41 pm
Location: Land of Supidity

Post by Corwin » Wed May 09, 2007 4:08 pm

* 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
I like rusty spoons....
I like to touch them...
It's almost orgasmic...

User avatar
shayhiri
Elder God
Posts: 6111
Joined: Mon Dec 20, 2004 7:15 pm

Post by shayhiri » Wed May 09, 2007 4:24 pm

От информатика разбирам нула, но не закачайте а***ния се*с. :evil:
passer-by wrote:А, сетих се. Гледайте "Големият Стан". В programata.bg беше злостно оплют, ама трейлърът ми допадна, рекох да рискувам и го гледах оня ден. Доста приятна комедийка. Напомни ми на оная другата с Адам Сандлър и затворническия футбол, но в по-добър вариант.

User avatar
Marfa
Moderator
Posts: 11233
Joined: Sat Dec 20, 2003 10:12 pm
Contact:

Post by Marfa » Wed May 09, 2007 4:35 pm

Ае, не че нещо, ама какво му е на секса, че се нуждае от звездичка насред себе си? :roll:
This octopus! Let's give him boots, send him to North Korea!

Image<-Подробно описание на нещата, които ми образуват нерви :twisted:
Уук.

User avatar
shayhiri
Elder God
Posts: 6111
Joined: Mon Dec 20, 2004 7:15 pm

Post by shayhiri » Wed May 09, 2007 4:44 pm

off
Това е смокиновото листо върху голямото К в средата.

Де да знам, от приличие. :) Иначе се радвам, че си от нашта партия.
/off
passer-by wrote:А, сетих се. Гледайте "Големият Стан". В programata.bg беше злостно оплют, ама трейлърът ми допадна, рекох да рискувам и го гледах оня ден. Доста приятна комедийка. Напомни ми на оная другата с Адам Сандлър и затворническия футбол, но в по-добър вариант.

User avatar
Morwen
Shadowdancer
Posts: 13468
Joined: Sat Dec 20, 2003 1:20 am

Post by Morwen » Wed May 09, 2007 4:50 pm

[offtopic]И откога секс е неприлична дума, значи? :lol: И къде е приличието да говориш за нещо и на всички да им е ясно за какво, но да си извърташ езика, та да не могат да те кажат, че си говорел точно за него?
[/offtopic]
Не ми е ясно точно как програмистката тема успя да се оспами със сексуални спорове, но може би не е зле някой модератор да попремести в пералнята излишното...
I don't wanna die
But I ain't keen on living either

User avatar
Moridin
Global Moderator
Posts: 19287
Joined: Fri Dec 19, 2003 10:21 pm
Location: On the other side
Contact:

Post by Moridin » Wed May 09, 2007 4:53 pm

Стига сте спамили ;р

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

User avatar
thunder
Forsaken
Posts: 3376
Joined: Wed Jan 21, 2004 2:18 pm
Location: София

Post by thunder » Wed May 09, 2007 10:27 pm

плакат е, за това в спойлерче :)
Spoiler: show
Image
Scalpel. Sponge. Magic Wand!

User avatar
Moridin
Global Moderator
Posts: 19287
Joined: Fri Dec 19, 2003 10:21 pm
Location: On the other side
Contact:

Post by Moridin » Thu May 10, 2007 4:13 pm

Измислих го, хитричко е :) Доста нестандартен подход, макар и леко хамалски :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:
This is it. Ground zero.

User avatar
thunder
Forsaken
Posts: 3376
Joined: Wed Jan 21, 2004 2:18 pm
Location: София

Post by thunder » Thu May 10, 2007 4:40 pm

еййй, за една задача в хаккуест използвах нещо подобно, но можах да се вместя в 3-те секунди време за излисление (много голямо число беше там) :)

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

User avatar
Moridin
Global Moderator
Posts: 19287
Joined: Fri Dec 19, 2003 10:21 pm
Location: On the other side
Contact:

Post by Moridin » Thu May 10, 2007 4:46 pm

А коя е Абигейл и отде знаем, че изразът е неин?
This is it. Ground zero.

Who is online

Users browsing this forum: No registered users and 22 guests