diff options
3 files changed, 235 insertions, 13 deletions
| -rw-r--r-- | src/teaching/upp-2023/index.md | 1 | ||||
| -rw-r--r-- | src/teaching/upp-2023/week4/index.md | 29 | ||||
| -rw-r--r-- | src/teaching/upp-2023/week4/revision.md | 218 |
diff --git a/src/teaching/upp-2023/index.md b/src/teaching/upp-2023/index.md index 3d90f62..df86867 100644 --- a/src/teaching/upp-2023/index.md +++ b/src/teaching/upp-2023/index.md @@ -17,3 +17,4 @@ |1 |06.10.2023|[Добре дошли](./week1/welcome.html) \|\| [Конфигуриране на GitHub classroom и Visual Studio](./week1/setup.html?a) \|\| [Задачи](./week1/?a) \|\| [Решения](https://github.com/Syndamia/upp-2023-solutions/tree/main/week01)| |2 |13.10.2023|[Преговор](./week2/revision.html?a) \|\| [Задачи](./week2) \|\| [Решения](https://github.com/Syndamia/upp-2023-solutions/tree/main/week02)| |3 |20.10.2023|[Преговор](./week3/revision.html?a) \|\| [Задачи](./week3) \|\| [GitHub classroom](https://classroom.github.com/a/JgMSXuCf)| +|4 |27.10.2023|[Преговор](./week4/revision.html?a) \|\| [Задачи](./week4) \|\| [GitHub classroom](https://classroom.github.com/a/jqKaO1ny)| diff --git a/src/teaching/upp-2023/week4/index.md b/src/teaching/upp-2023/week4/index.md index 8c865de..0d8093b 100644 --- a/src/teaching/upp-2023/week4/index.md +++ b/src/teaching/upp-2023/week4/index.md @@ -1,9 +1,12 @@ -# Задачи - УПП, Седмица 4, 26.10.2023 +# Задачи - УПП, Седмица 4, 27.10.2023 + +GitHub classroom: [classroom.github.com/a/jqKaO1ny](https://classroom.github.com/a/jqKaO1ny) ## Задача 1 - Числен редактор -Получавате число `N`, което ще е в обхвата от 1 до TODO. +Получавате число `N`, което ще е в обхвата от 1 до 10000000000000000000. Вашата програма трябва да поддържа няколко операции върху това число, включително копиране на редица от цифри в него и поставянето им в друга част на числото. +Подробните операции ще получите по-късно, и не е нужно да валидирате вход или дали след дадена операция числото се побира в типа данни. Първо, в тази задача индексите на цифрите в едно число започват от 1 и се броят от ляво на дясно. Тоест, в числото "481395" на индекс 1 имаме 4, на индекс 2 имаме 8 и на индекс 6 имаме 5. @@ -27,13 +30,13 @@ - `remove`, която приема число, начален индекс и дължина (в този ред) Връща числото, без "дължина" на брой цифри от началния индекс - Пример: `get(481395, 3, 3)` връща `485` + Пример: `remove(481395, 3, 3)` връща `485` -- `insert`, която приема число, краен индекс, дължина и число за вмъкване - Връща числото, като на стария краен индекс намираме края на вмъкнатото число с дължина "дължина" +- `insert`, която приема число, начален индекс, дължина и число за вмъкване + Връща числото, като на началния индекс намираме началото на вмъкнатото число с дължина "дължина" Ефектът, е че числото се вмъква на дадения индекс, обаче избутва цифрите в ляво от него, вместо тези от дясно. - Пример: `insert(495, 2, 4, 1001)` връща `4910015` + Пример: `insert(495, 2, 4, 1001)` връща `4100195` ### Подточка б) Композитните функции @@ -45,7 +48,7 @@ Пример: `copy(481395, 3, 4, 2)` връща `4139581395` -- `cut`, която приема число, начален индекс, дължина и втори начален индекс +- `cut`, която приема число, начален индекс, дължина и втори начален индекс Връща числото, като "дължина" на брой цифри от (стария) начален индекс са преместени във втория начален индекс Пример: `cut(481395, 3, 4, 2)` връща `413958` @@ -80,10 +83,16 @@ |Вход|Изход| |----|-----| +|x 8504830028402847111 9 6 7|8504832840280047111| +|p 8 968824945839039458|9688249458390394588| +|a 968824945839039458 1|9688249458390394581| +|r 9938175002843839 1 10 86998385021|86998385021843839| ## Задача 2 - Умножение на полиноми Представяме полином чрез две числа, първото побитово определя дали x на конкретната степен съществува, докато второто определя коефициента (като цифра) пред всеки член, без значение дали съществува в полинома. +Тоест, старшата степен на полинома е или най-левия бит или най-лявата цифра от двете числа. +Числото с коефициенти е между 1 и 10000000000000000000. Пример: първото число е 13, a второто е 3052. Побитово `13 = 1101`, тоест ще имаме @@ -156,9 +165,3 @@ V **Упътване:** Лесно се получава, ако занулим цифрите които първия играч е посетил. Още по-лесно става ако използвате функции от първата задача. - -**Примери** - -|Вход|Изход| -|----|-----| - diff --git a/src/teaching/upp-2023/week4/revision.md b/src/teaching/upp-2023/week4/revision.md new file mode 100644 index 0000000..ce380a8 --- /dev/null +++ b/src/teaching/upp-2023/week4/revision.md @@ -0,0 +1,218 @@ +# Преговор - УПП, Седмица 4, 27.10.2023 + +&&presentation + +&&clide &&font35 &¢ered + +# Функции и алгоритмични задачи + +&&/centered &&/font &&/clide + + + +&&slide + +## От сега нататък ще направим няколко промени + +- Вместо много и лесни задачи ще давам малко и трудни задачи + - Контролното наближава, а резултата от задачата на семинара не е добър + - Моето впечатление е, че повечето които имат опит с програмиране нямат много опит с алгоритмични задачи и обратно + - Задачите ще са повече алгоритмични, лесните задачи ще виждате на семинар +- Ще изисквам добър стил при писане на код + - Това означава добре подравнен код, празни символи около оператори **и** свестни имена на променливи + - Името на променлива не трябва да бъде 150 знака, но трябва да е разбираемо какво съдържа + - **Без шльокавица!** +- Преговорът ще бъде за вас да си го четете (освен ако не трябва да преподам нещо ново) + +&&/slide + + + +*Нещата за 2s compliment се намират и в [преговора на миналата седмица](../week3/revision.html?a), ама го написах след като свърши часа, затова го копирам и тук.* + + + +&&slide + +## 2s compliment + +Интуитивно обяснение на 2s compliment. +Да приемем, че работим с тип данни, при който имаме само 3 бита. + +Как бихме ги използвали, за да представим отрицателните числа? +Най-лесния начин е да погледнем най-левия (старшия) бит, ако е 0 значи е положително, ако е 1 значи е отрицателно, тоест `010` е 2, докато `110` е -2. +Ако разпишем всичките ни числа: + +``` +111 -3 +110 -2 +101 -1 +100 -0 +011 3 +010 2 +001 1 +000 0 +``` + +&&/slide + + + +&&clide + +Това работи, обаче имаме един гигантски проблем: събирането не работи! +От математика знаем, че "2 - 1 = 2 + (-1)", тоест би трябвало да можем да съберем побитово 2 и -1 и да получим 1. +Ама, + +``` +2 + -1 = 010 + 101 = 111 = -3 +``` + +Също, знаем, че "(-1) + (-1) = -2", обаче + +``` +-1 + -1 = 101 + 101 = 1010 имаме overflow, това се съкращава на 010 = 2 +``` + +Излиза, че с тази схема не можем да събираме отрицателни числа както събираме положителни (или както събираме побитово). + +Да не говорим, че ние имаме -0, което не ни трябва много. + +&&/clide + + + +&&clide + +Нека да помислим пак, да вземем само положителните: + +``` +011 3 +010 2 +001 1 +``` + +Сега, искаме -1 да бъде такова число, различно от досега дефинираните (тоест което има единица в старшия си бит) така че "1 + -1 = 0". +Лесно се досещаме, че ако добавим към "001" числото "111", тогава тяхната сума ще предизвика overflow и резултата ще бъде 0: + +``` +001 + 111 = 1000 overflow, става 000 +``` + +Нека тогава "-1 = 111". + +&&/clide + + + +&&slide + +Правейки същото за "2 + -2", намираме че + +``` +010 + 110 = 1000 overflow, става 000 +``` + +Нека тогава "-2 = 110". +За "3 + -3" се досещаме, че "-3 = 101". +За сега имаме: + +``` +111 -1 +110 -2 +101 -3 +100 x +011 3 +010 2 +001 1 +000 0 +``` + +100 не сме го използвали, обаче намерихме отрицателното число за всяко положително. +Да видим как работим с него, побитово "100 + 001 = 101", тоест "x + 1 = -3", следователно x ще бъде -4. + +&&/slide + + + +&&clide + +Това е идеята на "complements", дефинираме отрицателни числа, така че да използваме едно и също събиране между положителни и отрицателни. + +Още от много старите "калкулатори" ([сумиращи машини](https://en.wikipedia.org/wiki/Adding_machine)), изваждането се е свеждало до събиране на положително и отрицателно число. + +И това е причината защо `~ 2` връща `-3`: + +``` +~ 00000000000000000000000000000010 +────────────────────────────────── + 11111111111111111111111111111101 +``` + +И затова при `>>` със знаков тип имаме аритметическо отместване: + +``` +11111111111111111111111111111101 >> 1 +───────────────────────────────────── +11111111111111111111111111111110 +``` + +&&/clide + + + +## Функции + +Позволяват ни да групираме редове код. +Синтаксисът е следния: + +```cpp +<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>) { + тяло +} +``` + +Като `<АРГУМЕНТИ>` са двойки от типа `ТИП ИМЕ`, разделени със запетаи. +Един вид, аргументите са променливи към `тяло`, които задаваме извън функцията. + +Извикваме функция чрез `име(<СТОЙНОСТИ>)`, като `<СТОЙНОСТИ>` са разделени със запетая и всяка съответства на поредния тип в аргументите на функцията. +Там, където пишем `име(<СТОЙНОСТИ>)` се "замества" с върнатата стойност от функцията. + +Връщаме стойност като напишем във функцията `return СТОЙНОСТ;`. + +Една функция трябва да бъде декларирана преди да бъде използвана, тоест кода + +```cpp +#include <iostream> + +int main() { + std::cout << doSomething(); +} + +int doSomething() { + ... +} +``` + +Няма да се компилира. +Можем само да декларираме функция, без да я дефинираме (тоест без да и дадем тяло) чрез синтаксиса: + +```cpp +<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>); +``` + +Тоест горния пример ще работи ако имаме: + +```cpp +#include <iostream> + +int doSomething(); + +int main() { + std::cout << doSomething(); +} + +int doSomething() { + ... +} +``` |