Отиди на страница:
| онзи, мерси много, но алгоритъмът ти е О(n*(n*log(n))), което не постига условието. Просто е, но требва да се мисли. Подсказване - раздели поредицата на две. Задачата е пряко свързана с бързото пресмятане на гласове, например: БКП, БКП, БКП, ГЕРБ,ГЕРБ,ГЕРБ, Атака, Атака, Атака, Атака, Атака, Атака, Атака. |
| Onzi, Meto, нема нужда да разделящ на две или от втори цикъл. в първия проверявай текущо най-големия брой към този които е в момента. Ако е по-голям този в момента -> той става текущо максимален. Така имаш само 1 цикъл и една проверка в него (на текущия елемент към главния). Това, че са числа прави проверката супер бърза, а цикъла има само едно ++ в него -> и.е. ще е по-бърз от делене или създаване (маллок) на нов блок памет, за два масива. Ако искаш да спестиш и време, можеш да преверяваш колко елементи остават в цикъла и дали има вероятност да се измести доминантния. Тогава ще свалиш и О(н) в общ случай |
Мишо Константинов 21 Дек 2012 09:12 Мнения: 298 От: Bulgaria Скрий: Име,IP Ако някой ми обясни какво общо имат чувалите с бюлетини в ОИК с изборния резултат, нека ми се обади, за да получи награда. Ама тази дивотия ще я дъвчат до края на света, щото и ГЕРБ са много прости. И не са в състояние да разобличават дивотиите. Бюлетините попадат в чувалите СЛЕД като гласовете са преброени в секцията и СЛЕД като протоколът е подписан. В изключителни случаи съдът може да разпореди материална проверка в някоя секция, като досега резултатът почти никога не се е променял. Да видим сега конкретната дивотия. Двама абдали от ГЕРБ мъкнат чували, очевидно с желание да помогнат на някого (или просто от глупост) и в нарушение на правилата - мястото на тези точно абдали не е в ОИК (днес опозицията се опитва да набута в ОИК и РИК по няколко хиляди наблюдатели, но това е друга дивотия). Двамата абдали знаят ли какво ще каже съдът след три месеца? Те знаят ли на кои секции ще се разпореди материална проверка (това е 1 секция на 1000)? Те знаят ли на кои секции бюлетините са вътре? Те като влачат чувалите как по-точно променят съдържанието им, така че след три месеца при материалната проверка (каквато най-вероятно няма да има) да се получи резултат, който да е изгоден за ГЕРБ? Ако абдалите искат да правят нарушение, що го правят ачик и пред камерите? Ако човек е нормален и се опита да отговори на всеки един от тези въпроси ще разбере, че мъкненето на чували с бюлетини НЯМА НИКАКВО ОТНОШЕНИЕ към изборния резултат. Но к'во ли питам и аз. Древните гърци са казали, че когато боговете искат да погубят някого, просто му взимат акъла. Което и наблюдаваме. Бъдете здрави! Мишо Константинов,  |
Икономиката върви към тоталитарната система на Тодор Живков Включително и чрез икономиката - по точно най-вече чрез нея, ние вървим към, а май не вървим, а вече сме стигнали до тресавището на Натисни тук | |
Редактирано: 1 път. Последна промяна от: Езоп |
ДСБ и Костов се връщат-Спете спокойно деца! Ще се върнат когато се върне БКП, само че когато ренегатите я самосвалят.  Костов и ДСБ са концентрат на свръхренегатокрацията БСП/СДС. Тоест, те са тайното оръжие някога наричано "щитът и мечът на Партията", което ще рече, че те са преобразилите я, нейни "наследници" и са в самата глутница национални от предатели. Заедно с БСП и ДПС. | |
Редактирано: 3 пъти. Последна промяна от: Езоп |
онзи, мерси много, но алгоритъмът ти е О(n*(n*log(n))), което не постига условието. глупости. вложен цикъл немам никъде, а логаритъма не знам откъде го измъкна. между другото, вторият ти пример вече е със сортиран масив, където задачката е тривиална. а ако се опитваш да ме накараш да сортирам входния масив - тогава вече по метода merge sort имаш n*log(n) сложност. това, което съм ти показал, е два отделни цикъла - от 1 до n и от 1 до броя различни елементи в масива (ключовете на хеша). ако реша, че имам неограничена памет, мога да използвам масив от 0 до m, където m е максималният елемент от входния масив - тогава вместо хеш с компактно използване на паметта ще имам нещо, гълтащо памет като таквоз, но задачката ще е решена с 2 цикъла - от 1 до n и от 0 до m. | |
Редактирано: 2 пъти. Последна промяна от: onzi |
онзи, извинявай, бил съм прекалено суров, когато съм оценявал решението ти, отчасти защото тогава виждах двойно.  Но само отчасти. Професията ми не е програмист и не познавам пърл, но от скриптата се вижда, че използуваш вградена хаш функция на пърл. Тази вътрешна функция не е безплатна. Не знам как е осъществена вътрешно и какво допринася към сложността на алгоритъма, но предполагам, че използуването й нарушава общото изискване О(n). Но грешката е моя, защото условието позволява използуването на всякакъв език. ПП Вторият, сортиран пример няма нищо общо с условието; дал съм го, за да покажа връзката на проблема с дискусията под темата. |
Явно е необходим по-дълъг ПУЦ. Тцъ, необходима е Пернишка УТКА  Ами съставят се такива такива с невярно съдържание. Във всяка секционна комисия половината от членовете са от опозицията. Така че шашмите, доколкото и където ги има, се правят съвместно от управляващи и опозиция в един-единний строй. Ъ-хъ, всички са маскари, само гербероидите на бял кон помагат на бременни жени и надничат из оиците. Евтино размиване и преразпределяне на отговорността и вината (документирани, заснети сиреч) за последните избори, твърде евтино. Ако опозицията не може да осигури свои свестни хора в комисиите и ако не може да прати свои представители в проблемните секции, ами да духа супата. Горното, предполагам, е еманация на евроатлантическите демократични ценности. А новият Изборен кодекс поне следите ли?  МК, Вие в Оная УТКА обяснявате ли на студентите си думата почтеност? Казвате ли им, че достойният учен не се продава, за да обслужва всяка власт дори когато се състои от престъпни мутрорапони с коефициент на интелигентност под нулата? Защото той е коректив и съвест на властта, независимо коя. Как си гледате студентите в очите впрочем?  | |
Редактирано: 1 път. Последна промяна от: SvSophia |
| мето, прав си. ползва двоично търсене и ето ти го n*log(n) за първото ми предложение. но дотам. и аз не бях съобразил това - на практика написаното от мен е равномощно на сортировка. но ако не се скъпим откъм рам и цапнем 2 масива - няма проблеми  естествено, за целта трябва елементите на входния масив да са цели неотрицателни числа. и колкото по-малки, толкова по-бързо  ps с 2 масива няма нужда от втори цикъл, както и николай се е досетил. то и с хеш няма нужда де. проверката пак може да е в първия цикъл. | |
Редактирано: 2 пъти. Последна промяна от: onzi |
в първия проверявай текущо най-големия брой към този които е в момента. Ако е по-голям този в момента -> той става текущо максимален. николайдс, нали трябва текущите бройки да ги пазиш някъде. затова сложих хеш - навици, кво да правиш. пък и това наистина ми хрумна първо. хешовете в пърл са кукличка. ако искаш бързодействие, жертваш памет. и съответно, ако максималният елемент на входния масив е 1248938109834845098329087357983570981, е напълно реално да ти свърши рам-а и операционната система да почне да дращи по харда като обезумяла. което "в пъти, пъти" ще забави цялото решение на задачката. |
| Онзи, не ти требва хeш (при зададената задача) Изчисляването на хеш е много трудоемко. Зимаш масив (например в случая е за партии -> и.е. да кажем 100 елемента) int func(int[] inputArray, int inputArrayLength) { int[100] partyArray; memset(partyArray, 0, 100*sizeof(int)); int currentMaxIndex = 0; for(int i=0;i<inputArrayLength;i++) { partyArray[inputArray]++; if(partyArray[inputArray]>currentMaxIndex) currentMaxIndex =inputArrayi; } return currentMaxIndex; } Това е целия код които ти требва -> О(н), ако не искаш да сложиш предикшън функция да спреш цикъла когато ще стане невъзможно да се смени победителя. Тази фунция обаче е бавна. Двоичния вариянт ще изиска допълнителен цикъл (напълно ненужен при краен масив partyArray) Горното изглежда да е най бързия, метод, които НЕ е най-оптимизирания за памет, но това нема gолемо значение при int. Aко обаче искаш и тази оптимизация, пак не ти требва хеш, може да стане с заместване на масива с malloc, чиито алгоритъм е добре оптимизиран |
| Тоталитарната система на Тодор Живков , тая която Иван Костов с нокти и зъби се бори да спаси със статии в работническо дело. Как ни подведе тоя търгаш. |
| Koстов имаше шанс да остарее като катедрала. Избра си съдбата на цървула. Сам, воден от личния си егоизъм. Останалото е епилог и изводи, за който може да си ги направи. |
| николай, 0. написал си някаква тъпотия, която просто не работи. фактът, че въртиш цикъл, без да използваш променливата му никъде, говори достатъчно. предполагам, че си имал желание да я сложиш някъде (променливата), но си я забравил в навалицата. всъщност - не си се сетил да сложиш един интервал и затова писанието ти е минало на италик  1. не връщаш каквото трябва - иска се доминантния елемент, а не броя срещания на елемента в масива. това е тривиално, допускам, че не си допрочел условието. 2. при първоначалната задача въобще не беше ясно колко са големи стойностите на масива. точно затова литнах към хеш. още от времената, когато писах на vax (в меи ленин), мразя да препълвам рам-а с глупости. впоследствие се изясни, че задачата може да се реши с масив. виждам, че ти даже си го ограничил до 100 елемента. при това без да знаеш колко може да ти е максималният. толкова от мен. весела коледа. | |
Редактирано: 4 пъти. Последна промяна от: onzi |
| Съгласна съм с много неща от статията.Нека да престанем да се делим на леви, десни, червени, сини и т.н. Да вникнем в същността на нещата, на това което пречи на бизнеса и обществото! Върви ли държавата към тоталитаризъм!...Върви...Върви с всеки новоприет от ГЕРБ закон- административни пречки до гуша...Ами да национализират тогава частните фирми, да не се лъжем, че има пазарна икономика! |