[Поправителен изпит]СД и СД-Практикум
Решението може да се предаде като единствен .CPP файл или ZIP файл, състоящ се от .CPP и .H файлове
Задачата е разделена на две части. Първата част носи точки по СД, а втората - по СД-Практикум. Не е задължително да решите първата част до край, за да преминете към втората част.
=== За оценка по СД ===
Задача 1. “HTML-подобен” документ наричаме текстов документ, съставен от отварящи тагове от типа <tagname> и затварящи тагове от типа </tagname>. Между таговете може да има произволни комбинации и символи, с изключение на символите ‘<’ и ‘>’. Например:
<html>
<head>
<title>Писмен изпит по СДП</title>
</head>
<body>
<h1>Вариант 1</h1>
</body>
</html>
Имената на таговете могат да се състоят единствено от малки латински букви.
Казваме, че </tag> “затваря” <tag>, ако го следва в документа и между тях няма друг отварящ таг със същото име.
Даден таг наричаме “затворен”, ако за него има таг, който го затваря.
Документът е правилно построен, ако между никой отварящ таг <tag> и затварящия му таг </tag> няма незатворени тагове. Документът от примера е правилно построен. Следният документ не е правилно построен "<tag><wrong></tag></wrong>".
Даден таг <child> наричаме “вложен” в таг <parent>, ако <child> се отваря преди <parent> да е затворен.
Листо в документа наричаме тези тагове, които нямат вложени тагове (title и h1 от примера).
Свободния текст между отварянето и затварянето на дадено листо наричаме негово съдържание, като новите редове са премахнати. Например "Вариант 1" е съдържанието на тага h1.
За HTML-подобните документи съдържание е позволено да имат само листата.
-
[1т.] Да се отвори тектов файл с име “doc.html”, създаден по описаните правила, и на стандартния изход да се изведе correct/incorrect в зависимост от това, дали е правилно построен.
-
[1т.] Да се изведат на стандартния изход съдържанията на всички листа в документа, всяко на нов ред.
Задача 2. Да се дефинира шаблон Counter<T>, който реализира “преброител” на елементи от тип T. Преброителят се инициализира с нулева бройка за всички елементи от тип T и позволява да се “добавя” и “премахва” по един брой от даден елемент x на T. Шаблонът да дефинира следните операции:
-
[0.25т.] operator +=: увеличава броя на елемента x;
-
[0.25т.] съответен оператор +;
-
[0.5т.] count: Връща колко елемента имат брой, различен от 0;
-
[0.5т.] оператор за индексиране [x], дава броя на x;
-
[0.5т.] operator + за събиране на два брояча (бройките на резултатния брояч са сумите на бройките на изходните броячи).
Например:
Counter<int> c; c+=0; c+=0; std::cout << c[0] << “,” << c[1];
ще изведе на стандартния изход “2,0”, защото имаме два броя нули и нула броя единици.
Класът да не налага ограничение за количеството елементи, които могат да бъдат представени. Пълен брой точки ще получите при използване на подходяща структура от данни с добра сложност на най-важните операции.
=== За оценка по СД-Практикум ===
Задача 3. Към решението на задача 1 да се добавят следните възможности:
3. [1.5т]. “Дълбочина” на таг наричаме броя на таговете, в които тага в вложен. Дълбочината на html е 0, а на h1 е 2. Да се създаде документ “doc-pretty.html”, със същото съдържание като “doc.html”, но такъв че:
-
Всеки отварящ и затварящ таг е на нов ред, освен затварящите тагове на листата.
-
Всеки отварящ и затварящ таг с дълбочина d се предшестват от точно 4*d на брой интервала (освен затварящия таг на листата)
-
Съдържанието на всяко листо е на същия ред като отварящия и затварящия му таг
-
Премахнати са всички листа, чието съдържание е празен низ
Примерният документ е изведен в описания формат.
4. При прочитането на файла да се извеждат събщение за следните грешки, като се изведе и името на засегнатия таг
-
[0.5т.] Име на таг не е съставено само от малки латински букви
-
[0.5т.] Затваря се родителски таг, преди да е затворен вложен таг
-
[0.5т.] Затваря се таг, който не е отворен
-
[0.5т.] Има съдържание, различно от интервали и нови редове, в таг, който не е листо
-
[0.5т.] В документа има отворен таг, който не е затворен
Задача 4. Разглеждаме ориентиран граф, чиито върхове са представени с числата от тип int [0,...,N-1], където N <= 100 се въвежда от стандартния вход:
-
[0.25т]Да се реализира вход на графа от стандартния вход. Вътрешното представяне е по ваш избор
-
[0.75т.]Двупосочен път в ориентиран граф наричаме път, в който всяко ребро има обратно, т.е. огледалният образ на пътя също е път в графа. Да се напише булева функция twoWayN с параметри length и n, която проверява дали в графа съществува ацикличен път с дължина поне length, започващ от върха n, който е двупосочен
-
[0.25т.]Използването на функцията да се демонстрира с работеща програма
Решението може да се предаде като единствен .CPP файл или ZIP файл, състоящ се от .CPP и .H файлове