Задачи - УПП, Седмица 9, 01.12.2023

GitHub classroom: classroom.github.com/a/lGXxCRZO

Освен ако не е казано друго, може да зачитате, че максималната дължина на един низ е 1024 знака.

Задача 1

Получавате от входа два низа. Трябва да изкарате на екрана низ, при който има знакът “_” на индексите, където буквите между двата низа се различават, и съответната буква, когато не се различават.

Пример:

Задача 2

От входа получавате число N и на следващия ред получавате низ с толкова на брой знака. Изкарайте на екрана втората половина от низа и след това директно долепена първата половина. Ако низа е с нечетна дължина, зачитаме средния елемент като част от втората половина.

Трябва да използвате динамична памет

Примери:

Задача 3

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

Примери:

This , is ,      a , sentence    .!

Задача 4

Една от ранните програми за Apple I компютърът, написана от Steve Wozniak в упътването на компютъра, е така наречената “Woz Monitor”, или wozmon за картко. Тя позволява да погледнеш стойностите в клетки от паметта, да запишеш стойности и да стартираш програми.

Игнорирайки последната му възможност, нека да го имплементираме. За нашите цели, паметта на компютъра е просто един масив, които ще расте когато е нужно. Ще адресираме (индексираме) стойностите от масива с числа от 16-тична бройна система.

Когато въведем низ във формата:

• “адрес”, без нищо друго на реда, изкарваме “X: V”, където X е конкретния адрес (пак в 16-тична бройна система) и V е стойността на клетката в този адрес.

• “адрес.адрес”, връщаме стойностите между тези адреси (включително) във формата “X: V …”, където X е начален адрес и “V …” са стойностите на всяка клетка.

  Допълнително, ако изкарваме повече от 8 адреса, трябва да продължим на нов ред, като изкараме в същия формат. Пример: вход: “0.А”, изход:

  0: 0 0 0 0 0 0 0 0
  8: 0 0 0
  

• “адрес: стойност”, записваме “стойност” на дадения адрес. Стойноста също е 16-тично число. Трябва да върнем старата стойност в адреса (във формата “X: V”).

• “адрес: стойност …”, като предходното, обаче може да определим стойностите на сегашната и на следващите клетки (пак изкарваме във формата “X: V …”)

Примери:

Задача 5

Перфокартите са стар формат за съхраняване на текст (код) върху хартиен носител, който е четим от машини. Разделени са на някакъв брой редове и колони, всяка колона определя една буква, и всеки ред определя битовите стойности на всяка буква, като дупката означава бит 1, а липсата и бит 0.

За удобство на програмиста, почти винаги най-отгоре на колоната се изписва с мастило каква е буквата на съответната колона.

Трябва да имплементирате програма, която получава перфо карти в стандартния IBM формат: 12 реда и 80 колони и изкарва съответния ред, който е закодиран.

Тоест, от входа получавате 12 низа, всеки низ е с дължина 80, и са съставени от 0 и 1.
Стойностите по колони:

• от “100000000000” до “000000000001” (със само една 1ца) съответстват на знаците “&”, “-”, “0”, “1”, … “9”.
• от “100100000000” до “100000000001” (с две 1ци, едната която е винаги първата) съответстват на знаците от “A” до “I”.
• от “010100000000” до “010000000001” (с две 1ци, едната която е винаги втората) съответстват на знаците от “J” до “R”.
• от “001100000000” до “001000000001” (с две 1ци, едната която е винаги третата) съответстват на знаците “/”, “S”, … “Z”.

Пример:

Задача 6

Регулярните изрази са низове, които позволяват да опишем шаблони, с които да филтрираме/приемаме низове. Вие ще ги изучавате много подробно в “Езици, автомати и изчислимост”, но за нашите цели ще се абстрахираме от детайлите.

Правилата за регулярни изрази са следните:

• ако е буквата “*”, значи предходната буква може да се повтаря 0 или повече пъти

• ако е буквата “?”, значи предходната буква може да се повтаря 0 или 1 пъти

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

1. Какво описва регулярният израз aa*bcd?

   Първата буква от нашия низ трябва да бъде а. След това имаме a*, след тази първа буква може да имаме 0 или повече a-та. Тоест втората буква може да бъде a или b, ако е a, третата буква може да бъде a или b, обаче ако втората буква е b, тогава продължаваме напред и останалите букви трябва да са bcd.

   Тоест, този регулярен израз приема низове, които започват с a, след това имат 0 или повече a-та и завършват на bcd. Следните низове ще бъдат приети: “abcd”, “aabcd”, “aaabcd”, “aaaabcd” и так. нат.

2. Какво описва регулярният израз b*cd??

   В началото имаме b нула или повече пъти, след това имаме c и накрая имаме нула или едно d. Следните низове ще бъдат приети: “c”, “bc”, “bbc”, “bbbc”, …, “cd”, “bcd”, “bbcd”, …

От входа получавате число N и след това ще получите 2N на брой редове. Един ред ще бъде регулярен израз, следващия ще бъде низ за проверка, след това пак регулярен израз, след това пак низ за проверка и така се редуват.

След всеки регулярен израз и низ за проверка, проверявате дали низа се приема от регулярния израз, и изкарвате “Matched”. В противен случай изкарвате “No match”. Ако регулярния израз е в грешен формат (срещнете “?” или “*” като първи знак), трябва да изкарате “Bad regex”.

Пример: Смесен вход/изход

9
text
text
Matched
text
test
No match
a*
a
Matched
ca*
c
Matched
ca*
caaaa
Matched
n?
n
Matched
mn?
m
Matched
0*573
0000005723
No match
*abc
ops
Bad regex