Структури от данни и програмиране (КН) 2014/15 г., 2 поток

Моля, изпращайте решенията си като ZIP файл, в който има четири директории с имена prog1, prog2, prog3, prog4 -- по една за всяка задача. Във всяка директория поставете изходните и заглавните файлове за всяка задача. Моля, в архива поставяйте само изходни и заглавни файлове, не поставяйте проектни, обектни и изпълними файлове!

В решението на задачата е позволено използването на стандартните библиотеки, включително STL, както и на шаблоните от лекции.

Внимание: Задачите са за самостоятелна работа, при установено взаимстване между колеги и от Интернет домашното се анулира.

Внимание: Моля, преди да изпратите решението си, уверете се, че файловете ви се компилират, в противен случай на съответната задача ще получите 0 точки!

Задача 1. (5 точки) Иванчо бил нает да мие чинии в кварталната кръчма "При бате Минчо”. Тя била толкова модерна, че помещението за миене на чинии било отделено от останалите и било оборудвано с една поточна линия, по която на всеки половин час пристигали нови чинии за миене. Тъй като, обаче, Иванчо не се справял с това да ги мие една по една, той измислил следната хитрост. На всяка идваща партида чинии той ги трупал една върху друга, ако това е възможно -- все пак той не искал да счупи чиниите и затова слагал само чинии с по-малък диаметър върху чинии с по-голям. Иванчо започвал от началото на поточната линия и трупал купчина с чинии до където може, след което я оставял на място и продължавал да строи нова купчина по същия начин. След като построял всички купчини, Иванчо все още не бил доволен. Затова се връщал отначало и минавал през всяка построена купчина, като се опитвал да я постави върху друга натрупана купчина след нея, като избирал първата възможна такава. За да бъде максимално ефективен, той повтарял процедурата докато остане с минимален брой купчини. Напишете програма, която приема редица от числа, разделени с интервал, представляваща диаметрите на чиниите от поточната линия, и извеждат на екрана описание на купчините от чинии, които са се получили в края.

Забележка: Диаметрите на всички чинии са положителни числа. Числото 0 отбелязва края на партидата от чинии.

Пример

Задача 2. (5 точки) Марийка била наета да мие чинии в кварталната кръчма "При кака Минка”. Заведението било толкова зле организирано, че Марийка била принудена да мие чинии на малка мивка, която имала място за мръсни чинии точно колкото за една купчинка. Докато тя миела, келнерите се редили на опашка, за да носят купчините мръсни чинии. Купчината до мивката, разбира се, нямало как да стане безкрайно висока и затова когато чиниите в купчината станели 15 или повече на брой, келнерите трябвало да изчакат отстрани Марийка да измие част от купчината преди да могат да сложат своите чинии. За щастие, келнерите не носели повече от 15 чинии наведнъж. Марийка всъщност била доста пъргава и миела чинии със скорост 7 чинии в минута. Келнерите пък били доста нетърпеливи и на всяка минута питали дали може да оставят чиниите си. Все пак, те били професионалисти и оставяли чиниите си на мивката само и единствено след като Марийка им казвала, че може да го направят (т.е. чиниите на мивката ставали по-малко от 15). Да се изведе поминутен дневник на събитията в миялното помещение на "При кака Минка” въз основа на предварително зададени данни за носените от келнерите чинии. Входните данни представляват списъци от цели числа, разделени с интервал, като всеки списък е на нов ред. всеки списък представлява купчината от чинии, носена от келнер, като числото 1 означава здрава чиния, 0 -- счупена. Марийка не мие счупени чинии, а направо ги хвърля, но за сметка на това те заемат място в нейната купчината чинии за миене.

Забележка: числото -1 във входните данни указва край на купчината с чинии, носена от съответния келнер или край на келнерите в случай, че е първото число на реда.

Пример

Задача 3. (5 точки) [Държавен изпит септември 2014 г.] Казваме, че двусвързаният списък L1 може да бъде „снаден" със списъка L2 в числото M, ако има кутия A в L1 и кутия B в L2, така че

• A.data и B.data са равни на M

• ако A е на разстояние X от началото на L1 И на разстояние Y от края на L1, то B е на разстояние X от края на L2 ИЛИ на разстояние Y от началото на L2

А) Да се реализира функция join, която „снажда" два списъка L1 и L2, ако това е възможно, както е показано на диаграмата долу. В случай, че снаждането може да се получи по няколко различни начина, да се избере този, при който, числото M е максимално. Получената структура наричаме „снаден списък".

Б) Да се реализира булева функция isJoined, която по двойка указатели към начало и края на двусвързана верига проверява дали веригата е снаден списък. Забележка: да се счита, че в подадената верига няма зацикляне.

В) Да се реализира функция sum, която по даден снаден списък намира сумата на всичките му елементи.

Задача 4. (5 точки) Целочислена функция се дефинира със следния синтаксис:

<функция>    ::= <сигнатура> = <израз>

<сигнатура>  ::= <име>(<променлива>)

<име>        ::= <латинска буква>

<променлива> ::= <латинска буква>

<израз>      ::= <израз><операция><израз> | (<израз>) | <терм>

<терм>       ::= <променлива> | <цяло число>

<операция>   ::= + | - | * | / | % | ^

<цяло число> ::= -<число> | <число>

<число>      ::= <цифра><число>

Операциите са с обичайния си приоритет: скобите са с най-висок приоритет, след това е степенуването (^) , следват умножение, частно и остатък, и с най-нисък приоритет са събиране и изваждане. Считаме, че a^b = 1, ако b ≤ 0.  Всички операции са лявоасоциативни. В дефиницията на функцията се среща само една променлива: тази, която е в сигнатурата на функцията. В дефиницията на функциите могат да се срещат интервали, които следва да бъдат пренебрегнати.

Да се напише програма, която прочита от файл две цели числа a и b и списък от дефиниции на функция (всяка на отделен ред) и след това извежда всички целочислени точки в интервала [a; b], където поне две от функциите се пресичат.

Пример