path: root / src / teaching / upp-2023 / additional1 / index.du

'def title Допълнително упражнение 1 - УПП, 04.11.2023
'def  desc Условия на задачите за упражнение

# {title}

\n

GitHub classroom: {url classroom.github.com/a/nlFuKALw;https://classroom.github.com/a/nlFuKALw}

При изображението {img /img/dialog-question.png} трябва да спрете, да помислите и да си отговорите на дадения въпрос.
Почти винаги ако не може да отговорите, ще имате проблеми в бъдеще с решаването.
Понякога ще ви спираме и ще ви питаме за тези въпроси.

## Задача - База гаднни

.warn {b Нямате} право да използвате каквито и да е функции, които вие не сте написали, както и неизучаван материал като двуизмерни масиви или динамична памет.
{b Не} употребявайте търсачки, ако ви трябва информация за нещо, ще може да си я изкарате с една проста тестова програма или калкулатор.

\n

Ще работим върху нещо като база данни, може да си го представете като един файл на Excel.
Имаме две таблици, за удобство първата ще я наричаме "Таблица А", а втората "Таблица Б".
Таблица А има максимум 8 реда, като всеки ред е едно цяло число с 9 цифри.
Таблица Б има максимум 8 реда, като всеки ред е число между 1 и 4294967295.

.question В какъв тип ще запазим всяка таблица?

В задачата винаги номерираме редовете (числата) на всяка таблица, започвайки от индекс 1.
Чрез различни комбинации на ред в таблица А и ред в таблица Б получаваме различни стойности.
Целта на задачата е да направите една система, чрез която може коректно да обработите и "изкарате" стойности от базата данни.

Задачата наистина е голяма, затова е разделена на много стъпки и са дадени примери на всяка стъпка.
Тествайте обилно!

### Формат на редове в таблици

Гледайки десетичния запис на число (ред) от таблица А, най-лявата цифра е ред в таблица Б, цифрата след нея е тип и останалото е просто някаква стойност.
Тоест в "531009864", "5" е реда в таблица Б, "3" е типа и "1009864" е някаква стойност.
Поглеждаме типа и според него правим нещо със стойността от таблица А и реда от таблица Б.

Имайте предвид, че ще наричам "стойност от таблица А" последните 7 цифри, "ред от таблица А" всички 9 цифри.
Стойност и ред в таблица Б означават едно и също, и отговарят на цялото число от таблицата.

Стойностите от таблица А са винаги ограничени отгоре с най-големия брой битове, които комфортно може да поберем в 7 цифри.
Тоест 9999999 не е валидна стойност от таблица А, докато 8388608 e.

.question Колко най-много {i битове} можем със сигурност да поберем в 7 цифри?

Понеже редовете са от 1 до 9, ако в таблица А имаме ред 0 правим нещо специално, но това ще видите в бъдеще.

.question Разбрахте ли как таблиците "изглеждат"?

### a) разделяне на реда от таблица А

Преди да започнем, трябва да имплементираме функция, която разделя дадения ред от таблица А на трите му компонента (ред, тип и стойност):

{` getRow} - приема ред от таблица А и указатели към променливи за ред, тип и стойност; не връща нищо\n
В подадените указатели пази съответните стойности от реда

.question Защо приемаме указатели към променливи? Каква е "сигнатурата" на функцията?

\n
{b Примери:}

:table
:2
|= Извикване
|= Резултат

|: getRow(1234567, &row, &type, &value)
|: row = 0, type = 0, value = 1234567

|: getRow(12345678, &row, &type, &value)
|: row = 0, type = 1, value = 2345678

|: getRow(123456789, &row, &type, &value)
|: row = 1, type = 2, value = 3456789



### б) обикновенно число

Ако типа е цифрата "0", тогава стойността в базата данни е някакво число с плаваща запетая.
Самото число е разделено на две части: цифрите преди запетаята се намират в стойността от таблица А, докато цифрите след запетаята са в реда от таблица Б.

.question В какъв тип данни трябва да запазим числото? Как ще "слепим" двете му части.

Имплементирайте функция:

{` parseNumber} - приема стойност от таблица А и ред от таблица Б; връща полученото число от тези стойности

\n
{b Примери:}
{i Възможно е отклонението на последния пример да бъде повече от 2 единици}

:table
:2
|= Извикване
|= Резултат

|: a = parseNumber(1, 5)
|: a = 1.5

|: a = parseNumber(0, 37)
|: a = 0.37

|: a = parseNumber(913, 0)
|: a = 913.0

|: a = parseNumber(8388607, 18446744073709551615)
|: a = 8388607.18446744073709551615



### в) числов текст (част едно)

Ако типа е "1", тогава стойността в базата данни е някакъв низ (последователност от букви), която е кодирана в числата.
Всеки 5 бита в реда (от дясно на ляво) от таблица Б определя буква, като:

:table
:3
|: Битове
|: Десетично число
|: Буква

|: 00000
|: 0
|: A

|: 00001
|: 1
|: B

|: 00010
|: 2
|: C

|: ...
|:
|:

|: 11001
|: 25
|: Z

|: 11010
|: 26
|: {i шпация}

|: 11011
|: 27
|: .

|: 11100
|: 28
|: ,

|: 11101
|: 29
|: :

|: 11110
|: 30
|: ?

|: 11111
|: 31
|: !



Тоест ако в нашия тип данни запазваме само 10 бита, тогава числото "2" ще бъде {` 0000000010} и имаме низа "AC".
Игнорирайте старшите битове, които остават като "остатък" (по-малко от 5 бита ширина).

.question Колко бита наистина запазваме в нашия тип данни? Колко бита ще трябва да игнорираме? Колко най-много букви може да поберем?

Имплементирайте функция:

{` decodeNumberText} - приема ред от таблица Б и указател към "низ"; не връща нищо\n
Записва декодиран текстът от реда в указателя

.question Нарочно има кавички около думата "низ", какъв трябва наистина да е типа на указателя?

\n
{b Примери:}

:table
:2
|= Извикване
|= Резултат

|: decodeNumberText(2, decodedText)
|: decodedText = "AAAAAAAAAAAC"

|: decodeNumberText(257104811188071551, decodedText)
|: decodedText = "HELLO WORLD!"

|: decodeNumberText(1148238614786569150, decodedText)
|: decodedText = "!. ,:?!. ,:?"



### г) числов текст (част две)

Дотук добре, обаче не сме свършили съвсем.
От гледна точка на сигурност, искаме дори някой да получи достъп до таблица Б, да не може да разбере текста дори след като е използвал {` decodeNumberText}.

Ще използваме {url шифъра на Цезар;https://en.wikipedia.org/wiki/Caesar_cipher}: един много прост шифър, където отместваме позицията на всяка буква с няколко места "напред".
Тоест, при отместаване 3, буквата A става D, B става E, и так. нат.
Как декодираме?
Отместваме буквите назад, тоест ако имаме текста "KHOOR" и ви кажа, че съм го кодирал като съм отместил всяка буква напред с 3 позиции, тогава при декодиране от K става на H, от H става на E, от О става на L и от R става на O.

.question Какво става със знака "!"? Има ли лесен (математически) начин да дешифрираме всяка буква?

Текстът, преди да е въведен в нашата база данни, ще бъде кодиран с шифъра на Цезар, като броя позиции с които сме отместили буквите се намира в стойността в таблица А.

Промененте функцията:

{` decodeNumberText} - приема ред от таблица Б, стойност от таблица А и указател към "низ"; не връща нищо\n
След като декодира текста от реда от Б, дешифрира го със стойността от таблица А

\n
{b Примери:}

:table
:2
|= Извикване
|= Резултат

|: decodeNumberText(0,  2,                   decodedText)
|: decodedText = "AAAAAAAAAAAC"

|: decodeNumberText(0,  257104811188071551,  decodedText)
|: decodedText = "HELLO WORLD!"

|: decodeNumberText(0,  1148238614786569150, decodedText)
|: decodedText = "!. ,:?!., :?"

|: decodeNumberText(17, 632247276719883827,  decodedText)
|: decodedText = "AAAAAAAAAAAC"

|: decodeNumberText(3,  368677860020992194,  decodedText)
|: decodedText = "HELLO WORLD!"

|: decodeNumberText(30, 1073856582231288700, decodedText)
|: decodedText = "!. ,:?!., :?"

|: decodeNumberText(32, 1148238614786569150, decodedText)
|: decodedText = "!. ,:?!., :?"



### д) масив (част едно)

Ако типа е "2", тогава в реда от Б сме вложили масив от стойности (числа).
Всеки 4 бита определят една стойност, като първия елемент е старшите (най-левите) битове, докато последния е младшите (най-десните) битове.

.question Коколо на брой елемента пазим в реда от Б?

Имплементирайте функцията:

{` decodeArray} - приема ред от таблица Б и указател към масив; не връща нищо\n
Декодира елементите от реда и ги запазва в указателя

\n
{b Пример:}

:table
:2
|= Извикване
|= Резултат

|: decodeArray(846406911526255600, arr)
|: arr = { 0, 11, 11, 15, 0, 10, 9, 10, 0, 0, 15, 5, 3, 11, 15, 0 }



### е) масив (част две)

От гледна точка на сигурност или оптимизране на памет, искаме да "лимитираме" какви стойности са валидни, и всички невалидни да станат някоя друга стойност по подразбиране.
Така може да запазим няколко различни масива на едно и също място, спестявайки малко памет, или да "вмъкнем" ненужни стойности, така че дори някой да получи масива, да не знае кои стойности са истински и кои фалшиви.

В старшите 20 бита от стойността в таблица А ще пазим общо 5 възможни валидни стойности, а в останалите (младши) 3 бита ще пазим индекс към тези стойности, който индекс (започвайки от 1) определя стойността по подразбиране.

Пример: ако имаме побитово {` 1111100000100011101101010101}, тогава:
.bulleted
- валидните числа са {` 11111, 00000, 10001, 11011 и 01010}
- числото по подразбиране е 5-тото ({` 101 = 5}), което е числото {` 01010}
- ако от реда в Б изкараме {` 11011}, тогава го запазваме, обаче ако изкараме примерно {` 11000} тогава го превръщаме в стойността по подразбиране, а именно {` 01010}

Разширете функцията:

{` decodeArray} - приема стойност от таблица А, ред от таблица Б и указател към масив; не връща нищо\n
Декодира елементите от реда, като всички невалидни стойност се превръщат в стойността по подразбиране, и ги запазва в указателя

\n
{b Примери:}

:table
:2
|= Извикване
|= Резултат

|: decodeArray(360537, 846406911526255600, arr)
|: arr = { 0, 11, 11, 11, 0, 11, 11, 11, 0, 0, 11, 11, 11, 11, 11, 0 }

|: decodeArray(3119812, 846406911526255600, arr)
|: arr = { 8, 8, 8, 15, 8, 8, 8, 8, 8, 8, 15, 5, 3, 8, 15, 8 }



### ж) компресирани стойности

Ако редът в таблица А е 0, тогава цялата стойност в базата данни е побрана в стойността на таблица А.
Очевидно само в стойност на таблица А имаме по-малко битове, отколкото в стойност на таблица А плюс ред в таблица Б, затова се налага по някакъв начин да "компресираме" информацията, така че да се побере.

.question Колко бита побираме в стойност на таблица А? Колко бита ни трябват общо, за да обработим една стойност в базата данни?

Ще го направим така: в стойността от таблица А ще пазим индекси, и всеки индекс ще съответства на някакво по-голямо число, което се съдържа в друг масив, който ще наричаме криптографски ред.

Пример (всички числа са представени двоично; стойностите не са напълно валидни за базата данни, но са логически коректни):

.comment                   000    001    010    011    100    101

:bulleted
- Kриптографски ред е {` 00000, 10101, 11011, 10001, 01101, 10100}
  .bulleted
  - Индексираме от 0 до 5, което побитово е от 000 до 101

- Стойност в таблицата А е {` 011001000001101101}
  .bulleted
  - Разделяйки го на индекси, това са {` 011, 001, 000, 001, 101, 101}

- Слепвайки от криптографския ред на тези индекси получаваме {` 100011010100000101011010010100}


Във вашата програма ще се наложи да направите още една променлива, в която пазите криптографския ред.
Всяка стойност в реда ще съдържа 21 бита.
Първите (най-левите) три бита от стойността в таблица А не са индекси, а трябва да се копират дословно.
След тях има 4 индекса, всеки с по 5 бита.

.question Как е разделена побитово една стойност от таблица А? Кои индекси за кои стойности ще се ползват? Достатъчно ли е всеки индекс към криптографския ред да бъде само 5 бита (тоест може ли да има повече от 2⁵ числа в реда)? Защо имаме само 4 индекса?

Напишете функция:

{` decompress} - приема стойност от таблица А, криптографски ред, указател за запазване на декомпресираната стойност от таблица А и указател за запазване на декомпресирания ред от таблица Б; не връща нищо

\n
{b Примери:}

:table
:2
|= Извикване
|= Резултат

|: crypt = { 0, 2, 5 }\ndecompress(32770, crypt, &decompA, &decompB)
|: decompA = 1, decompB = 5

|: crypt = { 2097151 }\ndecompress(7340032, crypt, &decompA, &decompB)
|: decompA = 8388607, decompB = 18446744073709551615



### з) входни данни

В началото на програмата получавате броя на редове от таблица А (между 1 и 16), след това толкова "реда".
След това броя редове от таблица Б (между 1 и 8), след това толкова реда.
Накрая получавате размера на криптографския ред (между 1 и 64) и толкова стойности.

### и) четене от базата данни

След това получавате команди (знак):
.bulleted
- {` g X}: изкарвате на екрана стойността в базата данни, започвайки с ред X от таблица А
- {` i}: Връщате информация за базата данни
- {` q}: спиране на програмата

### й) заявки

.bulleted
- {` t X}: връщате броя и след това всички редове от таблица А с тип X
- {` r X}: връщате броя и всички редове от таблица А, които използват реда Х\n
  Ако реда е 0, тогава трябва да върнете и размера на криптографския ред

### к) презаписване в базата данни

.bulleted
- {` w T R V}: запазвате (презаписвате) стойност V в таблица Т (може да бъде {` A} или {` B}) на ред R
- {` s T V}: запазвате стойност V от тип Т в базата данни\n
  Пробвате се да я запазите, използвайки и двете таблици, но ако Б вече е запълнена, добавяте я като компресирана стойност в таблица А.
  Ако и А е запълнена, изкарвате съобщение за запълнена база данни и не запазвате стойността.

.question Какво трябва да направите, ако получите компресирана стойност за таблица А?