[HomeWork] Структури от данни - Linear Data Structures – Stacks and Queues
Здравейте,
отварям тази тема да си проверим домашните и да обсъдим грешките по тях ако има такива.
Ето го моето домашно.
Поздрави!
Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.
Тази сутрин реших да си прочистя малко ума след краха по Database снощи :) --> Домашно: StacksAndQueues
Без Unit тестове е и за някои неща не съм изпълнявал всичко 1:1 с условието. Например не правя метод Grow(), а един метод OptimizeCpacity(), който служи за разширяване на масива и съответно за свиване когато е необходимо. За имплементациите също не съм се водил от материала от упражненията, защото още не съм ги правил. Unit-ите ще ги добавя утре.
Оносно 9-та задача могат да се направят и още неща: например да се изкарат всички най-кратки варианти, когато са повече от един, може когато за пръв път се срещне края да се спре с добавянето на повече елементи и безмисленото и нарастване. Понякога за дори малки интервали опашката може да стане много голяма и това може да се окаже значителна оптимизация.
EDIT: Добавени са и Unit тестове.
Аз да попитам защо го няма този Lab: implement an array-based stack качен ? има само за queue ??? не са го правили ли ?
Тази задача е дадена в домашното - задача 3 и 4.
Мерси :) Вярно , сега съм на 2 задача , за малко да си отговоря сам на въпроса .
На втора задача в едно завъртане на цикъла вкарваш три пъти стойности в опашката, което не генерира правилни резултати. Би трябвало на всяка итерация да се вкарва поредната стойност.
Ето моето решение - направих го с четири опашки.
Не е грешка в едно завъртане да се вкарат три стойности. Важното е колко изкарваш от опашката - само по една. Може да стане много лесно само с една опашка. Единствения недостатък е, че пълниш опашката малко повече отколкото е нужно (2*n а ти трябват n елемента само). В случая за n=50 не е голям недостатък. Пък и сложността е линейна.
Здравейте @ Petar_Ivanov ,
Относно втората задача, която сте написал до колкото разбирам условието е
- S1 = N
- S2 = S1 + 1
- S3 = 2*S1 + 1
- S4 = S1 + 2
- S5 = S2 + 1
- S6 = 2*S2 + 1
- S7 = S2 + 2
Следователно S8 = S3 +1, S9 = 2S3 + 1, S10 = S3 + 2; S11 = S4 + 1, S12 = 2*S4 + 1, S13 = S4 + 2. Според вашата имплементация всяка следваща серия е фунцкия на първото число от предходната серия. Под серия имам в предвид всяка една тройка числа, фунцкия на някое S от поредицата. По принцип, всяка серия е функция на поредното изчислено S. Tук идва ролята на опашката, където всяко изчислено S се пъха в опашката и когато му дойде времето се използва за ичисление на следващите числа от поредицата. Т.е. пази се реда на изчислените елементи, за да може да се изчилят новите. Това е смисълът да се използва опашка за решението. Надявам се да съм обяснила правило разсъжденията си, ако имате някакви въпроси, може да ги коментирате.
Здравейте,
благодаря за проверката на задачата. Оправих си грешката ето го новото решение. Моята имплементация на проблема е, че просто правя опашката на масив и вземам елемента, който ми трябва. За щастие има зависимисто между позицията на нужния елемент и итерациите на цикъла, следователно нужния елемент е на позиция n + 1.
Здравей. Малко се бях запънал на тази задача докато схвана каква е логиката на поредицата (много ги мразя такива). Прегледах ти решението и се оказа доста елементарна. Твоето решение мисля обаче, че може много да се оптимизира. Можеш в рамките на 1 цикъл да свършиш всичко по поредицата. Ето линк към моето за референции.
Така задачата не изпълнява условието да вземеш първите 50. Ти взимаш първите 102.
В условието пише да се принтират първите 50, не колко да се вземат. Решението е коректно, но определено не е най-ефективното.
Здравейте @ Petar_Ivanov ,
На 5-та задача при операцията Push(), след като добавите нов елемент, който не е първи, трябва първия елемент да стане новодобавения елемент. Т.е. this.firstNode = newNode.
Здравей,
ако погледнеш реализацията на конструктора, точно това се случва;
this.firstNode = new Node<T>(element, this.firstNode);
тук втория параметър в инициализиращи конструктор напрактика казва "на този нов елемент, които става първи елемент и следващия елемент е стария първи елемент".
На 5 задача има странен метод private void Grow() { … } , къде се ползва ? Аз написах стека без този метод и не виждам какво точно трябва да расте ?
И аз много се чудих, предполагам е останал след някакъв copy-paste на условието.
Грешка трябва да е наистина. То типичното за динамичната имплементация е, че не се грижиш за размера на стека или листа. Аз също го направих без Grow() просто защото няма какво да сложа вътре...
Има няколко грешки в кода, предоставен за тази задача, Grow() методът е една от тях.
Най-после успях да ги довърша : тук са задачите ми написани на java https://github.com/creature5/SoftUniDataStructures/tree/master/SoftUniDataStructures/src/stacksAndQueues
Колеги, вчера реших 9-та задача, следвайки упътването в условието. Там обаче е казано да проверяваме за всяко число дали е по-малко от търсеното и ако да - да продължаваме. Обаче де факто ако числото N е отрицателно, винаги има начин да стигнем до число, по-малко от текущото. Например, подават се на входа стартово число -3 и цел -5, което може да стане с две стъпки - * 2, + 1. Някой решил ли е задачата така, че да работи и в тези случаи?
И аз вчера се замислих. Сега като попита си отворих решението и успях да го направя, но може би ще трябва да го оптимизирам. След малко ще дам код.
Направил съм решението ми да намира всички shortest комбинации.
Ето моето решение за отрицателни. Реално се добавя само още едно || ..&& в if-а -> Зад.9
А на задачите със стековете - метода ToArray() трябва да връща в обратен ред или във същия ред на въвеждането елементите, които са в стека? Защото на задачата за имплементиране на стек чрез масив искат ToArray() да връща
"sub-array от elements[0....this.Count-1]", тоест така, както сме ги въвели, във същия ред. А после във Unit Tests пише, че трябва да се връщат в обратния ред. Кое е вярното?
@dim4o, TestStackToArrayAfterPushingNubers този тест метод не е ОК, не очаква елементите в правилния ред, очаква ги в реда, в който са push-нати. Трябва да ги очаква в обратния ред Last-In-First-Out
Най-краткия начин за редактиране не този метод е във втория for loop вместо това:
Assert.AreEqual(arrayWithOrigins[i], stackToArray[i]);
да кажеш така:
Assert.AreEqual(arrayWithOrigins[arrayWithOrigins.Length-1-i], stackToArray[i]);
Да, знам че е така - благодаря за наблюдението. Поправил съм и ToArray() метода, защото май не работеше като .Net-ския. Просто още не съм commit-нал в GitHub финалния вариант. Ходих да разучавам "изкуствените дървета" отблизо :)