From 5102f9fa83c5204f7d6e86a5a61548f2138cb25c Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 26 Oct 2023 23:22:07 +0300 Subject: (te/upp-2023/w4) Added almost complete draft of exercises --- src/teaching/upp-2023/week4/index.md | 164 +++++++++++++++++++++++++++++++++++ 1 file changed, 164 insertions(+) create mode 100644 src/teaching/upp-2023/week4/index.md diff --git a/src/teaching/upp-2023/week4/index.md b/src/teaching/upp-2023/week4/index.md new file mode 100644 index 0000000..8c865de --- /dev/null +++ b/src/teaching/upp-2023/week4/index.md @@ -0,0 +1,164 @@ +# Задачи - УПП, Седмица 4, 26.10.2023 + +## Задача 1 - Числен редактор + +Получавате число `N`, което ще е в обхвата от 1 до TODO. +Вашата програма трябва да поддържа няколко операции върху това число, включително копиране на редица от цифри в него и поставянето им в друга част на числото. + +Първо, в тази задача индексите на цифрите в едно число започват от 1 и се броят от ляво на дясно. +Тоест, в числото "481395" на индекс 1 имаме 4, на индекс 2 имаме 8 и на индекс 6 имаме 5. + +Всичките операции трябва да бъдат отделени във функции. +Затова, и за улеснение, задачата е разделена на стъпки: + +**ВАЖНО:** В решението **НЕ** може да изполвате масиви, вектори, ..., както и каквито и да е функции, които не сте написали вие! + +### Подточка а) Примитивните функции + +За да имплементираме всички нужни функционалности, първо ще направим няколко супер удобни функции, чрез които ще изразим останалите операции. + +Имплементирайте функциите: + +- `get`, която приема число, начален индекс и краен индекс (в този ред) + Тя връща подчислото, което започва от началния и завършва в крайния индекс. + + Пример: `get(481395, 2, 4)` връща `813` + +- `remove`, която приема число, начален индекс и дължина (в този ред) + Връща числото, без "дължина" на брой цифри от началния индекс + + Пример: `get(481395, 3, 3)` връща `485` + +- `insert`, която приема число, краен индекс, дължина и число за вмъкване + Връща числото, като на стария краен индекс намираме края на вмъкнатото число с дължина "дължина" + Ефектът, е че числото се вмъква на дадения индекс, обаче избутва цифрите в ляво от него, вместо тези от дясно. + + Пример: `insert(495, 2, 4, 1001)` връща `4910015` + +### Подточка б) Композитните функции + +Сега е време да имплементираме съществената логика в задачата. +Използвайки **само** примитивните функции, имплементирайте функциите: + +- `copy`, която приема число, начален индекс, дължина и втори начален индекс + Връща числото, като от втория начален индекс, следващите "дължина" на брой цифри съвпадат с "дължина" на брой цифри от първия начален индекс + + Пример: `copy(481395, 3, 4, 2)` връща `4139581395` + +- `cut`, която приема число, начален индекс, дължина и втори начален индекс + Връща числото, като "дължина" на брой цифри от (стария) начален индекс са преместени във втория начален индекс + + Пример: `cut(481395, 3, 4, 2)` връща `413958` + +- `replace`, която приема число, начален индекс, дължина и число за замяна + Връща числото, като "дължина" на брой цифри от начален индекс са заменени с числото за замяна + Заменените цифри и числото за замяна **може да имат различни дължини**! + + Пример: `replace(481395, 4, 2, 705)` връща `4817055` + +- `prepend`, която приема две числа + Връща долепени второто и първото число + + Пример: `prepend(395, 81)` връща `81395` + +- `append`, която приема две числа + Връща долепени първото и второто число + + Пример: `append(395, 81)` връща `39581` + +### Подточка в) Вход и изход + +Последно, време е да имплементираме интерфейса на програмата. +Както вече казахме, първия вход е числото `N` с което ще извършим операция. + +След това приемаме буква, която определя нашата (композитна) функция, като за всички функции използваме първата буква в името им, освен за `cut`, за която използваме `x`. +Тоест, `c` означава, че ще "copy"-ваме, `p` че ще "prepend"-ваме, `x` че ще "cut"-ваме и так. нат. + +След като въведем буква, трябва да приемем съответния за дадената функция брой аргументи и да изкараме на екрана резултата от функцията. + +**Примери** + +|Вход|Изход| +|----|-----| + +## Задача 2 - Умножение на полиноми + +Представяме полином чрез две числа, първото побитово определя дали x на конкретната степен съществува, докато второто определя коефициента (като цифра) пред всеки член, без значение дали съществува в полинома. + +Пример: първото число е 13, a второто е 3052. +Побитово `13 = 1101`, тоест ще имаме + +``` +x³ * 1 + x² * 1 + x¹ * 0 + x⁰ * 1 +``` + +След това, от второто получаваме всеки коефициент, става + +``` +3 * x³ * 1 + 0 * x² * 1 + 5 * x¹ * 0 + 2 * x⁰ * 1 +``` + +Финално, нашия полином, кодиран от числата 13 и 3052 е `3x³ + 2`. + +От входа получавате два полинома, трябва да ги умножите и да изкарате получилия се полином (пак във формата с две числа). + +**ВАЖНО:** В решението **НЕ** може да изполвате масиви, вектори, ..., както и каквито и да е функции, които не сте написали вие! + +## Задача 3 - Дъската на Зар + +*Името си го измислих, няма връзка с нещо :)* + +Дъската на Зар е една много проста игра. +Имаме два играча, които играят върху квадратна дъска, като на всяка "клетка" има цифра (0 до 9). +Всеки играч има сегашната си позиция върху дъската и брой точки. + +В един ход, един играч поглежда какво число има върху дъската на неговата позиция. +След това той се премества толкова "клетки" надясно от сегашната позиция. +На новата позиция, на която е попаднал, поглежда каква цифра има върху дъската и добавя толкова на брой точки към досегашния си сбор. +Накрая играча се премества с още една клетка надясно и алгоритъма започва пак. +Неговия ход свършва чак когато няма достатъчно клетки в реда, и тогава броя премествания надясно продължава на следващия ред в дъската (и следващия му ход). + +Пример: ако играем с дъска 5х5, намираме се на реда "25486" и позицията на първия играч е първата, тогава ходът му изглежда така (с "V" показваме къде се намира): + +``` +V +25486 +Прочита цифрата 2, значи трябва да се премести с две клетки на дясно + + V +25486 +Прочита цифрата 4, събира я към общия брой точки, сега се премества с една клетка на дясно + + V +25486 +Прочита цифрата 8, трябва да се премести с осем клетки на дясно +Обаче редът е твърде къс, премества се с една клетка и на следващия си ход ще се премести със 7 клетки надясно +``` + +Обаче, правилата между първия и втория играч са малко по-различни. +Първия играч започва от първата клетка на първия ред, докато втория започва от първата клетка, до която първия играч не е бил. + +Тоест, ако първия ни ред е "131324" (в дъска 6x6), тогава първия играч ще посети първите 5 клетки (и ще има 6 точки), и чак тогава ще дойде реда на втория играч, който ще започне с 6тата клетка. +Възможно е първия играч да посети всяка клетка в първия ред (примерно "131313"), и тогава втория играч ще трябва да се пробва да започне от втория ред. +Възможно е през цялата игра втория играч никога да не започне. + +Допълнително, ако втория играч започне и се озове на клетка, която е вече посетена от първия играч, тогава втория не получава точки и се връща в незапочнато състояние. +Пробва се да започне отново на същия ред, и ако успее, продължава хода си нормално. + +Накрая на играта, трябва да сравните точките на първия и втория играч и да изкарате кой е победил (или дали никой не е). + +Един ред може да се представи като цяло число и обработваме ред по ред, без да се връщаме назад. +Тоест, първо от входа получавате число `N`, което е размера на дъската. +След това ще получавате `N` числа, всяко с `N` цифри в десетичния си запис, като след получаване на едно число изпълнявате ходовете на всички играчи. + +**ВАЖНО:** В решението **НЕ** може да изполвате масиви, вектори, ..., както и каквито и да е функции, които не сте написали вие! + +**Упътване:** +Лесно се получава, ако занулим цифрите които първия играч е посетил. +Още по-лесно става ако използвате функции от първата задача. + +**Примери** + +|Вход|Изход| +|----|-----| + -- cgit v1.3.1-23-gd82d