diff options
2 files changed, 198 insertions, 0 deletions
| -rw-r--r-- | src/teaching/upp-2023/index.md | 1 | ||||
| -rw-r--r-- | src/teaching/upp-2023/week6/index.md | 197 |
diff --git a/src/teaching/upp-2023/index.md b/src/teaching/upp-2023/index.md index f8b9f16..051880d 100644 --- a/src/teaching/upp-2023/index.md +++ b/src/teaching/upp-2023/index.md @@ -23,3 +23,4 @@ |4 |27.10.2023|[Преговор](./week4/revision.html?a) \|\| [Задачи](./week4) \|\| [GitHub classroom](https://classroom.github.com/a/jqKaO1ny) \|\| [Решения (само 1ва)](https://github.com/Syndamia/upp-2023-solutions/tree/main/week04)| |5 |03.11.2023|[Преговор](./week5/revision.html) \|\| [Задачи](./week5) \|\| [GitHub classroom](https://classroom.github.com/a/3KoIQ71H)| ||04.11.2023|[Допълнително упражнение 1](./additional1/) \|\| [GitHub classroom](https://classroom.github.com/a/nlFuKALw)| +|6 |10.11.2023|[Задачи](./week6) \|\| [GitHub classroom](https://classroom.github.com/a/BBLlWMOy)| diff --git a/src/teaching/upp-2023/week6/index.md b/src/teaching/upp-2023/week6/index.md new file mode 100644 index 0000000..991f987 --- /dev/null +++ b/src/teaching/upp-2023/week6/index.md @@ -0,0 +1,197 @@ +# Задачи - УПП, Седмица 6, 10.11.2023 + +GitHub classroom: [classroom.github.com/a/BBLlWMOy](https://classroom.github.com/a/BBLlWMOy) + +## Задача 1 + +Първо получавате две цели положителни числа: N и M. +След това ще получите редица числа, първите ще отговарят на матрица NxM (N реда, M стълба), вторите на матрица MxN. +Трябва да умножите първата матрица по втората, както следва обикновенното правило за умножение ред по стълб и да изкарате резултата на екрана. + +N и M са между 1 и 60. + +**Пример:** + +|Вход|Изход| +|----|-----| +|4 3<br>8 1 9<br>0 3 0<br>4 7 5<br>6 9 0<br>9 5 7 3<br>6 7 2 0<br>1 3 3 7<br>| 87 74 85 87<br>18 21 6 0<br>83 84 57 47<br>108 93 60 18<br>| + +## Задача 2 + +Разглеждаме числатата от 0 до N. +За всяко число знаем колко интервала го включват (покриват). +Тоест в `0 1 1 0` означава, че 0 интервала "покриват" числото 0, един интервал покрива числото 1, един интервал покрива числото 2 и 0 покриват числото 3. + +Търси се колко различни интервала имаме. +Не различаваме между два долепени интервала и един дълъг интервал. + +От входа получаввате N (от 1 до 30), и след това N на брой числа: броя покриващи интервали за всички числа от 0 до N-1. + +**Примери:** + +|Вход|Изход| +|----|-----| +|5<br>1 1 0 1 1|2| +|5<br>1 2 1 2 1|3| +|5<br>9 5 2 9 0|16| +|11<br>1 1 2 3 2 2 4 2 1 1 1|5| + +## Задача 3 + +Трябва да имплементирате дигитална версия на морски шах. +Всяка клетка е номерирана от 1 до 9, както на мобилен телефон или калкулатор. + +В началото изкарвате (празното) игрално поле, първо играе Х, след това О, и се редуват докато не завърши играта. +След като един играч избере своя ход, трябва да покажете игралното поле. +Ако след това излезе, че някой играч е спечелил, трябва да изкарате "PLAYER wins!" (където PLAYER е X или O) и да спрете програмата. + +В случай, че игралното поле се запълни и никой не е спечелил, след последното му изкарване трябва да върнете "Draw!" и да спрете програмата. + +**Пример:** +*Смесен вход/изход, вход е означен с "$ " преди него* + +``` + + + +$ 5 + + X + +$ 9 + + X + O +$ 3 + X + X + O +$ 7 + X + X +O O +$ 1 +X X + X +O O +$ 8 +X X + X +OOO +O wins! +``` + +**Бонус:** направете го да работи с NxN брой клетки, като N е число между 1 и 50. + +## Задача 4 + +Имплементирайте играта [chomp](https://en.wikipedia.org/wiki/Chomp): представете си, че имаме един шоколад, разделен на NxM квадратчета. +Всеки играч избира квадратче (координати), след това изяжда всички парчета, които са в дясно или надолу от квадратчето. +Играчът, който изяде квадратчето в горния ляв ъгъл губи играта. + +От входа получавате две числа, N и M, това е броя редове и колони в шоколада. +След това изкарвате шоколада, като с # маркирате неизядено квадратче, а с шпация - изядено. +Редуват се първия и втория играч, като всеки въвежда две числа - координати в шоколада (между 1 и N за реда и 1 и M за колоната). +Когато някой изяде парчето в горния ляв ъгъл, програмата изкарва "PLAYER wins!" (PLAYER е 1 или 2) и спира изпълнение. + +**Пример** +*Смесен вход/изход, вход е означен с "$ " преди него* + +``` +4 5 +##### +##### +##### +##### +$ 3 5 +##### +##### +#### +#### +$ 4 2 +##### +##### +#### +# +$ 1 2 +# +# +# +# +$ 2 1 +# + + + +$ 1 1 + + + + +2 wins! +``` + +## Задача 5 + +**Тази задача е много трудна, proceed with caution!** + +Ще имплементираме програма, която "симулира" един елементарен компютър. +Компютъра ни, като всеки друг, работи само и единствено с цели неотрицателни числа. +Неговата (използваема) памет е разделена на две части: два "регистъра", наречени А и B, и "RAM" памет (един масив) с 128 стойности. + +В началото въвеждаме програма (разбира се това са числа), която трябва да бъде поставена в RAM паметта. +Първото число е инструкция, следващите няколко числа са нейни аргументи, и след това имаме друга инструкция. +Започваме изпълнение от началото на паметта, след като изпълним една инструкция, изпълняваме тази директно до нея, и така докато не стигнем инструкцията "EXT". +В такъв случай, изкарваме стойността в регистър B и спираме програмата. + +Това са командите, описани във формата "D - `A B C`", като D е число, съответстващо на инструкцията с име `A` (името го използваме за нас, в кода то не присъства) и аргументи след името `B` и `C`. +`MEMORY` е число, съответстващо на индекс (адрес) в паметта на компютъра (между 0 и 127), а `VALUE` е произволна числова стойност. + +- 0 - `EXT` - край на изпълнението на програмата в симулирания компютър + +- 1 - `INC MEMORY` - инкрементира стойността на индекс `MEMORY` + Пример: `0 2` - инкрементира стойността на индекс 2 + +- 2 - `RIN VALUE MEMORY` - инкрементира стойността на индекс `VALUE + MEMORY` + Пример: `1 3 6` - инкрементира стойността на адрес `3 + 6 = 9` + +- 3 - `DEC MEMORY` - декрементира стойността на индекс `MEMORY` + +- 4 - `RDE VALUE MEMORY` - декрементира стойността на индекс `VALUE + MEMORY` + +- 5 - `STA MEMORY` - запазва стойността на индекс `MEMORY` в регистъра А + Пример: `4 19` - запазва стойността на индекс 19 в регистъра А + +- 6 - `RST VALUE MEMORY` - запазва стойността на адрес `VALUE + MEMORY` в регистър А + Пример: `5 2 14` - запазва стойността на индекс `2 + 14 = 16` в регистър А + +- 7 - `STB MEMORY` - запазва стойността на индекс `MEMORY` в регистъра B + +- 8 - `BEQ MEMORY` - продължава изпълнение от индекс `MEMORY`, ако стойността в регистъра А е нула + Пример: `7 8` - продължава изпълнение от индекс 8, ако стойността в регистър А е нула + +- 9 - `BNE MEMORY` - продължава изпълнение от индекс `MEMORY`, ако стойността в регистъра А не е нула + +В началото получавате N, това са броя числа, които съставят цялата програма. +След това се въвеждат N числа, които са цялата програма. + +Ако по време на изпълнение стигнете до инструкция, която не е дефинирана, изкарвате "Error: undefined instruction!" и спирате програмата. +Ако някой аргумент е индекс в паметта, обаче стойността му е извън обхвата на паметта, изкарвате "Error: invalid memory address!" и спирате програмата. + +Ако няма грешка и програмата успешно стигне до `EXT` инструкция, както беше казано, изкарваме на екрана стойността в регистъра B. + +**Примери:** + +|Вход|Изход| +|----|-----| +|3 10 8 0|Error: undefined instruction!| +|3 5 8000 0|Error: invalid memory address!| +|6 1 3 7 3 0 958|959| +|17 5 9 8 6 1 8 3 9 5 9 9 2 7 8 0 91461 772000|863461| + +&&question Какво прави последната програма? + +**Бонус:** направете програми за симулаторния компютър, които + +1. умножават числата 87401 и 37 +2. намира сумата на числата 87, 305, 2, 612, 222 |