Основи програмирања: вежбе - XI недеља
Задатак 1
Написати функцију која прави троугао од звездица. Функција прима целобројну бредност n, који представља дужину странице троугла.
Решење
def trougao_od_zvezdica():
n = int(input())
broj_razmaka = n-1
broj_zvezdica = 1
for i in range(n):
for j in range(broj_razmaka):
print(' ', sep='', end='')
broj_razmaka -= 1
for j in range(broj_zvezdica):
print('*', sep='', end='')
broj_zvezdica += 2
print()
Задатак 2
Написати функцију која исписује троугао од речи. Функција прима ниску s, која представља дату реч.
Решење
def trougao_od_reci():
def ispisi_n_puta(c, n):
for i in range(n):
print(c, sep='', end='')
s = input()
n = len(s)
ispisi_n_puta(' ', n-1)
print(s[0])
for i in range(1, n-1):
ispisi_n_puta(' ', n-1-i)
print(s[i], sep='', end='')
ispisi_n_puta(' ', 2*i-1)
print(s[i])
print(s[n-1:0:-1] + s[0:n])
Задатак 3
Написати функцију која црта ромб од звездица. Функција прима целобројну вредност n, која представља дужину странице ромба.
Решење
def romb_od_zvezdica(n):
for i in range(n):
for j in range(n-i):
print(" ", end="",sep="")
for j in range(n):
print("*", end="",sep="")
print()
Задатак 4
Написати функију која за дато n исписује чланове низа 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, . . . , n.
Решење
def serija123(n):
"""
Написати функију која за дато n исписује чланове низа 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, . . . , n.
"""
for i in range(1,n+1):
for j in range(i):
print(i, end=' ')
Задатак 5
За дато n исписати елементе низа 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, … који се формира тако што се полазећи од броја 1 – приказује један непаран природни број, затим следећа два парна – 2, 4; па следећа 3 непарна – 5, 7, 9; следећа 4 парна – 10, 12, 14, 16, … итд. Последња серија садржи n елемената.
Решење
def serije_neparni_parni(n):
"""
За дато n исписати елементе низа 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, … који се формира тако што се полазећи
од броја 1 – приказује један непаран природни број, затим следећа два парна – 2, 4; па следећа 3 непарна –
5, 7, 9; следећа 4 парна – 10, 12, 14, 16, … итд. Последња серија садржи n елемената.
"""
k=1
for i in range(n):
print(k, end=' ')
for j in range(i):
k+=2
print(k, end=' ')
print()
k+=1
Задатак 6
Вредна девоjчица Маjа жели да помогне своjоj мами да рашчисти фрижидер и оставу. Наиме, њен мали брат Марко постао jе алергичан на све намирнице коjе у свом називу садрже слово “у”. Помозите Маjи да направи списак свих намирница коjе jе потребно да избаце из куће.
Намирнице коjе се тренутно налазе у Маjиноj кући дате су као сложени низ, чиjи су чланови низови намирница истог типа (воће, поврће, месо, млечни производи и слично). Потребно jе написати функциjу коjа враћа сложени низ по узору на постоjећи, чиjи ће угнеждени чланови бити све намирнице у чиjем називу постоjи слово “у”.
Решење - угнеждене петље
def izbaciNamirnice(namirnice):
izbaciti = []
for vrstaNamirnice in namirnice:
izbacitiPoVrstama = []
for namirnica in vrstaNamirnice:
if "у" in namirnica:
izbacitiPoVrstama.append(namirnica)
izbaciti.append(izbacitiPoVrstama)
return izbaciti
#namirnice = [["јабуке", "банане", "крушке", "киви"], ["паприка", "купус", "краставчићи"], ["ћуретина", "пилетина", "свињетина"]]
#print(izbaciNamirnice(namirnice))
Решење - List Comprehension
def izbaciNamirnice2(namirnice):
izbaciti = [[namirnica for namirnica in vrsta if "у" in namirnica] for vrsta in namirnice]
return izbaciti
#namirnice = [["јабуке", "банане", "крушке", "киви"], ["паприка", "купус", "краставчићи"], ["ћуретина", "пилетина", "свињетина"]]
#print(izbaciNamirnice2(namirnice))
Задатак 7
Написати функцију која рaчуна збир свих чланова матрице.
Решење - угнеждене петље
# Функције за унос и штампање матрице
"""
def matrica_input():
br_vrsta, br_kolona = map(int, input().split())
matrica=[]
for i in range(br_vrsta):
vrsta=list(map(int,input().split()))
matrica.append(vrsta)
return matrica
def matrica_print(matrica):
br_vrsta=len(matrica)
br_kolona=len(matrica[0])
for i in range(br_vrsta):
for j in range(br_kolona):
print("{:3d}".format(matrica[i][j]), end=" ")
print("\n")
"""
def suma_svih_clanova_matrice(matrica):
suma = 0
for i in range(len(matrica)):
for j in range(len(matrica[0])):
suma += matrica[i][j]
return suma
#matrica=matrica_input()
#matrica_print(matrica)
#print(suma_svih_clanova_matrice(matrica))
Решење - List Comprehension
# Функције за унос и штампање матрице
"""
def matrica_input():
br_vrsta, br_kolona = map(int, input().split())
matrica=[]
for i in range(br_vrsta):
vrsta=list(map(int,input().split()))
matrica.append(vrsta)
return matrica
def matrica_print(matrica):
br_vrsta=len(matrica)
br_kolona=len(matrica[0])
for i in range(br_vrsta):
for j in range(br_kolona):
print("{:3d}".format(matrica[i][j]), end=" ")
print("\n")
"""
def suma_svih_clanova_matrice_2(matrica):
return sum([sum(i) for i in matrica])
#matrica=matrica_input()
#matrica_print(matrica)
#print(suma_svih_clanova_matrice_2(matrica))
Задатак 8
Написати функциjу коjа проналази и исписуjе минималан члан дате матрице.
Омогућити учитавање матрице. На стандардни улаз уносе се димензиjе матрице $N$ и $M$, где jе $N$ броj врста, а $M$ броj колона матрице. Након тога се уносе чланови матрице, врсту по врсту.
Димензиjе матрице су природни броjеви, док су њени чланови цели броjеви.
Решење - угнеждене петље
# Учитавање матрице
N, M = map(int, input().split())
matrica=[]
for i in range(N):
vrsta=list(map(int,input().split()))
matrica.append(vrsta)
def minimalanClan(matrica):
minimalan = matrica[0][0]
for i in range(len(matrica)):
for j in range(len(matrica[0])):
if matrica[i][j] < minimalan:
minimalan = matrica[i][j]
return minimalan
print(minimalanClan(matrica))
Решење - List Comprehension
# Учитавање матрице
N, M = map(int, input().split())
matrica=[]
for i in range(N):
vrsta=list(map(int,input().split()))
matrica.append(vrsta)
def minimalanClan2(matrica):
return min([min(i) for i in matrica])
print(minimalanClan2(matrica))
Задатак 9
Написати програм коjи исписуjе 1 изнад главне диjагонале, 3 испод главне диjагонале и 2 на главноj диjагонали квадратне матрице.
Главна диjагонала матрице jе скуп елемената коjи леже на замишљеноj диjагонали између горњег левог и доњег десног угла матрице.
На стандардни улаз уноси се jедан природан броj, коjи представља димензиjу квадратне матрице.
На стандардни излаз исписати матрицу формирану по задатим правилима.
Решење
def matrica_print(matrica):
br_vrsta=len(matrica)
br_kolona=len(matrica[0])
for i in range(br_vrsta):
for j in range(br_kolona):
print("{:3d}".format(matrica[i][j]), end=" ")
print("\n")
n=int(input())
matrica=[[0 for i in range(n)] for j in range(n)]
for i in range(len(matrica)):
for j in range(len(matrica[i])):
if i==j:
matrica[i][j]=2
elif i<j:
matrica[i][j]=1
else:
matrica[i][j]=3
print("------------------------------")
matrica_print(matrica)
Задатак 10
Написати функцију која ће рачунати траг дате матрице.
Траг матрице је дефинисан као збир елемената на главној дијагонали.
Дата матрица је подразумевано квадратна.
Решење - $O(n^2)$
def trag_matrice(matrica):
suma = 0
for i in range(len(matrica)):
for j in range(len(matrica[0])):
if i == j:
suma += matrica[i][j]
return suma
Решење - $O(n)$
def trag_matrice_alternativno(matrica):
suma = 0
for i in range(len(matrica)):
suma += matrica[i][i]
return suma
Задатак 11
Написати функцију која транспонује дату матрицу.
Решење
def matrica_input():
br_vrsta, br_kolona = map(int, input().split())
matrica=[]
for i in range(br_vrsta):
vrsta=list(map(int,input().split()))
matrica.append(vrsta)
return matrica
def matrica_print(matrica):
br_vrsta=len(matrica)
br_kolona=len(matrica[0])
for i in range(br_vrsta):
for j in range(br_kolona):
print("{:3d}".format(matrica[i][j]), end=" ")
print("\n")
# Специјалан случај - квадратна матрица
def transponovanje_matrice_kvadratne(matrica):
for i in range(len(matrica)):
for j in range(i+1,len(matrica[0])):
matrica[i][j],matrica[j][i] = matrica[j][i],matrica[i][j]
return matrica
def transponovanje_matrice(matrica):
matrica_trans=[[0 for i in range(len(matrica))] for j in range(len(matrica[0]))]
for i in range(len(matrica)):
for j in range(len(matrica[0])):
matrica_trans[j][i]=matrica[i][j]
return matrica_trans
if __name__ =="__main__":
matrica=matrica_input()
print("------------------------------")
matrica_print(matrica)
print("------------------------------")
matrica=transponovanje_matrice(matrica) if len(matrica)!=len(matrica[0]) else transponovanje_matrice_kvadratne(matrica)
matrica_print(matrica)
Задатак 12
Написати програм коjи сортира колоне дате матрице у растућем поретку.
Решење
## Увози се функција из претходног задатка
from zad3 import transponovanje_matrice
def matrica_input():
br_vrsta, br_kolona = map(int, input().split())
matrica=[]
for i in range(br_vrsta):
vrsta=list(map(int,input().split()))
matrica.append(vrsta)
return matrica
def matrica_print(matrica):
br_vrsta=len(matrica)
br_kolona=len(matrica[0])
for i in range(br_vrsta):
for j in range(br_kolona):
print("{:3d}".format(matrica[i][j]), end=" ")
print("\n")
matrica=matrica_input()
print("------------------------------")
matrica_print(matrica)
print("------------------------------")
matrica=transponovanje_matrice(matrica)
matrica=[sorted(i) for i in matrica]
matrica=transponovanje_matrice(matrica)
matrica_print(matrica)
Задатак 13
Написати функциjу коjа израчунава збир чланова матрице коjи се налазе изнад њене споредне диjагонале.
Дата матрица jе подразумевано квадратна.
Решење
def zbir_clanova_iznad_sporedne(matrica):
sum = 0
for i in range(len(matrica)-1):
for j in range(len(matrica)-(i+1)):
sum += matrica[i][j]
return sum
Задатак 14
Написати функцију која враћа низ чланова матрице поређаних у спиралном реду.
Решење
def spiralOrder(matrix):
output = []
leftCol, rightCol = 0, len(matrix[0])
topRow, bottomRow = 0, len(matrix)
while leftCol < rightCol and topRow < bottomRow:
for i in range(leftCol,rightCol):
output.append(matrix[topRow][i])
topRow += 1
for i in range(topRow,bottomRow):
output.append(matrix[i][rightCol-1])
rightCol-=1
if not(leftCol < rightCol and topRow < bottomRow):
break
for i in range(rightCol-1,leftCol-1,-1):
output.append(matrix[bottomRow-1][i])
bottomRow-=1
for i in range(bottomRow-1,topRow-1,-1):
output.append(matrix[i][leftCol])
leftCol+=1
return output
Задатак 15
Написати функцију која мења матрицу тако да, ако је члан матрице једнак 0, тада се сви чланове реда и колоне у коме је тај члан мењају у 0.
Решење - $O(1)$ меморијска комплексност
def setZeroes(matrix):
set_first_row_zero = False
rows, cols = len(matrix), len(matrix[0])
for r in range(rows):
for c in range(cols):
if matrix[r][c] ==0:
matrix[0][c]=0
if r==0:
set_first_row_zero = True
else:
matrix[r][0] = 0
for r in range(1,rows):
for c in range(1,cols):
if matrix[r][0] == 0 or matrix[0][c] ==0:
matrix[r][c] =0
if matrix[0][0] == 0:
for r in range(rows):
matrix[r][0]=0
if set_first_row_zero:
for c in range(cols):
matrix[0][c]=0
Задатак 16
Написати функцију која ротира матрицу за 90 степени у негативном математичком смеру (смеру казаљке на сату).
Решење
def rotate(matrix):
left, right = 0, len(matrix[0])-1
while left < right:
bottom, top =right , left
for i in range(right-left):
top_right = matrix[top+i][right]
matrix[top+i][right] = matrix[top][left+i]
bottom_right = matrix[bottom][right-i]
matrix[bottom][right-i] = top_right
bottom_left = matrix[bottom-i][left]
matrix[bottom-i][left] = bottom_right
matrix[top][left+i] = bottom_left
left+=1
right-=1