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

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

View on GitHub

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

Задатак 1

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

Решење
def ravnanje(niz):
    """
    Написати функцију за поравнавање низа. Улазни низ може бити празан, а може садржати и ма коjи 
    други тип података укључуjући и низове коjи такође могу садржати низове до произвољне дубине.
    Пример:
    [[1,'a',['zec'],2],[[[3]],'pas'],4,5] -> [1, 'a', 'zec', 2, 3, 'pas', 4, 5]
    """

    if niz == []:
        return niz
    if type(niz[0]) == list:
        return ravnanje(niz[0]) + ravnanje(niz[1:])
    return niz[:1] + ravnanje(niz[1:])

Задатак 2

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

Решење
def duboko_brojanje(niz,vrednost):
    """
    Написати функцију коjа прима низ произвољно дубоко угнежђених низова броjевних вредности и
задати броj, а враћа колико се укупно пута таj броj поjављуjе у улазном низу на произвољноj дубини.
    Пример:
    niz = [3,[[2,[3],4],[[[[3]]]],[3,5,[7]]],3]
    vrednost = 3 -> 5
    """
    if niz == []:
        return 0
    if type(niz[0]) == list:
        return duboko_brojanje(niz[0], vrednost) + duboko_brojanje(niz[1:], vrednost)
    return int(niz[0] == vrednost) + duboko_brojanje(niz[1:], vrednost)
    

Задатак 3

Написати програм коjи за дати низ $A$, и величину “прозора” $К$ прави нови низ $B$ на следећи начин:

Решење
K = int(input())
A=list(map(int,input().split()))
N=len(A)
B=[0 for _ in range(N)]

for i in range(N):
    if i+1<K:
        B[i]=A[i]
    else:
        B[i]=sum(A[i-K+1:i+1])//K
print(B)    

Задатак 4

Броj 6174 коjи jе такође познат и као такозвана Капрекарова константа поседуjе jедно занимљиво своjство. Наиме, полазећи од произвољног четвороцифреног броjа код кога нису све цифре међусобно jеднаке (дакле изузимаjући ту 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888 и 9999), или чак и од jедноцифреног, двоцифреног или троцифреног броjа коjи бива проширен водећим нулама до четворо- цифреног, и примењуjући на њега следећи алгоритам увек се долази до Капрекарове константе 6174:

Решење
def kaprekarova_konstanta(broj):
    """
    Пример:
    broj = 2111 -> 5
    broj = 9831 -> 7
    """
    brojac = 0
    while broj != 6174:
        brojac += 1
        broj = list(str(broj))
        while len(broj) < 4:
            broj.insert(0, '0')
        veci = int(''.join(sorted(broj, reverse=True)))
        manji = int(''.join(sorted(broj, reverse=False)))
        broj = veci - manji
        
    return brojac

Задатак 5

Написати програм коjи за унето n исписуjе следећу фигуру:

За $n = 8$:

11111111
12222222
12333333
12344444
12344444
12333333
12222222
11111111

За $n = 5$:

11111
12222
12333
12222
11111
Решење
n=int(input())
niz=[1 for i in range(n)]
def figura(niz,i=1):
    if i>=(len(niz)/2+1):
        return
    niz[i-1:]=[i for _ in range(len(niz)-i+1)]
    print(niz)
    figura(niz[::],i+1)
    if i<=(len(niz)/2):
        print(niz)

figura(niz)

Задатак 6

Написати програм коjи проверава да ли се jедна матрица налази унутар друге матрице. Уколико се налази, одштампати $DA$, у супротном одштампати $NE$.

Пример 1:

Улаз:

3 5
1 1 2 3 3
4 4 5 6 6
7 7 8 9 9
2 3
1 2 3
4 5 6

Излаз:

DA

Пример 2:

Улаз:

2 3
1 1 2
2 1 1
2 2
1 1
1 1

Излаз:

NE
Решење
n1, m1 = map(int, input().split())
matrica1 = []
for i in range(n1):
    red = list(map(int, input().split()))
    matrica1.append(red)

n2, m2 = map(int, input().split())
matrica2 = []
for i in range(n2):
    red = list(map(int, input().split()))
    matrica2.append(red)


def daLiSuIste(matrica1, matrica2, redovi, kolone):
    rezultat = True
    for i in range(redovi):
        for j in range(kolone):
            if matrica1[i][j] != matrica2[i][j]:
                rezultat = False
                break
    return rezultat

i = 0
resenje = False
while (i <= n1-n2):
    j = 0
    while(j<= m1-m2):
        trenutna_matrica = []
        for x in range(i, i+n2):
            trenutni_red = []
            for y in range(j, j+m2):
                trenutni_red.append(matrica1[x][y])
            trenutna_matrica.append(trenutni_red)
        if(daLiSuIste(trenutna_matrica, matrica2, n2, m2)):
            resenje = True
            break
        j += 1
    i += 1
    
if(resenje):
    print("DA")
else:
    print("NE")

Задатак 7

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

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

Решење
def jedinstveneVrednosti(r):
    tempDict = {}
    uniqueValues = []
    uniqueKeys = []
    for value in r.values():
        tempDict[value] = value in tempDict
    for key in tempDict:
        if not tempDict[key]:
            uniqueValues.append(key)
    for (key, value) in r.items():
        if value in uniqueValues:
            uniqueKeys.append(key)
    uniqueKeys.sort()
    
    return uniqueKeys

#print(jedinstveneVrednosti({1: 5, 76: 432, 9: 5, 8: 12, 11: 5}))

Задатак 8

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

Кључеви речника пресека су заjеднички кључеви $rA$ и $rB$, а кључеви речника разлике су кључеви коjи се поjављуjу искључиво у jедном од речника $rA$ и $rB$.

Вредности речника пресека добиjаjу се као збир вредности за одговараjуће кључеве из $rA$ и $rB$, док су вредности речника разлике непромењене.

Решење
def presekRazlika(rA, rB):
    presek = {}
    for kljuc in rA:
        if kljuc in rB:
            presek[kljuc] = rA[kljuc] + rB[kljuc]
    razlika = {}
    for kljuc in rA:
        if kljuc not in rB:
            razlika[kljuc] = rA[kljuc]
    for kljuc in rB:
        if kljuc not in rA:
            razlika[kljuc] = rB[kljuc]

    return (presek, razlika)
    #return (dict(sorted(presek.items())), dict(sorted(razlika.items())))

#print(presekRazlika({1: 30, 2: 20, 3: 30, 5: 80},  {1: 40, 2: 50, 3: 60, 4: 70, 6: 90}))

Задатак 9

Написати функциjу коjа врши конкатенирање садржаjа $n$ различитих речника и на таj начин формира нови речник. Одштампати добиjени речник.
Садржаj речника коjе jе потребно конкатенирати учитава се са стандардног улаза. У првом реду на стандардном улазу прослеђуjе се броj $n$.
У наредних $n$ редова прослеђуjе се садржаj одговараjућег речника у следећем формату:
$kljuc_1\ vrednost_1\ kljuc_2\ vrednost_2\ … kljuc_m\ vrednost_m$

Решење
def konkateniranje_recnika():
    mojRecnik = dict()
    n = int(input())
    while n>0:
        trenutniRed = list(input().split())
        for i in range(0, len(trenutniRed), 2):
            mojRecnik[int(trenutniRed[i])] = trenutniRed[i+1]
        n -= 1
    
    return mojRecnik
    
print(konkateniranje_recnika())

Задатак 10

Jедноцифрени и двоцифрени броjеви у мандаринском кинеском jезику прате три jедноставна правила:

Решење
def mandarinski_broj(broj):
    """
    Jедноцифрени и двоцифрени броjеви у мандаринском кинеском jезику прате три jедноставна правила:
    • за сваку од цифара, односно за сваки од броjева између 0 и 10 постоjи засебна реч;
    • броjеви од 11 до 19 се изговараjу као “десет цифра”, где jе цифра реч за цифру између 1 и 9;
    • броjеви од 20 до 99 се изговараjу као “цифра десет цифра”, изузев нуле коjа се не изговара.
    Следећи речник коjи преводи све броjеве од нуле до десет на мандарински jе већ у вашем окружењу.
    бројеви = {'0': ’линг’, '1': 'jи','5': ’ву’,'6': ’љу’,'2': ’ер’, '3': ’сан’, '4': ’си’, '7': ’ћи’, '8': ’ба’, '9': ’ђу’, '10': ’ши’}
    Написати функцију коjа преводи арапске броjеве до 99 унете у облику ниске на мандарински jезик.
    Пример:
    broj = '17' -> ши ћи
    broj = '20  -> ер ши
    broj = '37- -> сан ши ћи
    """
    brojevi = {'0': 'линг', '1': 'jи','5': 'ву','6': 'љу','2': 'ер', '3': 'сан', '4': 'си', '7': 'ћи', '8': 'ба', '9': 'ђу', '10': 'ши'}
    br = int(broj)
    if br <= 10:
        return brojevi[broj]
    if br < 20:
        return brojevi['10'] + ' ' + brojevi[str(br%10)]
    if br % 10 == 0:
        return brojevi[str(br//10)] + ' ' + brojevi['10']
    return brojevi[str(br//10)] + ' ' + brojevi['10'] + ' ' + brojevi[str(br%10)]

    

Задатак 11

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

Решење
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

Задатак 12

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

Решење
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)                                        # type: ignore