Задачи - УПП, Седмица 6, 10.11.2023

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

Задача 1

Първо получавате две цели положителни числа: N и M. След това ще получите редица числа, първите ще отговарят на матрица NxM (N реда, M стълба), вторите на матрица MxN. Трябва да умножите първата матрица по втората, както следва обикновенното правило за умножение ред по стълб и да изкарате резултата на екрана.

N и M са между 1 и 60.

Пример:

Задача 2

Разглеждаме числатата от 0 до N. За всяко число знаем колко интервала го включват (покриват). Тоест в 0 1 1 0 означава, че 0 интервала “покриват” числото 0, един интервал покрива числото 1, един интервал покрива числото 2 и 0 покриват числото 3.

Търси се колко различни интервала имаме. Не различаваме между два долепени интервала и един дълъг интервал.

От входа получаввате N (от 1 до 30), и след това N на брой числа: броя покриващи интервали за всички числа от 0 до N-1.

Примери:

Задача 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: представете си, че имаме един шоколад, разделен на 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.

Примери:

Какво прави последната програма?

Бонус: направете програми за симулаторния компютър, които

1. умножават числата 87401 и 37
2. намира сумата на числата 87, 305, 2, 612, 222