From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar02/README.md | 92 ----------------------------------------------------- 1 file changed, 92 deletions(-) delete mode 100644 Seminar02/README.md (limited to 'Seminar02/README.md') diff --git a/Seminar02/README.md b/Seminar02/README.md deleted file mode 100644 index d1779b2..0000000 --- a/Seminar02/README.md +++ /dev/null @@ -1,92 +0,0 @@ -# Задачи за стекове 12.10.22 - -## Задача първа -Имаме низ състоящ се от английски букви и символа \*. Всеки път когато видим \* трябва да премахнем символът отляво както и самата звезда. -Пример: -* aa\* -> "a" -* erase\*\*\*\*\* -> "" -* thi\*s i\*s exampl\*e -> "ths s exampe" - -Задачата да се реализира за линейно време с линейна памет. -## Задача втора -* Вход: Низ състоящ се от отварящи и затварящи скоби. -* Изход: Дали скобите в този низ са балансирани - -Примери: -* ((())) -> true -* ))() -> false -* )( -> false -* ()()(()) -> true - -## Задача трета -Обратен полски запис наричаме запис, в който операторите "следват" (са след) числата. Примерно изразът 3 + 4 в обратна полска нотация е 3 4 +. Или изразът 1−2+3 би изглеждал 1 2 −3+. Обикновено първо са дадени числата а след това операциите които извършваме върху тях. - -А как би изглеждал израза 1−(2+3). Тук първо трябва да извършим събирането и след това изваждането. Тоест израза се записва като 123+−. Предимството от тази нотация е, че нямаме нужда от скоби, което ускорява сметките. Нашата задача е да напишем функция, която приема валиден стринг в обратна полска нотация и връща пресметнатия резултат. - - -# Монотонни стекове -Монотонен стек наричаме стек, чиито елементи са монотонно растящи или намаляващи. Монотонните стекове имат приложения върхо много различни и интересни задачи върху масиви. - -```cpp -void monotonicStackExample(const std::vector& v) { - // Нека v = {4, 1, 2, 6, 7, 3} - // В стека можем да пазим стойности или индекси в зависимост от задачата. - // По името може да познаете какво пазим и какъв е типа на стека. - std::stack minMonotonicValues; - - for(int i = 0; i < v.size(); i++) { - while(!minMonotonicValues.empty() && minMonotonicValues.top() < v[i]) { - minMonotonicValues.pop(); - } - minMonotonicValues.push(v[i]); - } - - /* - В края на for цикъла при индекс i стека изглежда така: - (върха на стека е най - десния елемент) - i = 0 : [4] - i = 1 : [4, 1] - i = 2 : [4, 2] - i = 3 : [6] - i = 4 : [7] - i = 5 : [7, 3] - */ -} -``` -Какво можем да забележим от този пример? Примерно, вярно е, че при i = k максимума на подмасива [0..k - 1] е на дъното на стека. - -## Задача четвърта -Искаме да създадем статична структура от данни построена върху масив, която за константно време по индекс ни връща стойността на първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс. - -Пример: -> [1, 4, 3, 8, 12, 7] -* getMinLeft(0) -> -1 // няма по - голям елемент от 1 в негово ляво -* getMinLeft(2) -> 4 // 4 е първия елемент по - голям от arr[2] = 3 -* getMinLeft(5) -> 12 // 12 е първия елемент по - голям от arr[5] = 7 - -## Обяснение на решението: -От тази задача можем да си направим извода, че точно преди да вкараме елемента в монотонния стек, върха на стека е първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс. - -Защо това е вярно? -Нека - -$$arr = [a_1 \dots a_k \dots a_m \dots a_n]$$ - -и нека в цикъла i = m. Твърдя, че ако $a_k$ е първото по - голямо число от $a_m$ то ще бъде задължително на върха на стека след приключване на while цикъла. - - -Ако има други числа на върха на стека, то по предположение те са по - малки от $a_m$ и ще бъдат премахнати. - -Ами ако $a_k$ не е в стека? Ако то не е в стека то някое по - голямо от него число, намиращо се между $a_k$ и $a_m$, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво. - -## Бонус задачи -1. Да се сортира стек като използвате само един допълнителен стек. - -2. Да се направи задачата със скобите, обаче този път функцията ни казва дали е възможно низът да стане балансиран след най - много едно изтриване на скоба. - -Пример: -* )) -> false -* ()) -> true -* () -> true -* (()()() -> true -* ())) -> false \ No newline at end of file -- cgit v1.3.1-26-gb76a