ScherZ Posted December 27, 2003 Share Posted December 27, 2003 Mmmm da vi dam edna zada4ka da se probvate(Ne se zaqjdam prosto mi emnogo interesno reshenieto i az li4no ne mojah da q resha) Дадено е равенството 1?2?3?.....?n=к . Ha мястото на всеки от въпросителните знаци,трябва да се постави един от знаците:"+"- за събиране,"-"-за изваждане,или "*"-за умножение(или навсякъде само един от трите знака),така че съгласно правилата на аритметиката да се полу4и вярно равенство(скоби не се използват).Пример за n=4 и k=14 един възможен верен израз е 1*2+3*4=14. Напишете програма която въвежда цялото число к, 0<к<10 000 и извежда наи-малкото цяло положително n, за което съществува верен израз от описания вид.Ако такова число n не съществува измежду числата до 10 000 ,програмата трябва да изведе 0. Пример : при въведено число 5, програмата трябва да изведе 3. ПС. Това е задачка дадена на Национален зимен турнир по математика и информатика "Димо Малешков" в Пловдив .Задачата е за 11 клас. Дерзайте! ПС: Има и др задачки но мисля че тази ви е достатачна за доста време ! Link to comment Share on other sites More sharing options...
tedy Posted December 27, 2003 Share Posted December 27, 2003 От пръв поглед си мисля, че тази задачка може да се реши с помощта на дървета или графи. Аз веднъж участвах в един конкурс, там взех 6-то място, ама бях решил задачата по 'дървен' начин, линейно. И въпреки това по бързина и точност беше доста задоволително. Първите места заеха именно тези, които използваха графи/двоични дървета. С помощта на готови методи за обработка на такива структури, за кратко време се решава задачката. Но отдавна не се занимавам с такива структури, така че няма да се пробвам Link to comment Share on other sites More sharing options...
ScherZ Posted December 28, 2003 Author Share Posted December 28, 2003 xaxa qvno nqma 4ak takiva golemi razbira4i... kolkoto se hvalite..... zashto li ne se u4udvam....emi da wse pak zada4kata si e trdyna i to dosta... Link to comment Share on other sites More sharing options...
tedy Posted December 28, 2003 Share Posted December 28, 2003 xaxa qvno nqma 4ak takiva golemi razbira4i... kolkoto se hvalite..... zashto li ne se u4udvam....emi da wse pak zada4kata si e trdyna i to dosta... Задачката си е лесна, и то доста, за един професионален програмист, това ще му е за закуска. Аз се чудя защо ти не я решиш, и тогава да видим решението колко е кратко. Още малко и ще ме навиеш да опитам Link to comment Share on other sites More sharing options...
ScherZ Posted December 28, 2003 Author Share Posted December 28, 2003 ne sam tvyrdqla 4e moga da e resha:) az ne sam nito profesionalen programist nito dori dobar:) prosto popadnah na tazi olimpiada i ne mojah da q resha:) koeto ne me o4udi estestveno... znam 4e zada4ata ne e trydna za edin dobar profesionalen programist:) v tova ne se samnqvam.... prosto vi q dadah zashtoto vsi4ki se pishete golemi programisti i reshih da vidq dali nqkoi moje da e reshi..pyk i mi e interesno reshenieto i:) BTw bqha kazali 4e shte iznesat reshenieto na saita na PU fmi ama ne sa go iznesli oshte ili pone az ne mojah da go namerq:) pak i w4era saityt ne ba4kashe ! Link to comment Share on other sites More sharing options...
tedy Posted December 28, 2003 Share Posted December 28, 2003 Така е, сайтът им често не бачка. За него се грижат добри професионалисти, познавам ги, но като се има предвид, че сайтът е базиран на Java, не е за учудване, че често го няма .Макар, че там основно изучавахме именно Java като основна технология ,аз въобще не съм фен на тази технология, просто е много тежка, има доста бъгове (все пак е сравнително нова). Link to comment Share on other sites More sharing options...
ScherZ Posted December 28, 2003 Author Share Posted December 28, 2003 mmm dam taka si e az ne razbiram mn ot java:) no sam prisastvala na razgovor mejdu priateli koito sa obsyjdali java ta znam 4e e bugava (uj)! Ina4e.... aide da ne obryshtame topica na obsyjdane na jaba:) ako nqkoi naistina e zaintrigycvam ot reshenieto na zada4kata .... neka se pomy4i:) ako li ne...skoro shte se closene topica:) Link to comment Share on other sites More sharing options...
BoardMan Posted December 28, 2003 Share Posted December 28, 2003 .... prosto vi q dadah zashtoto vsi4ki se pishete golemi programisti i reshih da vidq dali nqkoi moje da e reshi..pyk i mi e interesno reshenieto i:) Хехе, така си е - задачка закачка Между другото има много голяма разлика между системен, пиложен, програмист на ниско ниво и т.н. В повечето влучай такива математически закачки изобщо не намират конкретно приложение в практиката За това аз се кефя на приложната математика, там поне има някаква истинка Иначе аз не се съмнявам, че във форума има много качествени програмисти, просто мен (а предполагам и на повечето) никога не са ми допадали задачки които не решават никакъв практически проблем Не казвам, че тези които се явяват на олимпиади по информатика не са добри и нямат знания, напротив!. В повечето случай при тях се губи връзката с приложноото и им е по-трудно да зе захванат в последствие с конкретен приложен проблем. Защото това което е на теория върви винаги, само че в това което се прави на практика излизат купчина непредвидени проблеми, просто подхода е по-друг Ама щом е за идеята що да не решим задачката Link to comment Share on other sites More sharing options...
Shiro Posted December 28, 2003 Share Posted December 28, 2003 Emi az mai sym takyf programist, koito se zanimava sys systezatelna inoformatika. Uchastvah na tozi konkurs i stanah 7-i. Mislih dosta vreme nad zadachkata i kakto kazva tedy, naistina dobroto reshenie e graphsko. Samo che tuk ima edna hitrost. Okazva se che vsichki chisla pod 10000 mogat da se dostignat s nai-mnogo 16 posledovatelni chisla svyrzani sys znacite + - *. Taka reshenieto na zadachkata se okazva bruteforce (nadqvam se znaete kakvo e tova). Nqma nikakyf problem da se izprobvat vsichki kombinacii. Te sa 3^15, koeto e 14348907 i za takiva prosti smetki kompiutyryt go izpylnqva za po-malko ot secunda (Testvashtiq komp na systezanieto beshe Duron na 1.7). A kak se pishe bruteforce-a nqma da obqsnqvam. ScherZ: q se predstavi Link to comment Share on other sites More sharing options...
furiozo Posted December 29, 2003 Share Posted December 29, 2003 Shiro, kaji kva e ideqta na "naistina dobroto reChenie" adi postvaite resheniq az napravih edno brute force reshenie, a syshto i benchmark extension koito reshava zadachata posledovatelno za vsichki stoinosti na k 2<=k<=p koito sym pusnal sega i go chakam da svyrshi koeto izglejda shte e sled chas-dva, osven obshtoto vreme shte stane qsno i za koq stoinost na k namiraneto na reshenie e bilo nai bavno adi, kato ste gotovi s vashite resheniq shte postna source + benchmark results Link to comment Share on other sites More sharing options...
furiozo Posted December 29, 2003 Share Posted December 29, 2003 helllooooo, anybody hoOoOome testa zavyrshi za 2h 48m na Athlon 2.2 GHz, ako mi e vqrno reshenieto ima stoinosti na k za koito minimalnoto n e 17 are pishete neshto Link to comment Share on other sites More sharing options...
tedy Posted December 29, 2003 Share Posted December 29, 2003 Като се позамислих малко, мисля че задачката може да се реши рекурсивно (пак с bruteforce). Нещо от сорта: прилага се първата операция. На резултата се прилага обратна операция спрямо К и се подава на следваща рекурсия. И така с всички от възможните знаци. Не съм го изгладил, само идея, може първо наистина да се пробвам по вашите начини Link to comment Share on other sites More sharing options...
BoardMan Posted December 30, 2003 Share Posted December 30, 2003 Znaci ne mi se iska da wiarwam ce 'grubata sila' e edinstwennoto reshenie w slucaja no maj za momenta towa e izhoda (kato se ima w predwid ce zadacata e za 11 klas). Inace eto moite razsazdenia po wuprosa: Shiro e prav za idejata, kato az zalagam na malki optimizacii. Purwo spowed men niama nerehimi stojnosti za K, toest K ne moze da e 0 oswen ako N=0. Togawa maximalnata redica s kojato moze da se reshi K e 1-2+3-4...+K=N, toest wseki pat stojnostta na rezultata ste se uwelicawa s 1 s uwelicawane na 2*K clena ot redicata. Znaci ako triabwa da se dostigne N to w naj-loshia slucaj towa ste e sled 2N iteracii na cikula. Oswen max. ogranicenie nalagam i min ogranicenie na cikula kato proweriawam purwo posledowatelno za 1!, 2!....p! dokato stojnostta na p! stane po-goliama ot N. Ako stane ravna na N znaci imame rezultat, ako ne wzimame po malkoto 'p' predi (p+1)! da e nadminalo N. Twa e min.stojnost na K za kojato se zapocwa da se wurti cikula. Znaci po-malka ne moze da ima. Oswen towa w samia cikal nalagam prioritet na operaciite: parwo *, posle +, sled towa - Spored max. twurdenie spored men kraen rezultat ste bade dostignat pri redica s 2N clenowe, toest 20000, ot swoha strana poslednia e 20000, koeto e 15 bita De da znam, moze i ga gresha no edwa li ste ima znacenie poneze smiatam krajnia rezultat za wsiako N i K da go oformia w nesto kato programiruema matrica s hesh tablica i sled puskaneto na programata tia da izwlica rezultata s edo tursene w gotowata tablica /pri hesh e naj-barzo / Ej na towa az mu wikam prakticno hehe. Kogato se goni skorost se dejstwa taka (pone pri woennite taka se backa w tehnite sistemi) Programka sled nowa godina stoto idwat praznici BTW, Weselo posrestane na nowata godina na wsicki i stasliwa nowa goina! Link to comment Share on other sites More sharing options...
tedy Posted December 30, 2003 Share Posted December 30, 2003 BoardMan, начинът ти ми изглежда, че може да даде резултат, само остава да се напише. Специално за bruteforce, това дето търсиш (Nmax-1)! преди да надмине К (защото условието беше 1?2?3...?N=K) е малко ненужно защото така или иначе цикълът ще се върти последователно за всички числа над 1 за трите възможни операции, следователно там няма да е нужно да знаем най-лошия случай защото ние ще сме получили резултата преди него. А според хитростта на Shiro, това ще са най-много 16 числа, наистина бързо . furiozo изглежда е готов отдавна, само ние си чешем езиците , да се пробваме и ние вече. Link to comment Share on other sites More sharing options...
tedy Posted December 30, 2003 Share Posted December 30, 2003 Ето и едно просто според мен решение на задачката с bruteforce. Не извеждам точните операции за достигане на К, само максималното N, както е в условието. Програмката тук за сорса ако има още интерес можем да сравняваме Link to comment Share on other sites More sharing options...
furiozo Posted December 30, 2003 Share Posted December 30, 2003 tedy, ako se beshe napynal da napravish da izpisva reshenieto shteshe da vidish che algorityma ti ne e korekten, nai niskoto chislo za koeto dava greshen rezultat e 8, vryshta n=4 a vsyshnost e 5, eto razvivka na obhojdane: n=2 3=1+2 -1=1-2 2=1*2 n=3 6=1+2+3 2=1-2+3 5=1*2+3 0=1+2-3 -4=1-2-3 -1=1*2-3 7=1+2*3 -5=1-2*3 6=1*2*3 n=4 10=1+2+3+4 6=1-2+3+4 9=1*2+3+4 4=1+2-3+4 0=1-2-3+4 3=1*2-3+4 11=1+2*3+4 -1=1-2*3+4 10=1*2*3+4 2=1+2+3-4 -2=1-2+3-4 1=1*2+3-4 -4=1+2-3-4 -8=1-2-3-4 -5=1*2-3-4 3=1+2*3-4 -9=1-2*3-4 2=1*2*3-4 15=1+2+3*4 11=1-2+3*4 14=1*2+3*4 -9=1+2-3*4 -13=1-2-3*4 -10=1*2-3*4 25=1+2*3*4 -23=1-2*3*4 24=1*2*3*4 n=5 15=1+2+3+4+5 11=1-2+3+4+5 14=1*2+3+4+5 9=1+2-3+4+5 5=1-2-3+4+5 8=1*2-3+4+5 i are nqkoi da kaje toq non brute force algoritym BoardMan, optimizaciqta ot dolu shte ima prenebrejim efekt zashtoto 8!=40320>10000 a vsichki kombinacii za n<=8 za obhojdat za stotni ot sekundata na moito PC, osezaemoto zabavqne zapochva ~ pri n=14, n=15 eto i moeto reshenie kompilirano za windows o_O http://play.evrocom.net/dl/incoming/furioz.../zad1/zad1a.exe i za linux http://play.evrocom.net/dl/incoming/furioz...39;s/zad1/zad1a startira se s parametyr k, primer: >zad1a.exe 9673 n= 1 ... no n= 2 ... no n= 3 ... no n= 4 ... no n= 5 ... no n= 6 ... no n= 7 ... no n= 8 ... no n= 9 ... no n= 10 ... no n= 11 ... no n= 12 ... no n= 13 ... no n= 14 ... no n= 15 ... no n= 16 ... no n= 17 ... yes 9673=1+2-3+4*5*6*7*8+9*10+11*12+13*14*15-16+17 Link to comment Share on other sites More sharing options...
tedy Posted December 30, 2003 Share Posted December 30, 2003 съжалявам наистина, сега видях, че наистина за 8 дава грешно. Нправих го да изписва и израза накрая. Изглежда в алгоритъма за управление на троичната бройна система съм допуснал някоя грешчица, но утре ще го погледна по- на светло, а може и аз да направя един benchmark модул да видя за колко ще свърши Link to comment Share on other sites More sharing options...
tedy Posted January 1, 2004 Share Posted January 1, 2004 Готово, оказа се техническа грешка в изчисляването на редовете. Тук това вече работи. furiozo, за числото 9673, което си дал като пример, аз го получавам с други операции, но пак с 17 поредни числа. Изглежда за по-големите числа има различни варианти за получаването им. И вероятно при някои твоя алгоритъм може да е по-бърз, при други моя. Аз въртя операциите по реда: *,+,-. Ти предполагам по друг начин и затова става така. А, нали щеше да дадеш benchmark, за кои К е най-бързо, за кои най-бавно, интересно ми е да сравня с моите резултати, които не съм получил още EDIT: Ето малко benchmark results и от мен: теста за всички 0<к<10000 завърши точно за 1 час, като най-бавно се намери резултата за к=9643 (7170 ms). Извадка: ... 9992 9993 9994 9995 9996 9997 9998 9999 10000 Total time: 3550 seconds Min time: ~0(k=1); Max time: 7170(k=9643) milliseconds Link to comment Share on other sites More sharing options...
furiozo Posted January 2, 2004 Share Posted January 2, 2004 izglejda statisticheski *+- e nai dobrata posledovatelnost moqta programa vse pak beshe okolo 2.5 pyti po bavna ot tvoita no kato zamenih edin ostatyk - '%' s izvajdane, umnojenie i 2 prisvoqvaniq stana dori malko po byrza no s razlika koqto navqrno e vypros na kompilator i parametri na kompilirane tazi promqna zagrozi koda vizualno no qvno deleneto trqa da se izbqgva po vyzmojnost syshto probvah da zamenq celochisleno delene s floating point umnojenie no tva ne beshe nikak dobra ideq eto mi koda : http://play.evrocom.net/dl/incoming/furioz...s/zad1/zad1a1.c otnosno tyrseneto na nai bavnata stoinost na k, ne trqa da se meri vremeto za namirane zashtoto pri blizki stoinosti kato se sluchi v tochniq moment mashinata da se natovari s neshto drugo i se zabavq otgovora , trqbva da se gleda kolko nadalech s variantite e stignal akgorityma, pri moq test pri obhojdane *+- nai tejkata stoinost na k izleze da e 9786 Link to comment Share on other sites More sharing options...
ScherZ Posted January 2, 2004 Author Share Posted January 2, 2004 ScherZ: q se predstavi V kakyv smisal da se predstavq????? Link to comment Share on other sites More sharing options...
tedy Posted January 2, 2004 Share Posted January 2, 2004 Значи направих и този тест, furiozo, с броя итерации за най-бавното К. Онова с времето беше просто приблизително. Оказа се, че цели 66 стойности на К се намират еднакво най-бавно, като последното е действително 9786 (след 26,664,030 комбинации). Теста пак завърши за 1 час и пак на компютър Duron 1.3 G. Предполагам програмата ми е по-бърза понеже никъде не използвам абсолютно никакво делене (с изключение накрая само при извеждането на total time да превърна милисекунди в секунди). Link to comment Share on other sites More sharing options...
furiozo Posted January 2, 2004 Share Posted January 2, 2004 ami qvno zaradi tova beshe po byrza dai i tvoq kod za da gi sravnim pri ravnostoini usloviq ama e hubavo da q napravish da vzima k ot command line parameter shtoto v linux ima komanda time s koqto se izmerva vremeto otnelo izpylnenieto na druga komanda: time ./zadacha 9786 ... real 0m32.003s user 0m32.00s sys 0m0.003s ... neshto takova Link to comment Share on other sites More sharing options...
tedy Posted January 2, 2004 Share Posted January 2, 2004 Това са двете архивчета със сорс и .exe (всичко е за Уиндоус). Тук - версията за изчисляване на единично К (с командлине параметър) Тук - версията за обхождане на всички 0<к<=10000 (без параметър) Според мен е по-добре да се сравни втората програма понеже ще се види сумарно за колко време става обхождането. В първата значение може да има скоростта на операторите за извеждане на екрана, и разликата да е в микросекунди за малките к. Програмата е на Delphi 7, не знам за Линукс дали имаш компилатор в случай че искаш да компилираш. А ти ще дадеш ли версия (.exe) за всички к до 10000 да направя сравнение и аз, или ръчно да наглася кода който си дал? Link to comment Share on other sites More sharing options...
furiozo Posted January 3, 2004 Share Posted January 3, 2004 eto go oq bench http://play.evrocom.net/dl/incoming/furioz.../zad1/zad1b.exe i toi se startira s pakametyr p (1<k<=p) na moito PC tvoq otne 36 minuti , moq 31 lyubopitno e da otbeleja che v linux gi smqta chustvitelno po bavno o_O, moje bi trqat nqkvi zli paramerti kym kompilatora, -O3 ima golqm efekt no pak e dalech ot windowskite vremena Link to comment Share on other sites More sharing options...
tedy Posted January 3, 2004 Share Posted January 3, 2004 При мен твоето .ехе завърши за 56 минути, моето за 60 (еднакви условия, процеса ползваше около 96% цпу). Признавам, малко по-бърза е твоята програма Ще взема да преведа моята на С и да пооптимизирам колкото може и да видя, може пък компилатора на Паскал (Делфи) да внася разлика. Link to comment Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.