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

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

View on GitHub

Основи програмирања: вежбе - 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