АСП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

5. задатак

Поставка

Дата је ретко попуњена квадратна матрица 2Н x 2Н. Неподразумевани елементи матрице смештају се у меморији по врстама. Индексирање креће од 1, а сваки елемент матрице заузима по 2 речи.
а) Извести адресну функцију за приступ произвољном елементу матрице.
б) Имплементирати функцију ГЕТ која враћа вредност траженог елемента који одговара индексима и и ј матрице А.

Решење

$a)$
$A_{ij} = ((i-1)*2+\left\lfloor{(j-1)/N)}\right\rfloor)*2$ ∧ $(i=j$ ∨ $i+j=2N+1)$
$A_{ij} = 0$ ∧ $(i$≠$j$ ∧ $i+j$≠$2N+1)$
$b)$

GET(A, i, j, N)
if (i = j or i + j = 2 * N + 1) then
    return A[i, j]
else 
    return 0
end_if