diff options
4 files changed, 678 insertions, 0 deletions
| -rw-r--r-- | src/teaching/oop-2023/index.md | 1 | ||||
| -rw-r--r-- | src/teaching/oop-2023/week1/good-software.md | 519 | ||||
| -rw-r--r-- | src/teaching/oop-2023/week1/index.md | 97 | ||||
| -rw-r--r-- | src/teaching/oop-2023/week1/organization.md | 61 |
diff --git a/src/teaching/oop-2023/index.md b/src/teaching/oop-2023/index.md index bbc7b8e..4c5e195 100644 --- a/src/teaching/oop-2023/index.md +++ b/src/teaching/oop-2023/index.md @@ -14,3 +14,4 @@ |№|Дата|Материали| |-------|----|---------| +|1 |22.02.2024|[Организационно](./week1/organization.html?a) \|\| [Основни добри софтуерни практики](./week1/good-software.html?a) \|\| [Задачи](./week1/) \|\| [GitHub classroom](https://classroom.github.com/a/UPJOzHty)| diff --git a/src/teaching/oop-2023/week1/good-software.md b/src/teaching/oop-2023/week1/good-software.md new file mode 100644 index 0000000..9e2e833 --- /dev/null +++ b/src/teaching/oop-2023/week1/good-software.md @@ -0,0 +1,519 @@ +# Основни добри софтуерни практики - ООП, Седмица 1, 22.02.2024 + +Миналия семестър не ни стигна времето да обсъдим домашното по-сериозно. +Главния проблем, който забелязах, беше колко грозно и нагласено бяха написани решенията. +Като въведение в ООП, ще поговорим по тази тема. + +&&presentation + +&&clide &¢ered &&font35 + +# Основни идеи<br>при добро писане на код + +&&/font &&/centered &&/clide + + + +&&slide &&font35 + +## Какво прави програмиста с чужд код? + +&&lineb4 + +1. Чете +2. Разучава как се ползва/какво прави +3. Използва го/Модифицира го + +Добър код прави тези задачи лесни! + +&&/font &&/slide + + + +&&slide &&font35 + +## Подобряване на четене + +&&lineb3 + +- Лично вярвам, че четимост е по-важна от конвенции +- Човек вижда най-лесно "контрастни" шаблони + + +``` + . . 0.00.0 010010 815213 + 000000 000000 738438 +. . .0000. 100001 122481 + .... 0....0 011110 511119 +``` + +&&/font &&/slide + + + +Както виждате, в примера има усмихнато личице, "закодирано" по различни начини. +С точка и шпации е най-ясно, като заменим шпациите с нули става по-неясно, като заменим точките с единици става още повече и като заменим нулите със случайни не-единични цифри, става пък съвсем невидимо. +Важното е шаблона да се намира в среда на други шаблони, иначе трудно се забелязва. + +При код, ще илюстрирам идеята си с един пример, но няма да задълбавам, следващата секция е много по-важна. +Пък и тази тема е малко религиозна и ще чувате различни мнения според човека който питате. + + + +&&clide + +Труден за четене код *(забелязвате ли грешките?)*: + +&&font22 + +``` +int a, b; +std::cout << "Enter coordinates" << std::endl; +std::cin >> a; +if (a == -1) return layerNavigation(board, rows, cols, layers); +if (a < 0 || a >= rows || b < 0 || a >= cols) return false; +for (int i = 0; i < layers; i++) { +if (board[a][b][i] == ' ') { + for (int j = 0; j < 8; j++){ + if (enptyRow[j] != ' ') { + emptyRow[j] = board[a][b][i]; + board[a][b][i] = ' '; + return true; + } + } + return false; +} +} +``` + +&&/font &&/clide + + + +Нарочно съм премахнал оцветяването, то драстично помага, но тук повече се интересуваме от "формата" на код. + +Вмъкнал съм три грешки: едно нещо липсва, има една печатна и една логическа грешка. +Разбира се, ако се зачетете дума по дума сигурно ще ги откриете, но сега да сравним. + + + +&&clide + +По-лесен за четене код *(а сега виждат ли се по-лесно?)*: + +&&font18 + +``` +std::cout << "Enter coordinates" << std::endl; +int a, b; + +std::cin >> a; +if (a == -1) { + return layerNavigation(board, rows, cols, layers); +} + +if (a < 0 || a >= rows || b < 0 || a >= cols) { + return false; +} + +for (int i = 0; i < layers; i++) +{ + if (board[a][b][i] == ' ') + { + for (int j = 0; j < 8; j++) + { + if (enptyRow[j] != ' ') { + emptyRow[j] = board[a][b][i]; + board[a][b][i] = ' '; + + return true; + } + } + return false; + } +} +``` + +&&/font &&/clide + + + +Би трябвало да е малко по-лесно, в последния `if` имаме "e**n**ptyRow", което е печатната грешка, `!=` което трябва да бъде `==` и липсва въвеждането на `b` след първия `if`. + +Примерът не е перфектен, но илюстрира какво се опитвам да кажа: формата на код е от огромно значение, обръщайте ѝ внимание. + + + +&&slide + +## Абстракцията - улеснява изучаване И употреба/модификация + +&&lineb1 + +- Разделяме обработване на стойностите от директната имплементацията +- Създаваме нови "машинни инструкции" + +&&lineb1 + +- `doX()` е по-лошо от `do(X)` + - можем да преизползваме `do()` за неща, различни от `X` + - един път разбрано, всяка употреба на `do()` също е разбрана; този стил кара `do()` да бъде по-обща функция, което я прави по-лесна за разбиране + - модификация на `do(X)` се свежда до заменяне на `do()` с `doOther()` или до заменяне на `X` с `Y`; променяме "инструкцията" или променяме данната + +&&/slide + + + +Нека сега разгледаме няколко примера, първият е много груб и елементарен, но служи за добро начало: + + + +&&clide + + +```cpp +Лошо - doX() │ Добро - do(X) + │ +int fib5() │ int fib(int n) +{ │ { + int prev = 0, curr = 1; │ int prev = 0, curr = 1; + for (int i = 1; i < 5; i++) │ for (int i = 1; i < n; i++) + { │ { + int tempPrev = prev; │ int tempPrev = prev; + prev = curr; │ prev = curr; + curr = curr + prev; │ curr = curr + prev; + } │ } + return curr; │ return curr; +} │ } +``` + +&&/clide + + + +Би трябвало да е супер очевидно, никой няма да пише отделна функция на Фибоначи за всяко число. + +Нека сега да разгледаме няколко "реални" примера, свързани с домашното (за припомняне, условието се намира [тук](https://learn.fmi.uni-sofia.bg/mod/assign/view.php?id=296069)). +Самите решения няма винаги да са добре форматирани, това е направено с цел да се поберат добре в слайда. + +Първия е върху функция, която приема координатите на плочка, премахва я от дъската (ако съществува) и я слага в края на празния ред. + + + +&&slide + +Лошо - `doX()` в тялото на функцията + +```cpp +void tryTakeTile(char** board, int rows, int cols, + char emptyRow[8]) { + int x, y; + std::cin >> x >> y; + if (x<0 || x>=rows || y<0 || y>=cols || board[x][y] == ' ') { + std::cout << "Invalid coordinates!" << std::endl; + } + else { + int emptyRowIndex = -1; + for (int i = 0; i < 8; i++) { + if (emptyRow[i] == ' ') { + emptyRowIndex = i; + break; + } + } + emptyRow[emptyRowIndex] = board[x][y]; + board[x][y] = ' '; + } +} +``` + +&&/slide + + + +Повечето предадени работи са имплементирали функционалността по точно този начин. +Замислете се обаче, какво става ако сменим типа данна, тоест ако дъската е триизмерна? +Тогава трябва да добавим още една `int` променлива, още едно условие в `if`, трябва да я добавим при трите индексирания на `board`. + +Какво става ако променим самата структура от данни за `emptyRow` (за сега сте учили само масиви, но скоро ще видите, че има и други начини да съхраняваш редица информация), тогава ще трябва да пренапишем целия цикъл. + +Тоест, ако променим нещо, трябва да пренапишем значителни части от самия код, и като разширим това върху 10-20 функции, изведнъж малка промяна става голяма. +Нека сега да пренапишем функцията, използвайки колкото се може повече абстракция. + + +&&clide + +Добро - `do(X)` + +```cpp +bool tryReadCoordinates(int& x, int& y) { + std::cin >> x >> y; + if (!availablePosition(board, rows, cols, x, y)) { + std::cout << "Invalid coordinates!" << std::endl; + return false; + } + return true; +} + +void tryTakeTile(char** board, int rows, int cols, + char emptyRow[8]) { + int x, y; + if (tryReadCoordinates(x, y)) { + appendToArray(emptyRow, 8, board[x][y]); + board[x][y] = ' '; + } +} +``` + +&&/clide + + + +Искаме трето измерение на `board`? +Няма проблем, написали сме нова `tryReadCoordinates`, която приема три променливи, и в `tryTakeTile` добавяме една декларация и обновяваме двете индексирания на `board`. +Ако `emptyRow` стане друг тип данна, просто променяме функцията да бъде `appendToOtherDataType` и сме готови. + +И ако тази промяна трябва да се направи в много функции, даже бихме могли да употребяваме функционалност на самия текстов редактор да търси и заменя срещания на един низ с друг. + +Нека сега да увеличим сложността още малко, да разгледаме функция за генерирането на дъската. +Отново, повечето предадени решения изглеждаха подобни на примера. + + + +&&slide + +Лошо - всички цикли са `doX()` + +```cpp +void generateLayer(char** layer, int rows, int cols, + char* tiles, int* tileCounts, int tilesSize) { + for (int i = 0; i < rows; i++) { + for (int j = 0; j < cols; j++) { + layer[i][j] = ' '; + } + } + for (int i = 0; i < tilesSize; i++) { + for (int j = 0; j < tileCounts[i]; j++) { + int x, y; + do { // randNum(x,y) връща случайно число∈[x,y] + x = randNum(0, rows - 1); + y = randNum(0, cols - 1); + } while(layer[x][y] != ' '); + layer[x][y] = tileCounts[i]; + } + } +} +``` + +&&/slide + + + +Стария проблем, някакви цикли, ако искаме да променям някоя данна или как нещо работи, трябва да пренапишем половината функция. + +Този сегмент е по-интересен за променяне от преди, понеже за да го направим хубаво трябва да променим самата ни логика. +Запълването със шпации е ясно, обаче случайното поставяне на плочки не е. + +Ако имаме функция `placeRandomЕлемент` която само поставя една плочка в слоя, пак ще имаме вложени цикли, трябва да има начин да останем с един цикъл. +Ако направим `placeRandomElementNTimes`, тогава пък абстрахираната функция става твърде специфична и вече имаме `doX()` при самата нея. + +Чрез функционално програмиране този проблем може да се разреши лесно, обаче вие ще го учите следващия семестър. +С достатъчно размишления, може да стигнем до следния вариант: вместо всяка плочка да я поставяме на случайна позиция, защо не поставим всички плочки една след друга и не разбъркаме слоя? + + + +&&clide + +Добро - `do(X)` + +```cpp +void generateLayer(char** layer, int rows, int cols, + char* tiles, int* tileCounts, int tilesSize) { + fillMatrix(layer, rows, cols, '\0'); + for (int i = 0; i < tilesSize; i++) { + // appendToMatrix(mat,rows,cols,fill,max): + // замества първите (най-много) max празни клетки с fill + // връща колко клетки наистина е заместило + appendToMatrix(layer, rows, cols, + tiles[i], tileCounts[i]); + } + shuffleMatrix(layer, rows, cols); +} +``` + +**Бонус:** работи по-коректно от преди + +&&/clide + + + +В предходния вариант, ако примерно цялата е пълна освен една клетка, и трябва да поставим една финална плочка, тогава трябва да чакаме докато случайните стойности се напаснат точно с координатите на тази една клетка. +Това може да се случи след половин секунда, но може да отнеме и един час докато се случи. +Даже, този проблем става все по-тегав с времето: с всяка запълнена клетка, шанса случайните стойности да ударят на заети координати се увеличава. + +Докато тук, нямаме този проблем, отнема някакво консистентно предопределено време да разбъркаме матрицата. +Как имплементираме `shuffleMatrix` си има и своите тънкости, но най-елементарния начин е просто да направим сортираш алгоритъм, при който вместо да сравним две стойности, използваме случайна стойност, която определя дали ще разменим плочките. + +Друго хубаво нещо на решения с абстракция, е един лек лавинен ефект, където веднъж като почнем да мислим за абстракции, намираме къде да ги ползваме навсякъде. +Да разгледаме същата функция, обаче при D подточка. + + + +&&clide + +Решения със слоеве правят същото. Лошо - `doX()` при циклите: + +```cpp +void generate(char*** board, int rows, int cols, int layers, + char* tiles, int* tileCounts, int tilesSize) { + ... + do { + x = randNum(0, rows - 1); y = randNum(0, cols - 1); + layer = randNum(0, layers - 1); + } while(layer[x][y][layer] != ' '); + ... +} +``` + +&&/clide + + + +Без абстракция отново ще пренапишем голяма част от `generate` функцията, за да се побере на слайда съм оставил само "най-сложната" промяна - случайните стойности. +Пак, имаше решения на подточката, без преизползване на `generate` за един слой. +Айде да разгледаме решението, заедно с абстрахираната `generate`. + + + +&&slide + +Добро - `do(X)` + +```cpp +void generateLayer(char** layer, int rows, int cols, + char* tiles, int* tileCounts, int tilesSize) { + fillMatrix(layer, rows, cols, '\0'); + for (int i = 0; i < tilesSize; i++) { + int actuallyAppended = + appendToMatrix(layer, rows, cols, + tiles[i], tileCounts[i]); + tileCounts[i] -= actuallyAppended; + } + shuffleMatrix(layer, rows, cols); +} +void generate(char*** board, int rows, int cols, int layers, + char* tiles, int* tileCounts, int tilesSize) { + for (int i = 0; i < layers; i++) { + generateLayer(board[i], rows, cols, + tiles, tileCounts, tilesSize); + } +} +``` + +&&/slide + + + +Супер елементарно, има-няма 5-6 реда код промяна, при генериране за всеки слой, просто извикваме функцията за генериране върху един слой, за всеки слой. +А в самата функция само премахваме броя вмъкнати плочки от сумата на даден тип. + +Наблюдателните са забелязали, че в "ръчното" решение слоевете са третия индекс, тоест имаме `board[x][y][layer]`, докато в това решение е първия, тоест `board[layer][x][y]`. +Разликата е значителна, но от гледна точка на код, особено когато използваме абстракция, промяната е лесна. + +Иначе, в момента се намираме в много добра позиция, без абстракция как правим рестартирането на играта? +По условие броя и типовете плочки трябва да се запазят, но позиции не. +Истината е, че става малко тромаво: цикълът за намираме на позиции се преизползва, и броя плочки трябва да се запази. + +Обаче, сега това става с едно `shuffleMatrix`, не е нужно нищо специално да правим! + + + +&&clide &&font35 + +### Абстракцията - подобрява и коментари + +- Целта на коментарите е да направи разбиране и модификация на код по-лесни. +- В повечето случаи, коментарът трябва да ни дава *нова* информация или да *свърже* парчета информация + +&&/font &&/clide + + + +Да разгледаме следния пример. + + + +&&clide + +Лошо: + +```cpp +// Fill matrix with '\0' +for (int i = 0; i < rows; i++) { + for (int j = 0; j < cols; j++) { + matrix[i][j] = '\0'; + } +} +``` + +Добро: + +```cpp +// Prepare matrix for functionX +// (for which empty cells are '\0') +for (int i = 0; i < rows; i++) { + for (int j = 0; j < cols; j++) { + matrix[i][j] = '\0'; + } +} +``` + + +&&/clide + + + +При добрия вариант, получаваме нова информация, че това запълване се случва понеже ще подаваме към някаква си `functionX`, и че евентуално може да има други функции, при които празни клетки може да не се обозначават с `'\0'`. +В лошия можем да стигнем до същото заключение като погледнем самия код. + +<!-- +<br> + +Всичко това е много хубаво, обаче цитирайки Дийкстра, малки изолирани примери не са достатъчни: + + + +&&clide + +> For practical reasons, the demonstration programs must be small, many times smaller than the "life-size programs" I have in mind. My basic problem is that precisely this difference in scale is one of the major sources of our difficulties in programming! + +— Edsger W. Dijkstra, [Notes on Structured Programming, On our inability to do much](https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF) + +&&lineb1 + +Решение на цялото домашно, с описаните методи TODO + +&&/clide + + + +Окуражавам ви да разгледате решенията, да ги сравните с вашите и поне да придобиете някаква интуиция за нещата. +Така да мислиш не е лесно, отнема време и усилия. +--> + +Умението да разрешиш един проблем *не те* прави добър програмист, да го разрешиш по четим, разширяем, лесен, ефикасен, ... начин *те* прави добър програмист. + + + +&&slide &&font35 + +## Изводи + +&&lineb4 + +- Форматирайте/подравнявайте си кода, искате лесно четене +- Вдигайте абстракция + - Обширни функции > код за конкретни стойности + - Преизползване на възможно най-много код + - Коментари които дават или разширяват знание + +&&/font &&/slide diff --git a/src/teaching/oop-2023/week1/index.md b/src/teaching/oop-2023/week1/index.md new file mode 100644 index 0000000..9b94e18 --- /dev/null +++ b/src/teaching/oop-2023/week1/index.md @@ -0,0 +1,97 @@ +# Задачи - ООП, Седмица 1, 22.02.2024 + +GitHub classroom: [classroom.github.com/a/UPJOzHty](https://classroom.github.com/a/UPJOzHty) + +## Задача 1 + +Имплементирайте чрез структура низ. +В структурата трябва да запазвате указател към низа и неговата дължина. + +Имплементирайте функция `concatString`, която приема две структури от този тип и връща низ, пак в същата структура, който е конкатенация (слепване) на първите два низа. + +&&question Има ли значение дали типовете на аргументите, или на върнатата стойност, са референции или указатели (или нито едното)? + +В самия код тествайте функциите (не е нужен потребителски вход). + +## Задача 2 + +Имплементирайте структура за динамично-заделен масив от целочислени числа. +Тя трябва да запазва указател към масива, размера на масива и бройката на елементи в масива. + +Заделянето на динамична памет е бавна операция, затова винаги ще заделяме повече клетки, отколкото са ни нужни. + +Имплементирайте функция `resize`, която удвоява размера на масива (нека първоначалния размер на масива е 2), на подадена стойност от тип вашата структура. + +Имплементирайте функция `addToEnd`, която приема (инстанция на) структурата ви и вмъква елемент в първата незаета позиция. + +В самия код тествайте функциите (не е нужен потребителски вход). + +## Задача 3 + +Разглеждате "пакети" (логове) информация от редица датчици. +Един пакет запазва времето, когато информацията е била отчетена от датчиците, и стойностите на всички датчици: температура, атмосферно налягане, влажност и надморска височина. +Всички типове данни са целочислени. + +От входа получавате N, броя пакети, които трябва да запазите, и след това 5N на брой целочислени стойности. +Накрая получавате буква: `t`, `p`, `h`, `e`, всяка съответства на някоя отделна стойност от датчиците. + +Трябва да изкарате на екрана всичките стойности от пакетите, подредени в нарастващ ред на времето, като всички след първата са разликите им спрямо първата. + +**Пример:** + +|Вход|Изход| +|----|-----| +|6<br>56 45 64 -8 98<br>14 40 -15 -18 -1<br>22 89 72 62 4<br>85 44 60 17 13<br>75 18 -12 48 21<br>27 10 94 -5 16<br>p|-15 87 109 79 3 75| + +## Задача 4 + +Направете структура за съхранение на полети[^sabre]. +Трябва да запазите имената на началния и крайния град като низове (допускаме, че няма шпации в имената на градовете), часът на излитане и на кацане в целочислен формат (като на циферблат на дигитален часовник, без разделителното двоеточие) и цената на полета в тип с плаваща запетая (в долари). + +### а) въвеждане + +От входа получавате N, това определя броя полети, които трябва да се добавят в системата. +Всеки полет е редица от 5 стойности, в реда в който са дефинирани. + +*Напомням, че това е нагласено да ползвате `std::cin` вместо ръчно да обработвате целия ред.* + +Изкарайте началните и крайните градове, както и цената на полетите, подредени в нарастващ ред на час на излитане. + +**Пример:** + +|Вход|Изход| +|----|-----| +|5<br>Berlin Paris 1105 1255 140<br>Sofia Paris 0915 1115 140<br>Paris NewYork 1225 1610 500<br>Sofia NewYork 0610 1345 800<br>Sofia Berlin 1020 1130 200|Sofia NewYork 800<br>Sofia Paris 140<br>Sofia Berlin 200<br>Berlin Paris 140<br>Paris NewYork 500| + +### б) търсене + +След като се въведат всички полети, получавате от входа два низа - имена на градове. +Трябва да изкарате най-евтиния, и след него най-бързия, вариант за пътуване от първия град към втория. + +Прикачване между полети е позволено, така че под "вариант" трябва да изкарате всичките полети, които са решение. +За един полет е нужно да изкарате само началния град, крайния град, час на излитане и цена, като градовете трябва да са подредени в нарастващ ред на часа на излитане. + +**Пример:** + +|Вход|Изход| +|----|-----| +|5<br>Berlin Paris 1105 1255 140<br>Sofia Paris 0915 1115 140<br>Paris NewYork 1225 1610 500<br>Sofia NewYork 0610 1245 800<br>Sofia Berlin 1020 1130 200<br>Sofia NewYork|Cheapest:<br>Sofia Paris 0915 140<br>Paris NewYork 1225 500<br>Quickest:<br>Sofia NewYork 0610 800| + + +## Задача 5 + +Имате система за потребители, всеки потребител си има име и приятели (един приятел е **указател към потребител**). + +В началото се въвежда N, това е броят потребители в системата. +За един потребител, първо се въвежда на нов ред името му, след това броя на неговите приятели и накрая, на отделни редове, имената на всички тези приятели. + +Накрая получавате едно име, това е началния потребител. +Трябва да намерите, започвайки от него, с колко други потребителя има някаква приятелска връзка (директна, приятел на приятел, приятел на приятел на приятел, ...). + +**Пример:** + +|Вход|Изход| +|----|-----| +|5<br>Георги<br>2<br>Асен Гьонов<br>Майстора<br>Асен Гьонов<br>2<br>Георги<br>др. Божидаров<br>Майстора<br>1<br>Георги<br>др. Божидаров<br>1<br>Асен Гьонов<br>Павел<br>0<br>Майстора|3| + +[^sabre]: Защото една от първите индустрии, които са се нуждаели от компютърни системи, била [авиационната индустрия](https://en.wikipedia.org/wiki/Sabre_%28travel_reservation_system%29#History). diff --git a/src/teaching/oop-2023/week1/organization.md b/src/teaching/oop-2023/week1/organization.md new file mode 100644 index 0000000..866b93a --- /dev/null +++ b/src/teaching/oop-2023/week1/organization.md @@ -0,0 +1,61 @@ +# Организация - ООП, Седмица 1, 22.02.2024 + +&&presentation + +&&clide &¢ered &&font35 + +# Добре дошли в ООП + +&&/font &&/centered &&/clide + + + +За разлика от Увод в програмиране, по ООП практикума е малко по-специален. + + + +&&clide &&font35 + +- ООП практикум е избираема, която няма смисъл да не запишете + - Само плюсове за вас +- Оценката е според контролни/изпити по ООП + +&&/font &&/clide + + + +Така ви помагаме с избираемите: по учебен план трябва да имате поне 2 практикума, сравнително безплатно получавате единия. +Относно оценяване: + + + +&&clide &&font35 + +- Освобождаване от изпит според работата ви по време на практикум +- Няма намаляване на оценка +- Оценявам общите ви умения<br> + Важното е да умеете да сте програмисти: коректност, брой и трудност на решени задачи се зачитат по-малко отколкото успех да напишете прилично-изглеждаща програма (дори с малко мой тласък) + +&&/font &&/clide + + + +Все пак не може да ви даваме безплатни оценки, затова: + + + +&&clide &&font35 + +- Зачитат се **единствено нещата, качени в GitHub classroom, качени в срок** + - До **15** минути след края на часа +- Както преди, не е нужно да присъствате, за да качвате решения +- Ако случайно някой не знае как се ползва: + +&¢ered [syndamia.com/upp-2023/week1/setup.html?a](../upp-2023/week1/setup.html?a) &&/centered + +&&/font &&/clide + + + +Който по време на УП е използвал GitHub classroom не би трябвало да прави нещо, продължавате си по старо му, със същите акаунти. +Разбира се, за всякакви проблеми се [свържете с мен](../upp-2023/week1/welcome.html?a#section-4). |