Силоз 2: Изчислителни

Този силоз съдържа проекти, които използват компютъра за това, за което е бил създаден: за извършване на разнообразни пресмятания. Целта на проектите е да приложите знанията си от курса по увод в програмирането и общи познания по математика, за да “научите” компютъра да смята и обработва разнообразни обекти извън стандартните възможности за работа цели и дробни числа и низове.

Матрици и вектори

Да се напише програма, която позволява операции с матрици и вектори от дробни (рационални) числа:

1. Матрици

• въвеждане на матрица от клавиатурата

• да се задават размерности и да се въвеждат елементите по удобен начин

• извеждане на матрица на екрана

• да се извежда матрицата в подреден табличен вид

• събиране и изваждане на матрици

• да могат да се правят няколко събирания или изваждания последователно, например A + B + C + D

• умножение на матрици

• да се прави проверка дали размерностите на матриците са подходящи

• транспониране на произволна правоъгълна матрица

• намиране на детерминанта на матрица

• без значение кой алгоритъм ще бъде използван

• намиране на обратна матрица

• да се извежда грешка, ако матрицата няма обратна

2. Вектори

Разглеждаме векторите като матрици с 1 ред или 1 колона (по ваш избор). Да се реализират следните операции за работа с вектори:

• скаларно и векторно произведение на вектори

• нормализиране на вектор

• умножение на вектор с матрица (линейна траснформация)

Програмата да поддържа текстов диалогов режим, позволяващ удобен интерактивен избор на горните операции.

Бонуси:

• персистентност (работа с файл)

• редактиране на матрица с курсор (както в електронна таблица)

• реализиране на именувани матрични променливи

Големи числа

“Големите числа” са цели положителни числа, представени, без практическо ограничение за тяхната големина (освен наличната памет). Ако би представялвало улеснение може да се приеме, че поддържаните големи числа не могат да имат повече от 255 цифри (в съответната бройна система).

• въвеждане от стандартния вход на число с практически произволен брой цифри в:

• десетична бройна система

• шеснайсетична бройна система

• извеждане на екрана на голямо число в:

• десетична бройна система

• шеснайсетична бройна система

• събиране на две големи числа

• изваждане на две големи числа

• умножение на две големи числа

• целочислено деление на две големи числа с намиране на частно и остатък

Програмата да поддържа текстов диалогов режим, позволяващ удобен интерактивен избор на горните операции.

Въпросните операции да са реализирани в програмата чрез ясно обособени функции. Употребата на входно / изходни операции в тялото на фунцкиите е забранена (освен при функциите за вход и изход), т.е. функциите реализират математически изображения.

Примери (за тестване):

"5" * "5" = "25"

"4321" - "1234" = "3087"

"1234" * "4321" = "5332114"

"12456789031415" + "98765432123456789" = "98777888912488204"

"12456789031415" * "98765432123456789" = "1230300151558439221348916026435"

"1230300151558439221348916026435" / "98765432123456789" = "12456789031415"

Геометрия

Да се напише програма, която поддържа текстов диалогов режим, позволяващ удобен интерактивен избор на серия от операции с геометрични обекти в тримерното пространство:

• Дефиниране (въвеждане) на прави (чрез уравнения на прави) и точки (чрез координати). На правите и точките да може да се задават “имена” от една буква (f,g,h…)

• Проверка дали дадена точка лежи на дадена права

• Извежда уравнение на права по дадени две точки

• по права g и точка p извежда уравнение на права, успоредна на g и минаваща през p

• по права g и точка p, лежаща на нея, извежда уравнение на права, перпендикулярна на на g с пета в p

• по две прави намира пресечната точка, ако има такава

• по триъгълник (зададен с три точки) построява уравненията на

• височина

• медиана

• симетрала

Дати

Да се напише програма, която поддържа текстов диалогов режим, позволяващ удобен интерактивен избор на серия от операции с дати:

• въвеждане на дата от клавиатурата и проверка за коректност

• извеждане на дата на екрана в избран от потребителя формат

• по дата да се определи ден от седмицата

• по описание с ден от седмицата да се определи датата, която отговаря на него, например:

• втората събота от месец октомври

• последният понеделник от месец ноември

• отпечатва календар за даден месец

• календарът да се извежда прегледно, като си личи коя дата на кой ден от седмицата отговаря

• позволява добавяне/извеждане на брой дни/седмици/месеци/години от дадена дата

• да се обработват правилно граничните случаи, например 31 януари 2012 г. + 1 месец = 29 февруари 2012 г.

• намира разстоянието между две дати в дни/седмици/месеци/години

• пример: разстоянието между 3 март 2012 г. и 13 юли 2013 г. е 1 година, 4 месеца, 1 седмица и 3 дена

• по дадена година определя датата на Великден за тази година

Реализацията на всички функции трябва да се съдържа в дадена програма, не е позволено използването на системна библиотека за работа с дати.

Кодирания RLE и Base64

1. RLE

Run-length encoding (RLE) представлява кодиране на низове, при което последователности от еднакви символи се заменят с двойка от символа и броя повторения. Например S = AAAABBBBCCCAABBBB може да се представи с RLE списъка R = (4,A) (4,B) (3,C) (2,A) (4,B). Да се напишат функции, които

• кодират даден низ в RLE списък

• декодират RLE списък до низ

• вмъкват един RLE списък на произволна позиция в друг, като позицията се указва в брой символи от началото на оригиналния низ

• пример: след като вмъкнем (3, C) (1, B) на позиция 6 в R се получава (4,A) (2, B) (3, C) (3, B) (3, C) (2, A) (4, B)

• изтриват последователност от символи от RLE списък

• пример: след като изтрием последователност от 8 символа от позиция 6 в R се получава списъкът (4,A) (5, B)

• проверяват дали низът, кодиран от RLE списъка A е подниз на низа, кодиран от RLE списъка B. Проверката да не включва операция по декодиране, с цел ефективност

• пример:  списъкът (2, B) (1, C) е подсписък на R

• пример: списъкът (1,C) (3,A) (1, B) не е подсписък на R (4,B)

• По дадено RLE кодиране на низ, да се построи честотната таблица на низа (за всеки символ, който се среща в низа, се оказават броят на срещанията му в низа). Резултатът да е под формата на  RLE списък, в който всеки символ се среща най-много веднъж

• пример: (6,A) (8,B) (3,C) е честотна таблица на R

Горните операции да бъдат реализирани в програмата чрез ясно обособени функции. Употребата на входно / изходни операции в тялото на фунцкиите е забранена, освен при функциите за вход и изход. С други думи, функциите трябва да реализират математически изображения.

2. Base64

Нека е даден масив F от байтове (unsigned char).  Да се дефинират функции, които:

• Преобразуват F до низ, в който се използват само символите “A-Za-z0-9+/”.

• От кодиран по този начин низ, възстановяват съдържанието на F

Целта на кодирането е да се избегнат специалните символи като ‘\t’, ‘\n’, ‘\0’ и други. Забележете, че броят на символите в множеството “A-Za-z0-9+/” е 64 (= 26+26+10+2).

Алгоритъм на кодиране:

1) разглеждаме двоичния файл като последователност от групи по 24 бита (три байта  от по 8 бита)

2) всеки 24 бита разбиваме на четири 6-битови байта

3) на всеки 6-битов байт съпоставяме съответния символ от “A-Za-z0-9+/”

4) записваме получените символи в текстовия файл

При достигане края на двоичния файл имаме от един от следните случаи:

а) при последната операция сме прочели точно 24 бита и значи всичко е ОК

б) при последното четене е имало само 8 бита

в) при последното четене е имало само 16 бита

В случай “б)” допълваме до 12 бита с нули и получаваме 2 6-битови байта, съпоставяме им символи и допълваме с два символа ‘=’ в текстовия файл.

В случай “в)” допълваме до 18 бита с нули и получаваме 3 6-битови байта, съпоставяме им символи и допълваме с един символ ‘=’ в текстовия файл.

Не е задължително да реализирате случаи “б)” и “в)”, приемете, че размера на файла е кратен на 3.

Това кодиране се нарича base64 и се използва при прикрепяне на файл към e-mail съобщение, заради изискванията на протокола да не се използват специални символи. Резултатът от кодирането е текстов файл с размер 4/3 спрямо оригиналния, но без специални символи и върши работа за всякакви файлове. Недостатък е, че съдържанието на кодирания файл е неразбираемо за човек. Съществува и друго широко използвано кодиране наречено quoted-printable – като при него се разчита, че се изпраща главно текст и малък брой специални символи, които се escape-ват.

Вашата задача е да напишете една кодираща и декодираща програма използвайки алгоритъма на base64. Програмата да реализира:

• кодиране

• прочитане на масив от байтове (числа от 0 до 255) от клавиатурата

• извеждане на екрана низ, който кодира масива

• декодиране

• прочитане на низ от клавиатурата

• извеждане на екрана на масив от байтове

Можете да проверите, че програмата ви работи правилно, като сравните резултата с този от някоя online реализация на base64.

Не се позволява използването на стандартни библиотеки и готови решения!

Подробна спецификация на base64 и quoted-printable кодиранията можете да намерите в секции 6.7 и 6.8 на rfc2045 (например на адрес http://www.faqs.org/rfcs/rfc2045.html).

Бонус: програмата да използва двоични файлове вместо масиви и да работи с командни параметри, както следва:

base64 encode file1.inp file1.out

base64 decode file1.out file1.copy

XML Parser

Да се напише програма, която разчита XML файлове и позволява правенето на прости XPath 2.0 заявки към тях.

Забележка: За проекта не е позволено използването на готови библиотеки за работа с XML. Целта на проекта е да се упражни работата със структурирани текстови файлове, а не толкова със самия XML. Внимание: Не се изисква осигуряване на всички условия в  XML и XPath спецификациите! Достатъчно е файловете да “приличат на XML” (както файла в горния пример, който не е валиден XML), а завките да “приличат” на XPath.  За уточняващи въпроси се обърнете към лекторите.

Минимални изисквания за поддържаните XPath заявки

Примерите по-долу са върху следния прост XML низ:

<person id=”0”>

    <name>John Smith</name>

    <address>USA</address>

</person>

<person id=”1”>

    <name>Ivan Petrov</name>

    <address>Bulgaria</address>

</person>

• да поддържат оператора  / (например “person/address” дава списък с всички адреси във файла)

• да поддържат оператора [] (например “person/address[0]” два адресът на първия елемент във файла)

• да поддържат оператора @ (например “person(@id)” дава списък с id на всички елементи във файла)

• Оператори за сравнение = (например “person(address=”USA”)/name” дава списък с имената на всички елементи, чиито адреси са “USA”)