# Преговор - УПП, Седмица 4, 27.10.2023

[$presentation-controller]

:title_slide35

# Функции и алгоритмични задачи


:slide27

## От сега нататък ще направим няколко промени

:unordered
- Вместо много и лесни задачи ще давам малко и трудни задачи
  .bulleted
  - Контролното наближава, а резултата от задачата на семинара не е добър
  - Моето впечатление е, че повечето които имат опит с програмиране нямат много опит с алгоритмични задачи и обратно
  - Задачите ще са повече алгоритмични, лесните задачи ще виждате на семинар

- Ще изисквам добър стил при писане на код
  .bulleted
  - Това означава добре подравнен код, празни символи около оператори =[и]= свестни имена на променливи
  - Името на променлива не трябва да бъде 150 знака, но трябва да е разбираемо какво съдържа
  - =[Без шльокавица!]=

- Преговорът ще бъде за вас да си го четете (освен ако не трябва да преподам нещо ново)
- Ще може да предавате задания след срока!\n
  Искам да решите колкото се може повече вкъщи.



*[Нещата за 2s compliment се намират и в [url ../week3/revision.html?a преговора на миналата седмица], ама го написах след като свърши часа, затова го копирам и тук.]*

:slide

## 2s compliment

.p
Интуитивно обяснение на 2s compliment.
Да приемем, че работим с тип данни, при който имаме само 3 бита.

.p
Как бихме ги използвали, за да представим отрицателните числа?
Най-лесния начин е да погледнем най-левия (старшия) бит, ако е 0 значи е положително, ако е 1 значи е отрицателно, тоест `[010]` е 2, докато `[110]` е -2.
Ако разпишем всичките ни числа:

```
111 -3
110 -2
101 -1
100 -0
011  3
010  2
001  1
000  0


:middle_slide

.p
Това работи, обаче имаме един гигантски проблем: събирането не работи!
От математика знаем, че "2 - 1 = 2 + (-1)", тоест би трябвало да можем да съберем побитово 2 и -1 и да получим 1.
Ама,

```
2 + -1 = 010 + 101 = 111 = -3

.p
Също, знаем, че "(-1) + (-1) = -2", обаче

```
-1 + -1 = 101 + 101 = 1010 имаме overflow, това се съкращава на 010 = 2

.p
Излиза, че с тази схема не можем да събираме отрицателни числа както събираме положителни (или както събираме побитово).

.p
Да не говорим, че ние имаме -0, което не ни трябва много.


:middle_slide

.p
Нека да помислим пак, да вземем само положителните:

```
011 3
010 2
001 1

.p
Сега, искаме -1 да бъде такова число, различно от досега дефинираните (тоест което има единица в старшия си бит) така че "1 + -1 = 0".
Лесно се досещаме, че ако добавим към "001" числото "111", тогава тяхната сума ще предизвика overflow и резултата ще бъде 0:

```
001 + 111 = 1000 overflow, става 000

.p
Нека тогава "-1 = 111".


:slide

.p
Правейки същото за "2 + -2", намираме че

```
010 + 110 = 1000 overflow, става 000

.p
Нека тогава "-2 = 110".
За "3 + -3" се досещаме, че "-3 = 101".
За сега имаме:

```
111 -1
110 -2
101 -3
100  x
011  3
010  2
001  1
000  0

.p
100 не сме го използвали, обаче намерихме отрицателното число за всяко положително.
Да видим как работим с него, побитово "100 + 001 = 101", тоест "x + 1 = -3", следователно x ще бъде -4.


:middle_slide

.p
Това е идеята на "complements", дефинираме отрицателни числа, така че да използваме едно и също събиране между положителни и отрицателни.

.p
Още от много старите "калкулатори" ([url https://en.wikipedia.org/wiki/Adding_machine сумиращи машини]), изваждането се е свеждало до събиране на положително и отрицателно число.

.p
И това е причината защо `[~ 2]` връща `[-3]`:

```
~ 00000000000000000000000000000010
──────────────────────────────────
  11111111111111111111111111111101

И затова при `[>>]` със знаков тип имаме аритметическо отместване:

```
11111111111111111111111111111101 >> 1
─────────────────────────────────────
11111111111111111111111111111110


## Функции

Позволяват ни да групираме редове код.
Синтаксисът е следния:

```cpp
<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>) {
    тяло
}

Като `[<АРГУМЕНТИ>]` са двойки от типа `[ТИП ИМЕ]`, разделени със запетаи.
Един вид, аргументите са променливи към `[тяло]`, които задаваме извън функцията.

Извикваме функция чрез `[име(<СТОЙНОСТИ>)]`, като `[<СТОЙНОСТИ>]` са разделени със запетая и всяка съответства на поредния тип в аргументите на функцията.
Там, където пишем `[име(<СТОЙНОСТИ>)]` се "замества" с върнатата стойност от функцията.

Връщаме стойност като напишем във функцията `[return СТОЙНОСТ;]`.

Една функция трябва да бъде декларирана преди да бъде използвана, тоест кода

:code_cpp
#include \<iostream>

int main() {
    std::cout << doSomething();
}

int doSomething() {
    ...
}


Няма да се компилира.
Можем само да декларираме функция, без да я дефинираме (тоест без да и дадем тяло) чрез синтаксиса:

```cpp
<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>);

Тоест горния пример ще работи ако имаме:

:code_cpp
#include \<iostream>

int doSomething();

int main() {
    std::cout << doSomething();
}

int doSomething() {
    ...
}