Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: вежбе - VIII недеља

Задатак 1

Написати функцију која враћа најучесталији карактер ниске.

Решење
def najcesci_karakter_niske(niska):
    """
    Написати функцију која враћа најучесталији карактер ниске.
    """
    recnik = {}

    for karakter in niska:
        if karakter in recnik:
            recnik[karakter] +=1
        else:
            recnik[karakter] = 1

        #ovaj if else iskaz menja samo
        #recnik[karakter] = recnik.get(karakter,0) + 1

    return max(recnik, key = recnik.get)  


niska=input()
print(najcesci_karakter_niske(niska))

Задатак 2

Написати функцију коjа враћа сортиран низ свих кључева улазног речника коjи имаjу задату циљану вредност, а уколико пак таквих кључева у речнику нема, функција ће вратити празан низ.

Додатно објашњење: Функција прима речник чиjи су кључеви цели броjеви, а вредности су му произвољне, док враћа сортиран низ кључева унетог речника коjи су повезани на задату вредност.

Решење
def ciljaneVrednosti(recnik, vrednost):
    nizKljuceva = []
    for kljuc in recnik:
        if recnik[kljuc] == vrednost:
            nizKljuceva.append(kljuc)
    
    return sorted(nizKljuceva)

print(ciljaneVrednosti({46:23,23:32,4:82,7:23,6:23,5:23},23))

Задатак 3

Написати функцију коjа врши инверзиjу речника са непроменљивим вредностима. Инверзни речник почетног речника jесте нов речник чиjи су кључеви заправо вредности изворног речника. Вредности инверзног речника су сортирани низови свих кључева почетног речника повезаних на задату вредност.

Пример:

{1:10, 2:20, 3:30} -> {10: [1], 20: [2], 30: [3]}

{1:10, 2:20, 3:30, 4:30} -> {10: [1], 20: [2], 30: [3, 4]}

{4:True, 0:True, 2:True} -> True: [0, 2, 4]

Решење
def inverzni_recnik(recnik):
    """
    Написати функцију коjа врши инверзиjу речника са непроменљивим вредностима. Инверзни речник
    почетног речника jесте нов речник чиjи су кључеви заправо вредности изворног речника. Вредности
    инверзног речника су сортирани низови свих кључева почетног речника повезаних на задату вредност.
    Пример:
    {1:10, 2:20, 3:30} -> {10: [1], 20: [2], 30: [3]}
    {1:10, 2:20, 3:30, 4:30} -> {10: [1], 20: [2], 30: [3, 4]}
    {4:True, 0:True, 2:True} -> True: [0, 2, 4]
    """
    inverzni = {}
    for kljuc, vrednost in recnik.items():
        if vrednost in inverzni:
            inverzni[vrednost].append(kljuc)
        else:
            inverzni[vrednost] = [kljuc]
        inverzni[vrednost].sort()
    return inverzni

recnik1={1:10, 2:20, 3:30}
recnik2={1:10, 2:20, 3:30, 4:30}
recnik3={4:True, 0:True, 2:True}

print(inverzni_recnik(recnik1))
print(inverzni_recnik(recnik2))
print(inverzni_recnik(recnik3))

Задатак 4

Дат је низ бројева. Желимо да наш низ постане монотоно растући низ. То можемо да средимо само инкрементовањем чланова низа. Написати функцију која враћа минималан број инкрементовања.

Решење
def minOperacija(niz):
    """
    Дат је низ бројева. Желимо да наш низ постане монотоно растући низ.
    То можемо да средимо само инкрементовањем чланова низа.
    Написати функцију која враћа минималан број инкрементовања.
    Пример:
    [1,1,1]     -> 3, јер желимо да добијемо [1,2,3]
    [1,5,2,4,1] -> 14, јер желимо да добијемо [1,5,6,7,8]
    """
    brojac = 0
    for i in range(1,len(niz)):
        if niz[i]<=niz[i-1]:
            razlika = niz[i-1]-niz[i]+1 #колико треба да инкрементујемо да би постао већи за 1
            brojac += razlika
            niz[i] = niz[i-1]+1 #сада је већи за 1
    return brojac
    

Задатак 5

Размотримо следећу секвенцу бројева: 0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9… Нулти елемент је једнак 0, а први елемент једнак 1. Сваки следећи елемент је дефинисан рекурзивно, и он је једнак збиру цифара претходна два. Написати функцију која ће вратити н-ти члан овако дефинисане секвенце бројева.

Решење
def sekvenca_brojeva(n):
    """
    Размотримо следећу секвенцу бројева:
    0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9..
    Нулти елемент је једнак 0, а први елемент једнак 1.
    Сваки следећи елемент је дефинисан рекурзивно, и он је једнак збиру цифара претходна два.
    Написати функцију која ће вратити н-ти члан овако дефинисане секвенце бројева.
    Пример:
    н = 2 -> 1
    н = 6 -> 8
    н = 10 -> 10
    """
    def zbir_cifara(broj):
        s = 0
        while broj>0:
            s += broj%10
            broj //= 10

        return s
        
    if n == 0 or n ==1:
        return n

    return zbir_cifara(sekvenca_brojeva(n-1)) + zbir_cifara(sekvenca_brojeva(n-2))

Задатак 6

Написати функцију која ће вратити максималан број карактера ‘a’ који се могу додати у улазну ниску тако да резултујућа ниска нема 3 узастопна таква карактера. Уколико улазна ниска већ има 3 узастопна карактара ‘a’ вратити -1.

Решење
def koliko_karaktera_a(niska):
    """
    Написати функцију која ће вратити максималан број карактера 'a' који се могу додати у улазну ниску 
    тако да резултујућа ниска нема 3 узастопна таква карактера.
    Уколико улазна ниска већ има 3 узастопна карактара 'a' вратити -1.
    Пример:
    niska = 'aabab' -> 3, резултућа ниска је 'aabaabaa'
    niska = 'dog'   -> 8, резултућа ниска је 'aadaaoaagaa'
    niska = 'aa'    -> 0, резултућа ниска је 'aa' 
    niska = 'baaa'  -> -1, већ постоји 'aaa'.
    """
    brojac = 0
    brojac_a = 0
    for char in niska:
        if char == 'a':
            brojac_a+=1
            if brojac_a == 3:
                return -1
        else:
            brojac += 2-brojac_a
            brojac_a=0

    brojac += 2-brojac_a
    return brojac
    

Задатак 7

Дат је низ цене где је цене[i] цена акције i-тог дана. Желимо да максимизујемо наш профит тако што ћемо изабрати ког дана ћемо купити акцију и ког дана ћемо је продати. Уколико не можемо да профитирамо, нећемо купити ниједну акцију, па ће наш профит бити 0. Написати функцију која ће за улазни низ цена вратити колико максимално можемо да профитирамо.

Решење
def maxProfit(cene):
    """
    Дат је низ цене где је цене[i] цена акције i-тог дана.
    Желимо да максимизујемо наш профит тако што ћемо изабрати ког дана ћемо купити акцију и ког дана ћемо је продати. 
    Уколико не можемо да профитирамо, нећемо купити ниједну акцију, па ће наш профит бити 0.
    Написати функцију која ће за улазни низ цена вратити колико максимално можемо да профитирамо.
    Пример:
    цене = [7,1,5,3,6,4] -> 5, купићемо 1-ог дана, када је цена једнака 1, и продати 4-ог када је цена једнака 6.
    цене = [7,6,4,3,1]   -> 0, нећемо купити јер не можемо да зарадимо.
    """
    indeks_najmanje_cene = 0
    maks = 0
    for i in range(len(cene)):

        maks = max(maks,cene[i]-cene[indeks_najmanje_cene])

        if cene[i] < cene[indeks_najmanje_cene]:
            indeks_najmanje_cene = i

    return maks