diff options
1 files changed, 269 insertions, 0 deletions
| -rw-r--r-- | src/teaching/upp-2023/additional1/index.md | 269 |
diff --git a/src/teaching/upp-2023/additional1/index.md b/src/teaching/upp-2023/additional1/index.md new file mode 100644 index 0000000..51209e8 --- /dev/null +++ b/src/teaching/upp-2023/additional1/index.md @@ -0,0 +1,269 @@ +# Допълнително упражнение 1 - УПП, 04.11.2023 + +GitHub classroom: [classroom.github.com/a/nlFuKALw](https://classroom.github.com/a/nlFuKALw) + +При изображението &&question трябва да спрете, да помислите и да си отговорите на дадения въпрос. +Почти винаги ако не може да отговорите, ще имате проблеми в бъдеще с решаването. +Понякога ще ви спираме и ще ви питаме за тези въпроси. + +## Задача - База гаднни + +&&warn **Нямате** право да използвате каквито и да е функции, които вие не сте написали, както и неизучаван материал като двуизмерни масиви или динамична памет. +**Не** употребявайте търсачки, ако ви трябва информация за нещо, ще може да си я изкарате с една проста тестова програма или калкулатор. + +<br> + +Ще работим върху нещо като база данни, може да си го представете като един файл на Excel. +Имаме две таблици, за удобство първата ще я наричаме "Таблица А", а втората "Таблица Б". +Таблица А има максимум 16 реда, като всеки ред е едно цяло число с 9 цифри. +Таблица Б има максимум 8 реда, като всеки ред е число между 1 и 4294967295. + +&&question В какъв тип ще запазим всяка таблица? + +В задачата винаги номерираме редовете (числата) на всяка таблица, започвайки от индекс 1. +Чрез различни комбинации на ред в таблица А и ред в таблица Б получаваме различни стойности. +Целта на задачата е да направите една система, чрез която може коректно да обработите и "изкарате" стойности от базата данни. + +Задачата наистина е голяма, затова е разделена на много стъпки и са дадени примери на всяка стъпка. +Тествайте обилно! + +### Формат на редове в таблици + +Гледайки десетичния запис на число (ред) от таблица А, най-лявата цифра е ред в таблица Б, цифрата след нея е тип и останалото е просто някаква стойност. +Тоест в "531009864", "5" е реда в таблица Б, "3" е типа и "1009864" е някаква стойност. +Поглеждаме типа и според него правим нещо със стойността от таблица А и реда от таблица Б. + +Имайте предвид, че ще наричам "стойност от таблица А" последните 7 цифри, "ред от таблица А" всички 9 цифри. +Стойност и ред в таблица Б означават едно и също, и отговарят на цялото число от таблицата. + +Стойностите от таблица А са винаги ограничени отгоре с най-големия брой битове, които комфортно може да поберем в 7 цифри. +Тоест 9999999 не е валидна стойност от таблица А, докато 8388608 e. + +&&question Колко най-много *битове* можем със сигурност да поберем в 7 цифри? + +Понеже редовете са от 1 до 9, ако в таблица А имаме ред 0 правим нещо специално, но това ще видите в бъдеще. + +&&question Разбрахте ли как таблиците "изглеждат"? + +### a) разделяне на реда от таблица А + +Преди да започнем, трябва да имплементираме функция, която разделя дадения ред от таблица А на трите му компонента (ред, тип и стойност): + +`getRow` - приема ред от таблица А и указатели към променливи за ред, тип и стойност; не връща нищо +В подадените указатели пази съответните стойности от реда + +&&question Защо приемаме указатели към променливи? Каква е "сигнатурата" на функцията? + +<br> +**Примери:** + +|Извикване|Резултат| +|---------|--------| +|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` - приема стойност от таблица А и ред от таблица Б; връща полученото число от тези стойности + +<br> +**Примери:** +*Възможно е отклонението на последния пример да бъде повече от 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 бита в реда (от дясно на ляво) от таблица Б определя буква, като: + +|Битове|Десетично число|Буква| +|------|---------------|-----| +|00000 |0 |A | +|00001 |1 |B | +|00010 |2 |C | +|...||| +|11001 |25 |Z | +|11010 |26 |*шпация*| +|11011 |27 |. | +|11100 |28 |, | +|11101 |29 |: | +|11110 |30 |? | +|11111 |31 |! | + +Тоест ако в нашия тип данни запазваме само 10 бита, тогава числото "2" ще бъде `0000000001` и имаме низа "AC". +Игнорирайте старшите битове, които остават като "остатък" (по-малко от 5 бита ширина). + +&&question Колко бита наистина запазваме в нашия тип данни? Колко бита ще трябва да игнорираме? Колко най-много букви може да поберем? + +Имплементирайте функция: + +`decodeNumberText` - приема ред от таблица Б и указател към "низ"; не връща нищо +Записва декодиран текстът от реда в указателя + +&&question Нарочно има кавички около думата "низ", какъв трябва наистина да е типа на указателя? + +<br> +**Примери:** + +|Извикване|Резултат| +|---------|--------| +|decodeNumberText(2, decodedText)|decodedText = "AAAAAAAAAAAC"| +|decodeNumberText(257104811188071551, decodedText)|decodedText = "HELLO WORLD!"| +|decodeNumberText(1148238614786569150, decodedText)|decodedText = "!. ,:?!. ,:?"| + +### г) числов текст (част две) + +Дотук добре, обаче не сме свършили съвсем. +От гледна точка на сигурност, искаме дори някой да получи достъп до таблица Б, да не може да разбере текста дори след като е използвал `decodeNumberText`. + +Ще използваме [шифъра на Цезар](https://en.wikipedia.org/wiki/Caesar_cipher): един много прост шифър, където отместваме позицията на всяка буква с няколко места "напред". +Тоест, при отместаване 3, буквата A става D, B става E, и так. нат. +Как декодираме? +Отместваме буквите назад, тоест ако имаме текста "KHOOR" и ви кажа, че съм го кодирал като съм отместил всяка буква напред с 3 позиции, тогава при декодиране от K става на H, от H става на E, от О става на L и от R става на O. + +&&question Какво става със знака "!"? Има ли лесен (математически) начин да дешифрираме всяка буква? + +Текстът, преди да е въведен в нашата база данни, ще бъде кодиран с шифъра на Цезар, като броя позиции с които сме отместили буквите се намира в стойността в таблица А. + +Промененте функцията: + +`decodeNumberText` - приема ред от таблица Б, стойност от таблица А и указател към "низ"; не връща нищо +След като декодира текста от реда от Б, дешифрира го със стойността от таблица А + +<br> +**Примери:** + +|Извикване|Резултат| +|---------|--------| +|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` - приема ред от таблица Б и указател към масив; не връща нищо +Декодира елементите от реда и ги запазва в указателя + +<br> +**Пример:** + +|Извикване|Резултат| +|---------|--------| +|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`, тогава: + +- валидните числа са `11111, 00000, 10001, 11011 и 01010` +- числото по подразбиране е 5-тото (`101 = 5`), което е числото `01010` +- ако от реда в Б изкараме `11011`, тогава го запазваме, обаче ако изкараме примерно `11000` тогава го превръщаме в стойността по подразбиране, а именно `01010` + +Разширете функцията: + +`decodeArray` - приема стойност от таблица А, ред от таблица Б и указател към масив; не връща нищо +Декодира елементите от реда, като всички невалидни стойност се превръщат в стойността по подразбиране, и ги запазва в указателя + +<br> +**Примери:** + +|Извикване|Резултат| +|---------|--------| +|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 Колко бита побираме в стойност на таблица А? Колко бита ни трябват общо, за да обработим една стойност в базата данни? + +Ще го направим така: в стойността от таблица А ще пазим индекси, и всеки индекс ще съответства на някакво по-голямо число, което се съдържа в друг масив, който ще наричаме криптографски ред. + +Пример (всички числа са представени двоично; стойностите не са напълно валидни за базата данни, но са логически коректни): + +<!-- 000 001 010 011 100 101 --> +- Kриптографски ред е `00000, 10101, 11011, 10001, 01101, 10100` + - Индексираме от 0 до 5, което побитово е от 000 до 101 +- Стойност в таблицата А е `011001000001101101` + - Разделяйки го на индекси, това са `011, 001, 000, 001, 101, 101` +- Слепвайки от криптографския ред на тези индекси получаваме `100011010100000101011010010100` + +Във вашата програма ще се наложи да направите още една променлива, в която пазите криптографския ред. +Всяка стойност в реда ще съдържа 21 бита. +Първите (най-левите) три бита от стойността в таблица А не са индекси, а трябва да се копират дословно. +След тях има 4 индекса, всеки с по 5 бита. + +&&question Как е разделена побитово една стойност от таблица А? Кои индекси за кои стойности ще се ползват? Достатъчно ли е всеки индекс към криптографския ред да бъде само 5 бита (тоест може ли да има повече от 2⁵ числа в реда)? Защо имаме само 4 индекса? + +Напишете функция: + +`decompress` - приема стойност от таблица А, криптографски ред, указател за запазване на декомпресираната стойност от таблица А и указател за запазване на декомпресирания ред от таблица Б; не връща нищо + +<br> +**Примери:** + +|Извикване|Резултат| +|---------|--------| +|crypt = { 0, 2, 5 }<br>decompress(32770, crypt, &decompA, &decompB)|decompA = 1, decompB = 5| +|crypt = { 2097151 }<br>decompress(7340032, crypt, &decompA, &decompB)|decompA = 8388607, decompB = 18446744073709551615| + +### з) входни данни + +В началото на програмата получавате броя на редове от таблица А (между 1 и 16), след това толкова "реда". +След това броя редове от таблица Б (между 1 и 8), след това толкова реда. +Накрая получавате размера на криптографския ред (между 1 и 64) и толкова стойности. + +### и) четене от базата данни + +След това получавате команди (знак): + +- `g X`: изкарвате на екрана стойността в базата данни, започвайки с ред X от таблица А +- `i`: Връщате информация за базата данни +- `q`: спиране на програмата + +### й) заявки + +- `t X`: връщате броя и след това всички редове от таблица А с тип X +- `r X`: връщате броя и всички редове от таблица А, които използват реда Х + Ако реда е 0, тогава трябва да върнете и размера на криптографския ред + +### к) презаписване в базата данни + +- `w T R V`: запазвате (презаписвате) стойност V в таблица Т (може да бъде `A` или `B`) на ред R +- `s T V`: запазвате стойност V от тип Т в базата данни + Пробвате се да я запазите, използвайки и двете таблици, но ако Б вече е запълнена, добавяте я като компресирана стойност в таблица А. + Ако и А е запълнена, изкарвате съобщение за запълнена база данни и не запазвате стойността. + +&&question Какво трябва да направите, ако получите компресирана стойност за таблица А? |