diff options
1 files changed, 218 insertions, 0 deletions
| -rw-r--r-- | src/teaching/upp-2023/week4/revision.md | 218 |
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() { + ... +} +``` |