АСП1/К1 2020
1. задатак
Поставка
Нека је дата функција рандом() која враћа број 0 или 1 са подједнаком вероватноћом. Објаснити и илустровати примером како би се коришћењем задате функције имплементирала функција која враћа вредност 0 са вероватноћом 25%, а са 1 вероватноћом од 75%.
Решење
У оквиру наше нове функције позивамо функцију рандом два пута, и само у једном од четири случаја, на пример када оба пута функција врати нулу (00), наша нова функција враћа нулу, а за све остале случајеве (01, 10, 11) враћа један. На тај начин је обезбеђено да функција враћа 0 са вероватноћом 25%, а 1 са вероватноћом 75%.
NEW RANDOM(')
if (random() = 0) and (random() = 0) then
return 0
else
return 1
end_if
2. задатак
Поставка
Нека је дат стек с1 на коме се налазе цели бројеви. Коришћењем додатног стека с2, трансформисати садржај стека с1 тако да он постане неопадајуће уређен низ. Сматрати да су операције за рад са стеком већ имплементиране.
Решење
Идеја јесте да на стеку с1 имамо сортирани и несортирани део. На почетку сви елементи су у несортираном делу и одређујемо дубину стека и тренутни максимум на њему. Сваком наредном итерацијом све елементе који су мањи од максимума пребацујемо на стек с2, док све максимуме избацујемо са стека, а затим накнадно убацујемо онолико пута колико су се појавили. На крају, враћамо све не-максималне елементе са стека с2 назад у несортирани део стека с1, притом поново одређујући максимални елемент у несортираном делу. Процес се понавља док има елемената у максималном делу.
SORT STACK(s1)
max = TOP(s1)
cnt = 0
while (not STACK_IS_EMPTY(s1)) do
x = POP(s1)
if (x > max) then
max = x
end_if
PUSH(s2, x)
cnt = cnt + 1
end_while
while (not STACK_IS_EMPTY(s2)) do
x = POP(s2)
PUSH(s1, x)
end_while
while (cnt > 0) do
num = cnt
tmp = 0
while (num > 0) do
x = POP(s1)
if (x < max) then
PUSH(s2, x)
else
cnt = cnt - 1
tmp = tmp + 1
end_if
num = num - 1
end_while
for i = 1 to tmp do
PUSH(s1, max)
i = i + 1
end_for
if (cnt > 0) then
max = TOP(s2)
while (not STACK_IS_EMPTY(s2)) do
x = POP(s2)
if (x > max) then
max = x
end_if
PUSH(s1, x)
end_while
end_if
end_while
3. задатак
Поставка
Посматра се ретка матрица А величине НxМ. Матрица је дата у виду кружних уланчаних листи са заглављима РА и CА. Написати ефикасну итеративну функцију у псеудокоду која дату матрицу претвара у векторски формат са три посебна вектора Р, C и V. Функција такође треба да врати број ненултих елемената у матрици. Сматрати да је за све векторе иницијално резервисано довољно простора.
Решење
REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)
cnt = 1
for i = 1 to N do
curr = next(Ra[i])
R[i] = cnt
while (curr ≠ Ra[i]) do
C[cnt] = col(curr)
V[cnt] = val(curr)
cnt = cnt + 1
curr = next(curr)
end_while
end_for
R[N + 1] = cnt + 1
return cnt
4. задатак
Поставка
Трансформисати израз у инфиксном облику
- А+C^(D-Е!)!^Ф*Б-C+Г*Х
у еквивалентни израз у постфиксној форми. Табелу приоритета оператора допунити одговарајућим вредностима, при чему је операција факторијел ! унарна операција која се групише слева на десно и има највећи приоритет од свих аритметичких операција, а операција ^ је операција степеновања и групише се сдесна на лево. Трансформацију израза приказати по корацима.
Решење
| оператор | ул. пр | стек пр. | Р |
|---|---|---|---|
| +, - | 2 | 2 | -1 |
| *, / | 3 | 3 | -1 |
| ^ | 5 | 4 | -1 |
| ! | 6 | 6 | 0 |
| ( | 7 | 0 | - |
| ) | 1 | - | - |
Постфиксна форма датог инфиксног израза који се добије применом алгоритма за конверзију из инфикса у постфикс је:
- АЦДЕ!-!Ф^^Б*+C-ГХ*+
5. задатак
Поставка
Дата је ретко попуњена квадратна матрица 2Н x 2Н. Неподразумевани елементи матрице смештају се у меморији по врстама. Индексирање креће од 1, а сваки елемент матрице заузима по 2 речи.
- Извести адресну функцију за приступ произвољном елементу матрице.
- Имплементирати функцију ГЕТ која враћа вредност траженог елемента који одговара индексима и и ј матрице А.
Решење
- ГЕТ(А, и, ј, Н)
if (i = j or i + j = 2 * N + 1) then
return A[i, j]
else
return 0
end_if
6. задатак
Поставка
У неком азилу за животиње су збринути пси, мачке и канаринци. Када неко жели да усвоји животињу, он се може изјаснити да ли жели пса, мачку, канаринца или му је свеједно. Није могуће упутити захтев за одређеном (појединачном) животињом већ у складу са одабиром врсте, биће додељена или животиња тражене врсте која је најдуже у азилу, ако таква постоји, или животиња која је ту дуже од свих других. Такође, азил прихвата нове животиње док се не попуни капацитет.
- Укратко објаснити која структура се користи за моделовање азила и како се она одржава са доласком и усвајањем животиња.
- Приказати како ће структура усвојена под а) изгледати након усвајања једног пса, ако је приказано тренутно стање животиња у азилу по боксовима у којима су смештени. Поред врсте животиње, ради илустрације, у загради се налази и тренутно време боравка животиње у азилу.
- M(2) К(1) П(6) П(3) M(6) M(7) К(5) П(3)
Решење
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
7. задатак
Поставка
У неком програму је потребно преставити скуп целих бројева у опсегу од 0 до 999. Нека су у програмском језику који се користи на располагању целобројни типови на 4 бајта ширине, а показивачи заузимају 4 бајта. Објаснити на које начине се овакав скуп може представити секвенцијалном и уланчаном репрезантацијом, а затим одредити просечно заузеће простора у оба случаја под претпоставком да се у скупу у просеку налази 10 елемената.
Решење
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
8. задатак
Поставка
Написати у псеудокоду имплементацију функције која у двоструко уланчану листу целих бројева на коју указује показивач лист убацује вредност x испред елемента на који указује показивач ноде. Водити рачуна да листа остане у потпуно конзистентном стању.
Решење
Претпостављамо да је ноде валидан показивач на елемент који се налази у листи лист.
INSERT BEFORE D(list, node, x) new_node = Node(x) new_node.prev = node.prev new_node.next = node if node.prev == null list = new_node else node.prev.next = new_node node.prev = new_node