Основи програмирања: вежбе - 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$ на следећи начин:
- $B[i] = A[i]$, ако jе $i + 1 < K$;
- $B[i] = (A[i] + A[i-1] + … + A[i - K + 1]) // K$, иначе.
Решење
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:
- поређати цифре почетног броjа наjпре у неопадаjућем, а затим у нерастућем редоследу;
- одузети први од другог, односно мањи од већег тако добиjеног броjа;
- на добиjену разлику (по потреби проширену водећим нулама) применити исти низ операциjа. Примера ради, полазећи од броjа 3524:
- након прве итерациjе добиjа се броj: 5432 - 2345 = 3087;
- након друге итерациjе добиjа се броj: 8730 - 0378 = 8352;
- и наjзад, након треће итерациjе добиjа се броj: 8532 - 2358 = 6174. Понављањем поступка у свим даљим итерациjама добиjа се исти резултат jер jе 7641 - 1467 = 6174. Написати функциjу коjа враћа у колико се итерациjа долази до Капрекарове константе 6174 полазећи од произвољног улазног природног броjа мањег од 9999 кога не сачињаваjу четири идентичне цифре.
Решење
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едноставна правила:
- за сваку од цифара, односно за сваки од бро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език.
Решење
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