Loading...
tosilv avatar tosilv 69 Точки

[Homework] Структури от данни - Linear Data Structures

Здравейте колеги. Дайте да сравним 8-ма задача.

Мойта е ето тук - цък, като направих и глупав генератор на по-големи матрици за да видя колко зле стават нещата нагоре. 

Тагове:
3
Структури от данни и алгоритми 05/07/2015 18:45:00
DHristoskov avatar DHristoskov 211 Точки

Ето и моите задачи от  домашното по структура от данни. Вътре е включена и въпросната 8-ма задача "Distance in Labyrinth", направил съм я по друг начин, защото в учебника има упътване как да се реши. Аз съм се придържал към него. Също да уточня, че съм решил всички задачи като основно ползвам LINQ и от към скорост на изпълнение не са много добре, но не видях да има условие за времето за изпълнение.

GitHub link to Linear Data Structures HomeWork

6
04/07/2015 20:05:46
tosilv avatar tosilv 69 Точки
Както винаги се сещам за по-сложният вариант за обикаляне :D. Интересно колко по-бърз е начина от учебника, ще го проверя като има време.
0
enevlogiev avatar enevlogiev 1168 Точки

"Също да уточня, че съм решил всички задачи като основно ползвам LINQ и от към скорост на изпълнение не са много добре"

@DHristoskov,
Не му се притеснявай на линк, ползвай си го с кеф, защото е много лесен за писане и четене. Освен това е достатъчно бърз. Ако някоя програма трябва наистина да е хипер-гига бърза, може би не точно код, който върви върху виртуална машина е решението, така че линк ти е последната грижа.
 

1
ttitto avatar ttitto 1153 Точки

@DHristoskov : Нещо Add методът на задача 7 LinkedList не работи правилно и връща с едно по-малко. Пуснах моите тестове върху твоя проект, защото видях, че си се постарал доста, обаче всичките гърмят заради Count пропъртито.

1
06/07/2015 01:05:12
plamen.yovchev avatar plamen.yovchev 5 Точки

За да не отваряме излишни теми за задачки от по 5-6 реда искам да питам тук.

На 3та LongestSubsequence пише да се напише програма, която проверява дали задачата работи коректно. UnitTest ли трябва да се напишат ?

0
ttitto avatar ttitto 1153 Точки

Не. Достатъчно е да използваш метода в конзолно приложение по такъв начин, че да е очевидна коректността му. Идеята е да е по-лесно за проверяващите на домашното и без да пишат допълнителен код за тестване да се убедят, че методът работи.

1
05/07/2015 16:54:25
plamen.yovchev avatar plamen.yovchev 5 Точки

Мерси, ама то това го пише само за 3та задача, а другите?

0
ttitto avatar ttitto 1153 Точки

Никъде не се изискват задължително Unit Tests. Обаче ти препоръчвам поне за имплементациите на двата списъка (зад. 6 и 7) да си направиш тестове. Аз си направих и бях изумен колко допълнителни неща трябваше да поправя по моята имплементация. 

0
ttitto avatar ttitto 1153 Точки

Ето линк и към моето почти пълно домашно. Последната задача ще я пиша малко по-късно. 

Поиграх си да напиша юнит тестове за 6та и 7ма задача. Можете да ги ползвате за тестване на вашите имплементации. Бих се радвал, ако добавите още случаи за тестване, които евентуално съм изпуснал.

2
dim4o avatar dim4o 288 Точки

Здравей,

Поздравления за мерака да правиш юнит тестове. Аз за пръв път ползвах такива в упражненията на лекцията. Не знам как точно се пишат и дали ще имаш възможност да добавиш следния тест, за да изгладиш един бъг, който смятам че имаш:

SingleIndexedLinkedList<int> list = new SingleIndexedLinkedList<int>();

list.Add(1);
        list.Add(2);  list.Add(3); list.Add(4); list.Add(5);list.Add(6); list.Add(7);
        // 1 2 3 4 5 6 7
        list.Remove(2);
        list.Remove(3);
        list.Remove(4);
        // 1 2 4 6
        list.Add(8);
        // 1 2 4 6
        list.Add(9);
        // 1 2 4 6 

Идеята е, че след като махнеш опашката листа ти си я "забравя" и трябва да му я припомниш. Преди това трябва да си махнал някои елементи по средата преполагам. Unit-ите сигурно тестват отделни поведения(поправи ме ако греша), което може да е предимство, но може и да е недостатък, защото когато работим динамично могат да се появят непредвидини комбинации.

Тази маневра с припомнянето не се налага при двусвързан списък. И при едносвързан може да се мине без нея, но цената е долу-горе същата или по-лоша.

2
06/07/2015 13:39:15
krach avatar krach 65 Точки

Давам и моя вариант за задача 7 ако някой му се гледа и да каже слаби места

 

https://codeboard.io/projects/7127

0
ttitto avatar ttitto 1153 Точки

@ dim4o : Много благодаря за корекцията. оправих грешката и добавих тест и за този случай. 

По въпроса за  юнит тестовете: Аз лично ги намирам за много полезни и виждам само една основателна причина да не се пишат - оскъпяват продукта и не всички клиенти искат да плащат за тестове.

0
dim4o avatar dim4o 288 Точки

Пускам и моето домашно -> LinearDataStructures. Сигурно няма да имам време да мисля много оптимизации. Направих всичко по първия начин по който се сетя. Следователно, ако забележите някакво несъответствие или имате градивни съвети - това би ми било от голяма полза. Иначе впечатленията са ми, че задачите засега не са много трудни. От 1 до 5 са на ниво CSharpBasics, 6 и 7 спокойно могат да се дадат за домашно по ООП, а за 8-ма само трябва да се сетиш. че числото в клетката трябва да е дълбочината на нивото при обхождане в ширина спрямо стартовата позиция. Обхождането съм го направил с опашка, защото с рекурсията при дебъгване понякога човек може да изпадне в големи филми.

 

1
krach avatar krach 65 Точки

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

0
dim4o avatar dim4o 288 Точки

Завизи какво си обхождал. В случая на зад.8  имаме граф с ниска степен на свързаност. Броят на възлите V=n^2, а на ребрата е Е=2n(n-1), следователно сложността е О(V + E) = O(3n^2-2n), което за малки n e ОК. Но ако имаш мн висока степен на сързаност и обхождаш нещо с мн разклонения ще зациклиш. Например при обхождане на хиперлинкове в нета ще завизнеш още на 2-3 ниво в дълбочина, а може и по-рано. А ако ти хвърля exception веднага това в повечето случай значи, че рекурсията няма дъно. Мисля, че компилаторите понякога се усещат още преди да са потънали докрай :). Такива са ми впечатленията на мен.

0
06/07/2015 19:03:39
ttitto avatar ttitto 1153 Точки

@dim4o: Чудесно стегнато решение на BFS задачата. Само едно нещо ми се струва да не си е на мястото. Мисля че маркирането на клетките с u, x и номера на стъпката не трябва да се случва в принт метода, а трябва да намери място в самия CalcDistance метод. Принтирането трябва да си е само принтиране.

0
Kamenov avatar Kamenov 18 Точки

Здравейте, някой може ли да ми обясни какво се иска от 4 задача, защото не мога да разбера много добре?

0
enevlogiev avatar enevlogiev 1168 Точки

Трябва да разкараш всички числа, които се повтарят нечетен брой пъти.

1 1 1 2 2 - разкарваш 1, резултат  2 2
1 1 2 2 - нищо не разкарваш

1 2 1 2 1 2 - и 1, и 2 се повтарят нечетен брой пъти, затова разкарваш всичко и в резултат не печатиш нищо

1
06/07/2015 20:01:11
ttitto avatar ttitto 1153 Точки

От подадените числа да определиш кои се срещат нечетен брой пъти в цялата последователност и да ги премахнеш

 

1
nikola.m.nikolov avatar nikola.m.nikolov 830 Точки

Ето моите решения на първите 5 задачи. За останалите нещо времето не стига за сега. Всички ги реших с LINQ. Знам че е бавен, но в това домашно не видях да се търси performance. 

Lists

0
aivian avatar aivian 51 Точки

Имам проблем с 6 - та задача. Направих array-based ReversedList<T> и му зададох DefaultCapacity = 4. Като си създам нов ReversedList  и ми запълва тези 4 места с нули, и примерно, съм Add - нал 1 и 2, и като итерирам ми изписва на конзолата:

0

0

2

1

Как мога да премахна това нещо? http://pastebin.com/1Jhhht4v

0
10/07/2015 20:28:09
tosilv avatar tosilv 69 Точки

Във енумератора си ползвай this.Count вместо размера на обекта. 

0
10/07/2015 20:42:17
aivian avatar aivian 51 Точки

Това ли имаш предвид: http://pastebin.com/HdPGJPrR. Сега цикъла ми връща:

0

0

Дебъгвах и достигнах да извода, че листа се създава с 4 нули - значи не е от енумератора, но не виждам от къде идва цялата работа.

0
milen_vm avatar milen_vm 68 Точки

По default стойноста на int променлива е 0, т. е. след като инициализираш списък или масив от int-ове и в него още не си записал никакви стойности, то на всички позиции се записва default-ната стойност за int - 0. Това условие this.elements[i] == null в твоя случаи не вярно, че да се break-не цикъла.

Тъй като списъкът по условие е reversed трябва да го циклиш отзад напред, когато имплементираш IEnumerator<T> GetEnumerator и не до Capacity а до броя записани елементи - Count

0
10/07/2015 21:32:33
creature5 avatar creature5 17 Точки

Здравейте колеги , реших задачите ама забравих да ги пратя в сайта :( . Ако на някой му се занимава да им хвърли един поглед и да си каже мнението .

На java съм писал.

http://arnaudov.net/upload/uploaded/all.rar

Благодаря предварително

1
bsdemon avatar bsdemon 348 Точки

Ти не си забравил, ами времето не е нагласено правилно. Трябва да е до 12/07/2015 23:59:59

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.