АСП1/К1 2020
1. задатак
Поставка
Нека је дата функција рандом() која враћа број 0 или 1 са подједнаком вероватноћом. Објаснити и илустровати примером како би се коришћењем задате функције имплементирала функција која враћа вредност 0 са вероватноћом 25%, а са 1 вероватноћом од 75%.
Решење
У оквиру наше нове функције позовемо функцију рандом два пута, и на пример само у случају када оба пута врати нулу тада наша нова функција враћа нулу, а за све остале случајеве (01, 10, 11) враћа један. На тај начин је обезбеђено да функција враћа 0 са вероватноћом 25%, а 1 са вероватноћом 75%.
2. задатак
Поставка
Нека је дат стек с1 на коме се налазе цели бројеви. Коришћењем додатног стека с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) do
num = cnt
tmp = 0
while (num) 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) 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