1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
'def title Преговор - УПП, Седмица 4, 27.10.2023
'def desc Преговор на материала
# {title}
{presentation-controller}
:title_slide35
# Функции и алгоритмични задачи
:slide27
## От сега нататък ще направим няколко промени
:unordered
- Вместо много и лесни задачи ще давам малко и трудни задачи
.bulleted
- Контролното наближава, а резултата от задачата на семинара не е добър
- Моето впечатление е, че повечето които имат опит с програмиране нямат много опит с алгоритмични задачи и обратно
- Задачите ще са повече алгоритмични, лесните задачи ще виждате на семинар
- Ще изисквам добър стил при писане на код
.bulleted
- Това означава добре подравнен код, празни символи около оператори {b и} свестни имена на променливи
- Името на променлива не трябва да бъде 150 знака, но трябва да е разбираемо какво съдържа
- {b Без шльокавица!}
- Преговорът ще бъде за вас да си го четете (освен ако не трябва да преподам нещо ново)
- Ще може да предавате задания след срока!\n
Искам да решите колкото се може повече вкъщи.
{i Нещата за 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 СТОЙНОСТ;}.
Една функция трябва да бъде декларирана преди да бъде използвана, тоест кода
````cpp
#include <iostream>
int main() {
std::cout << doSomething();
}
int doSomething() {
\...
}
Няма да се компилира.
Можем само да декларираме функция, без да я дефинираме (тоест без да и дадем тяло) чрез синтаксиса:
```cpp
<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>);
Тоест горния пример ще работи ако имаме:
````cpp
#include <iostream>
int doSomething();
int main() {
std::cout << doSomething();
}
int doSomething() {
\...
}
|
