Допълнително упражнение 1 - УПП, 04.11.2023
GitHub classroom: classroom.github.com/a/nlFuKALw
При изображението трябва да спрете, да помислите и да си отговорите на дадения въпрос. Почти винаги ако не може да отговорите, ще имате проблеми в бъдеще с решаването. Понякога ще ви спираме и ще ви питаме за тези въпроси.
Задача - База гаднни
#Нямате право да използвате каквито и да е функции, които вие не сте написали, както и неизучаван материал като двуизмерни масиви или динамична памет. Не употребявайте търсачки, ако ви трябва информация за нещо, ще може да си я изкарате с една проста тестова програма или калкулатор.
Ще работим върху нещо като база данни, може да си го представете като един файл на Excel. Имаме две таблици, за удобство първата ще я наричаме “Таблица А”, а втората “Таблица Б”. Таблица А има максимум 8 реда, като всеки ред е едно цяло число с 9 цифри. Таблица Б има максимум 8 реда, като всеки ред е число между 1 и 4294967295.
В какъв тип ще запазим всяка таблица?
В задачата винаги номерираме редовете (числата) на всяка таблица, започвайки от индекс 1. Чрез различни комбинации на ред в таблица А и ред в таблица Б получаваме различни стойности. Целта на задачата е да направите една система, чрез която може коректно да обработите и “изкарате” стойности от базата данни.
Задачата наистина е голяма, затова е разделена на много стъпки и са дадени примери на всяка стъпка. Тествайте обилно!
Формат на редове в таблици
#Гледайки десетичния запис на число (ред) от таблица А, най-лявата цифра е ред в таблица Б, цифрата след нея е тип и останалото е просто някаква стойност. Тоест в “531009864”, “5” е реда в таблица Б, “3” е типа и “1009864” е някаква стойност. Поглеждаме типа и според него правим нещо със стойността от таблица А и реда от таблица Б.
Имайте предвид, че ще наричам “стойност от таблица А” последните 7 цифри, “ред от таблица А” всички 9 цифри. Стойност и ред в таблица Б означават едно и също, и отговарят на цялото число от таблицата.
Стойностите от таблица А са винаги ограничени отгоре с най-големия брой битове, които комфортно може да поберем в 7 цифри. Тоест 9999999 не е валидна стойност от таблица А, докато 8388608 e.
Колко най-много битове можем със сигурност да поберем в 7 цифри?
Понеже редовете са от 1 до 9, ако в таблица А имаме ред 0 правим нещо специално, но това ще видите в бъдеще.
Разбрахте ли как таблиците “изглеждат”?
a) разделяне на реда от таблица А
#Преди да започнем, трябва да имплементираме функция, която разделя дадения ред от таблица А на трите му компонента (ред, тип и стойност):
getRow
- приема ред от таблица А и указатели към променливи за ред, тип и стойност; не връща нищо
В подадените указатели пази съответните стойности от реда
Защо приемаме указатели към променливи? Каква е “сигнатурата” на функцията?
Примери:
Извикване | Резултат |
---|---|
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”, тогава стойността в базата данни е някакво число с плаваща запетая. Самото число е разделено на две части: цифрите преди запетаята се намират в стойността от таблица А, докато цифрите след запетаята са в реда от таблица Б.
В какъв тип данни трябва да запазим числото? Как ще “слепим” двете му части.
Имплементирайте функция:
parseNumber
- приема стойност от таблица А и ред от таблица Б; връща полученото число от тези стойности
Примери:
Възможно е отклонението на последния пример да бъде повече от 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” ще бъде 0000000010
и имаме низа “AC”.
Игнорирайте старшите битове, които остават като “остатък” (по-малко от 5 бита ширина).
Колко бита наистина запазваме в нашия тип данни? Колко бита ще трябва да игнорираме? Колко най-много букви може да поберем?
Имплементирайте функция:
decodeNumberText
- приема ред от таблица Б и указател към “низ”; не връща нищо
Записва декодиран текстът от реда в указателя
Нарочно има кавички около думата “низ”, какъв трябва наистина да е типа на указателя?
Примери:
Извикване | Резултат |
---|---|
decodeNumberText(2, decodedText) | decodedText = “AAAAAAAAAAAC” |
decodeNumberText(257104811188071551, decodedText) | decodedText = “HELLO WORLD!” |
decodeNumberText(1148238614786569150, decodedText) | decodedText = “!. ,:?!. ,:?” |
г) числов текст (част две)
#Дотук добре, обаче не сме свършили съвсем.
От гледна точка на сигурност, искаме дори някой да получи достъп до таблица Б, да не може да разбере текста дори след като е използвал decodeNumberText
.
Ще използваме шифъра на Цезар: един много прост шифър, където отместваме позицията на всяка буква с няколко места “напред”. Тоест, при отместаване 3, буквата A става D, B става E, и так. нат. Как декодираме? Отместваме буквите назад, тоест ако имаме текста “KHOOR” и ви кажа, че съм го кодирал като съм отместил всяка буква напред с 3 позиции, тогава при декодиране от K става на H, от H става на E, от О става на L и от R става на O.
Какво става със знака “!”? Има ли лесен (математически) начин да дешифрираме всяка буква?
Текстът, преди да е въведен в нашата база данни, ще бъде кодиран с шифъра на Цезар, като броя позиции с които сме отместили буквите се намира в стойността в таблица А.
Промененте функцията:
decodeNumberText
- приема ред от таблица Б, стойност от таблица А и указател към “низ”; не връща нищо
След като декодира текста от реда от Б, дешифрира го със стойността от таблица А
Примери:
Извикване | Резултат |
---|---|
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 бита определят една стойност, като първия елемент е старшите (най-левите) битове, докато последния е младшите (най-десните) битове.
Коколо на брой елемента пазим в реда от Б?
Имплементирайте функцията:
decodeArray
- приема ред от таблица Б и указател към масив; не връща нищо
Декодира елементите от реда и ги запазва в указателя
Пример:
Извикване | Резултат |
---|---|
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
- приема стойност от таблица А, ред от таблица Б и указател към масив; не връща нищо
Декодира елементите от реда, като всички невалидни стойност се превръщат в стойността по подразбиране, и ги запазва в указателя
Примери:
Извикване | Резултат |
---|---|
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, тогава цялата стойност в базата данни е побрана в стойността на таблица А. Очевидно само в стойност на таблица А имаме по-малко битове, отколкото в стойност на таблица А плюс ред в таблица Б, затова се налага по някакъв начин да “компресираме” информацията, така че да се побере.
Колко бита побираме в стойност на таблица А? Колко бита ни трябват общо, за да обработим една стойност в базата данни?
Ще го направим така: в стойността от таблица А ще пазим индекси, и всеки индекс ще съответства на някакво по-голямо число, което се съдържа в друг масив, който ще наричаме криптографски ред.
Пример (всички числа са представени двоично; стойностите не са напълно валидни за базата данни, но са логически коректни):
- Kриптографски ред е
00000, 10101, 11011, 10001, 01101, 10100
- Индексираме от 0 до 5, което побитово е от 000 до 101
- Стойност в таблицата А е
011001000001101101
- Разделяйки го на индекси, това са
011, 001, 000, 001, 101, 101
- Разделяйки го на индекси, това са
- Слепвайки от криптографския ред на тези индекси получаваме
100011010100000101011010010100
Във вашата програма ще се наложи да направите още една променлива, в която пазите криптографския ред. Всяка стойност в реда ще съдържа 21 бита. Първите (най-левите) три бита от стойността в таблица А не са индекси, а трябва да се копират дословно. След тях има 4 индекса, всеки с по 5 бита.
Как е разделена побитово една стойност от таблица А? Кои индекси за кои стойности ще се ползват? Достатъчно ли е всеки индекс към криптографския ред да бъде само 5 бита (тоест може ли да има повече от 2⁵ числа в реда)? Защо имаме само 4 индекса?
Напишете функция:
decompress
- приема стойност от таблица А, криптографски ред, указател за запазване на декомпресираната стойност от таблица А и указател за запазване на декомпресирания ред от таблица Б; не връща нищо
Примери:
Извикване | Резултат |
---|---|
crypt = { 0, 2, 5 } decompress(32770, crypt, &decompA, &decompB) |
decompA = 1, decompB = 5 |
crypt = { 2097151 } decompress(7340032, crypt, &decompA, &decompB) |
decompA = 8388607, decompB = 18446744073709551615 |
з) входни данни
#В началото на програмата получавате броя на редове от таблица А (между 1 и 16), след това толкова “реда”. След това броя редове от таблица Б (между 1 и 8), след това толкова реда. Накрая получавате размера на криптографския ред (между 1 и 64) и толкова стойности.
и) четене от базата данни
#След това получавате команди (знак):
g X
: изкарвате на екрана стойността в базата данни, започвайки с ред X от таблица Аi
: Връщате информация за базата данниq
: спиране на програмата
й) заявки
#t X
: връщате броя и след това всички редове от таблица А с тип Xr X
: връщате броя и всички редове от таблица А, които използват реда Х
Ако реда е 0, тогава трябва да върнете и размера на криптографския ред
к) презаписване в базата данни
#w T R V
: запазвате (презаписвате) стойност V в таблица Т (може да бъдеA
илиB
) на ред Rs T V
: запазвате стойност V от тип Т в базата данни
Пробвате се да я запазите, използвайки и двете таблици, но ако Б вече е запълнена, добавяте я като компресирана стойност в таблица А. Ако и А е запълнена, изкарвате съобщение за запълнена база данни и не запазвате стойността.
Какво трябва да направите, ако получите компресирана стойност за таблица А?