In [1]:
def cria_matriz(tot_lin, tot_col, valor):
matriz = [] #lista vazia
for i in range(tot_lin):
linha = []
for j in range(tot_col):
linha.append(valor)
matriz.append(linha)
return matriz
In [3]:
x = cria_matriz(2, 3, 99)
x
Out[3]:
In [4]:
def cria_matriz(tot_lin, tot_col, valor):
matriz = [] #lista vazia
for i in range(tot_lin):
linha = []
for j in range(tot_col):
linha.append(valor)
matriz.append(linha)
return matriz
In [5]:
x = cria_matriz(2, 3, 99)
x
Out[5]:
Este código faz com que primeiramente toda a primeira linha seja preenchida, em seguida a segunda e assim sucessivamente. Se nós quiséssemos que a primeira coluna fosse preenchida e em seguida a segunda coluna e assim por diante, como ficaria o código?
Um exemplo: se o usuário digitasse o seguinte comando “x = cria_matriz(2,3)” e em seguida informasse os seis números para serem armazenados na matriz, na seguinte ordem: 1, 2, 3, 4, 5, 6; o x teria ao final da função a seguinte matriz: [[1, 3, 5], [2, 4, 6]].
In [6]:
def cria_matriz(num_linhas, num_colunas):
matriz = [] #lista vazia
for i in range(num_linhas):
linha = []
for j in range(num_colunas):
linha.append(0)
matriz.append(linha)
for i in range(num_colunas):
for j in range(num_linhas):
matriz[j][i] = int(input("Digite o elemento [" + str(j) + "][" + str(i) + "]: "))
return matriz
In [7]:
x = cria_matriz(2, 3)
In [8]:
x
Out[8]:
In [10]:
def tarefa(mat):
dim = len(mat)
for i in range(dim):
print(mat[i][dim-1-i], end=" ")
mat = [[1,2,3],[4,5,6],[7,8,9]]
tarefa(mat)
# Observação: o trecho do print (end = " ") irá mudar a finalização padrão do print
# que é pular para a próxima linha. Com esta mudança, o cursor permanecerá na mesma
# linha aguardando a impressão seguinte.
In [1]:
def dimensoes(A):
'''Função que recebe uma matriz como parâmetro e imprime as dimensões da matriz recebida, no formato iXj.
Obs: i = colunas, j = linhas
Exemplo:
>>> minha_matriz = [[1],
[2],
[3]
]
>>> dimensoes(minha_matriz)
>>> 3X1
'''
lin = len(A)
col = len(A[0])
return print("%dX%d" % (lin, col))
In [2]:
matriz1 = [[1], [2], [3]]
dimensoes(matriz1)
In [3]:
matriz2 = [[1, 2, 3], [4, 5, 6]]
dimensoes(matriz2)
Escreva a função soma_matrizes(m1, m2) que recebe 2 matrizes e devolve uma matriz que represente sua soma caso as matrizes tenham dimensões iguais. Caso contrário, a função deve devolver False.
Exemplos:
m1 = [[1, 2, 3], [4, 5, 6]]
m2 = [[2, 3, 4], [5, 6, 7]]
soma_matrizes(m1, m2) => [[3, 5, 7], [9, 11, 13]]
m1 = [[1], [2], [3]]
m2 = [[2, 3, 4], [5, 6, 7]]
soma_matrizes(m1, m2) => False
In [7]:
def soma_matrizes(m1, m2):
def dimensoes(A):
lin = len(A)
col = len(A[0])
return ((lin, col))
if dimensoes(m1) != dimensoes(m2):
return False
else:
matriz = []
for i in range(len(m1)):
linha = []
for j in range(len(m1[0])):
linha.append(m1[i][j] + m2[i][j])
matriz.append(linha)
return matriz
In [8]:
m1 = [[1, 2, 3], [4, 5, 6]]
m2 = [[2, 3, 4], [5, 6, 7]]
soma_matrizes(m1, m2)
Out[8]:
In [9]:
m1 = [[1], [2], [3]]
m2 = [[2, 3, 4], [5, 6, 7]]
soma_matrizes(m1, m2)
Out[9]:
Exercício 1: Imprimindo matrizes
Como proposto na primeira vídeo-aula da semana, escreva uma função imprime_matriz(matriz), que recebe uma matriz como parâmetro e imprime a matriz, linha por linha. Note que NÃO se deve imprimir espaços após o último elemento de cada linha!
Exemplos:
minha_matriz = [[1], [2], [3]]
imprime_matriz(minha_matriz)
1
2
3
minha_matriz = [[1, 2, 3], [4, 5, 6]]
imprime_matriz(minha_matriz)
1 2 3
4 5 6
In [26]:
def imprime_matriz(A):
for i in range(len(A)):
for j in range(len(A[i])):
print(A[i][j])
In [27]:
minha_matriz = [[1], [2], [3]]
imprime_matriz(minha_matriz)
In [28]:
minha_matriz = [[1, 2, 3], [4, 5, 6]]
imprime_matriz(minha_matriz)
Duas matrizes são multiplicáveis se o número de colunas da primeira é igual ao número de linhas da segunda. Escreva a função sao_multiplicaveis(m1, m2) que recebe duas matrizes como parâmetro e devolve True se as matrizes forem multiplicavéis (na ordem dada) e False caso contrário.
Exemplos:
m1 = [[1, 2, 3], [4, 5, 6]]
m2 = [[2, 3, 4], [5, 6, 7]]
sao_multiplicaveis(m1, m2) => False
m1 = [[1], [2], [3]]
m2 = [[1, 2, 3]]
sao_multiplicaveis(m1, m2) => True
In [30]:
def sao_multiplicaveis(m1, m2):
'''Recebe duas matrizes como parâmetros e devolve True se as matrizes forem multiplicáveis (número de colunas
da primeira é igual ao número de linhs da segunda). False se não forem
'''
if len(m1) == len(m2[0]):
return True
else:
return False
In [31]:
m1 = [[1, 2, 3], [4, 5, 6]]
m2 = [[2, 3, 4], [5, 6, 7]]
sao_multiplicaveis(m1, m2)
Out[31]:
In [32]:
m1 = [[1], [2], [3]]
m2 = [[1, 2, 3]]
sao_multiplicaveis(m1, m2)
Out[32]:
In [1]:
"áurea gosta de coentro".capitalize()
Out[1]:
In [2]:
"AQUI".capitalize()
Out[2]:
In [3]:
# função para remover espaços em branco
" email@company.com ".strip()
Out[3]:
In [4]:
"o abecedário da Xuxa é didático".count("a")
Out[4]:
In [5]:
"o abecedário da Xuxa é didático".count("á")
Out[5]:
In [6]:
"o abecedário da Xuxa é didático".count("X")
Out[6]:
In [7]:
"o abecedário da Xuxa é didático".count("x")
Out[7]:
In [8]:
"o abecedário da Xuxa é didático".count("z")
Out[8]:
In [9]:
"A vida como ela seje".replace("seje", "é")
Out[9]:
In [11]:
"áurea gosta de coentro".capitalize().center(80) #80 caracteres de largura, no centro apareça este texto
Out[11]:
In [12]:
texto = "Ao que se percebe, só há o agora"
texto
Out[12]:
In [13]:
texto.find("q")
Out[13]:
In [14]:
texto.find('se')
Out[14]:
In [16]:
texto[7] + texto[8]
Out[16]:
In [17]:
texto.find('w')
Out[17]:
In [18]:
fruta = 'amora'
In [20]:
fruta[:4] # desde o começo até a posição TRÊS!
Out[20]:
In [23]:
fruta[1:] # desde a posição 1 (começa no zero) até o final
Out[23]:
In [24]:
fruta[2:4] # desde a posição 2 até a posição 3
Out[24]:
In [30]:
def mais_curto(lista_de_nomes):
menor = lista_de_nomes[0] # considerando que o menor nome está no primeiro lugar
for i in lista_de_nomes:
if len(i) < len(menor):
menor = i
return menor.capitalize()
In [31]:
lista = ['carlos', 'césar', 'ana', 'vicente', 'maicon', 'washington']
In [32]:
mais_curto(lista)
Out[32]:
In [33]:
ord('a')
Out[33]:
In [34]:
ord('A')
Out[34]:
In [35]:
ord('b')
Out[35]:
In [39]:
ord('m')
Out[39]:
In [40]:
ord('M')
Out[40]:
In [26]:
ord('AA')
In [36]:
'maçã' > 'banana'
Out[36]:
In [37]:
'Maçã' > 'banana'
Out[37]:
In [41]:
'Maçã'.lower() > 'banana'.lower()
Out[41]:
In [56]:
txt = 'José'
txt = txt.lower()
txt
Out[56]:
In [92]:
lista = ['ana', 'maria', 'José', 'Valdemar']
len(lista)
Out[92]:
In [93]:
lista[3].lower()
Out[93]:
In [94]:
lista[2]
Out[94]:
In [95]:
lista[2] = lista[2].lower()
In [96]:
lista
Out[96]:
In [98]:
for i in lista:
print(i)
In [105]:
lista[0][0]
Out[105]:
In [ ]:
In [106]:
def menor_string(array_string):
for i in range(len(array_string)):
array_string[i] = array_string[i].lower()
menor = array_string[0] # considera o primeiro como o menor
for i in array_string:
if ord(i[0][0]) < ord(menor[0]):
menor = i
return menor
In [111]:
lista = ['maria', 'José', 'Valdemar']
In [112]:
menor_string(lista)
Out[112]:
In [114]:
# Código para inverter string e deixa maiúsculo
def fazAlgo(string):
pos = len(string)-1
string = string.upper()
while pos >= 0:
print(string[pos],end = "")
pos = pos - 1
fazAlgo("paralelepipedo")
In [115]:
# Código que deixa maiúsculo as letras de ordem ímpar:
def fazAlgo(string):
pos = 0
string1 = ""
string = string.lower()
stringMa = string.upper()
while pos < len(string):
if pos % 2 == 0:
string1 = string1 + stringMa[pos]
else:
string1 = string1 + string[pos]
pos = pos + 1
return string1
print(fazAlgo("paralelepipedo"))
In [118]:
# Código que tira os espaços em branco
def fazAlgo(string):
pos = 0
string1 = ""
while pos < len(string):
if string[pos] != " ":
string1 = string1 + string[pos]
pos = pos + 1
return string1
print(fazAlgo("ISTO É UM TESTE"))
In [135]:
# e para retornar "Istoéumteste", ou seja, só deixar a primeira letra maiúscula...
def fazAlgo(string):
pos = 0
string1 = ""
while pos < len(string):
if string[pos] != " ":
string1 = string1 + string[pos]
pos = pos + 1
string1 = string1.capitalize()
return string1
In [136]:
print(fazAlgo("ISTO É UM TESTE"))
In [1]:
x, y = 10, 20
In [2]:
x, y
Out[2]:
In [3]:
x
Out[3]:
In [4]:
y
Out[4]:
In [5]:
def peso_altura():
return 77, 1.83
In [6]:
peso_altura()
Out[6]:
In [8]:
peso, altura = peso_altura()
In [9]:
peso
Out[9]:
In [10]:
altura
Out[10]:
In [ ]:
# Atribuição múltipla em C (vacas magras...)
'''
int a, b, temp
a = 10
b = 20
temp = a
a = b
b = temp
'''
In [14]:
a, b = 10, 20
a, b = b, a
a, b
Out[14]:
In [15]:
# Atribuição aumentada
x = 10
x = x + 10
x
Out[15]:
In [17]:
x = 10
x += 10
x
Out[17]:
In [19]:
x = 3
x *= 2
x
Out[19]:
In [20]:
x = 2
x **= 10
x
Out[20]:
In [22]:
x = 100
x /= 3
x
Out[22]:
In [23]:
def pagamento_semanal(valor_por_hora, num_horas = 40):
return valor_por_hora * num_horas
In [24]:
pagamento_semanal(10)
Out[24]:
In [26]:
pagamento_semanal(10, 20) # aceita, mesmo assim, o segundo parâmetro.
Out[26]:
In [27]:
# Asserção de Invariantes
def pagamento_semanal(valor_por_hora, num_horas = 40):
assert valor_por_hora >= 0 and num_horas > 0
return valor_por_hora * num_horas
In [28]:
pagamento_semanal(30, 10)
Out[28]:
In [29]:
pagamento_semanal(10, -10)
In [30]:
x, y = 10, 12
x, y = y, x
print("x = ",x,"e y = ",y)
In [31]:
x = 10
x += 10
x /= 2
x //= 3
x %= 2
x *= 9
print(x)
In [32]:
def calculo(x, y = 10, z = 5):
return x + y * z;
calculo(1, 2, 3)
Out[32]:
In [34]:
calculo(1, 2) # 2 entra em y.
Out[34]:
In [36]:
def calculo(x, y = 10, z = 5):
return x + y * z;
print(calculo(1, 2, 3))
In [37]:
calculo()
In [38]:
print(calculo( ,12, 10))
In [39]:
def horario_em_segundos(h, m, s):
assert h >= 0 and m >= 0 and s >= 0
return h * 3600 + m * 60 + s
print(horario_em_segundos (3,0,50))
In [40]:
print(horario_em_segundos(1,2,3))
In [41]:
print(horario_em_segundos (-1,20,30))
In [1]:
# Módulos em Python
def fib(n): # escreve a série de Fibonacci até n
a, b = 0, 1
while b < n:
print(b, end = ' ')
a, b = b, a + b
print()
def fib2(n):
result = []
a, b = 0, 1
while b < n:
result.append(b)
a, b = b, a + b
return result
In [ ]:
'''
E no shell do Python (chamado na pasta que contém o arquivo fibo.py)
>>> import fibo
>>> fibo.fib(100)
1 1 2 3 5 8 13 21 34 55 89
>>> fibo.fib2(100)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
>>> fibo.fib2(1000)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
>>> meuFib = fibo.fib
>>> meuFib(20)
1 1 2 3 5 8 13
'''
Incluindo
```print(__name__)```na última linha de fibo.py, ao fazer a importação import fibo no shell do Python, imprime 'fibo', que é o nome do programa.
Ao incluir
if __name__ == "__main__": import sys fib(int(sys.argv[1]))
podemos ver se está sendo executado como script (com o if do jeito que está) ou como módulo dentro de outro código (se o nome não for main, está sendo importado pra usar alguma função lá dentro).
In [1]:
def fazAlgo(string): # inverte a string e deixa as vogais maiúsculas
pos = len(string)-1 # define a variável posição do array
stringMi = string.lower() # aqui estão todas minúsculas
string = string.upper() # aqui estão todas maiúsculas
stringRe = "" # string de retorno
while pos >= 0:
if string[pos] == 'A' or string[pos] == 'E' or string[pos] == 'I' or string[pos] == 'O' or string[pos] == 'U':
stringRe = stringRe + string[pos]
else:
stringRe = stringRe + stringMi[pos]
pos = pos - 1
return stringRe
if __name__ == "__main__":
print(fazAlgo("teste"))
print(fazAlgo("o ovo do avestruz"))
print(fazAlgo("A CASA MUITO ENGRAÇADA"))
print(fazAlgo("A TELEvisão queBROU"))
print(fazAlgo("A Vaca Amarela"))
Escreva a função maiusculas(frase) que recebe uma frase (uma string) como parâmetro e devolve uma string com as letras maiúsculas que existem nesta frase, na ordem em que elas aparecem.
Para resolver este exercício, pode ser útil verificar uma tabela ASCII, que contém os valores de cada caractere. Ver http://equipe.nce.ufrj.br/adriano/c/apostila/tabascii.htm
Note que para simplificar a solução do exercício, as frases passadas para a sua função não possuirão caracteres que não estejam presentes na tabela ASCII apresentada, como ç, á, É, ã, etc.
Dica: Os valores apresentados na tabela são os mesmos devolvidos pela função ord apresentada nas aulas.
Exemplos:
In [ ]:
maiusculas('Programamos em python 2?')
# deve devolver 'P'
maiusculas('Programamos em Python 3.')
# deve devolver 'PP'
maiusculas('PrOgRaMaMoS em python!')
# deve devolver 'PORMMS'
In [34]:
def maiusculas(frase):
listRe = [] # lista de retorno vazia
stringRe = '' # string de retorno vazia
for ch in frase:
if ord(ch) >=65 and ord(ch) <= 91:
listRe.append(ch)
# retornando a lista para string
stringRe = ''.join(listRe)
return stringRe
In [40]:
maiusculas('Programamos em python 2?')
Out[40]:
In [41]:
maiusculas('Programamos em Python 3.')
Out[41]:
In [42]:
maiusculas('PrOgRaMaMoS em python!')
Out[42]:
In [24]:
x = ord('A')
y = ord('a')
x, y
Out[24]:
In [21]:
ord('B')
Out[21]:
In [14]:
ord('Z')
Out[14]:
Como pedido no primeiro vídeo desta semana, escreva uma função menor_nome(nomes) que recebe uma lista de strings com nome de pessoas como parâmetro e devolve o nome mais curto presente na lista.
A função deve ignorar espaços antes e depois do nome e deve devolver o menor nome presente na lista. Este nome deve ser devolvido com a primeira letra maiúscula e seus demais caracteres minúsculos, independente de como tenha sido apresentado na lista passada para a função.
Quando houver mais de um nome com o menor comprimento dentre os nomes na lista, a função deve devolver o primeiro nome com o menor comprimento presente na lista.
Exemplos:
In [ ]:
menor_nome(['maria', 'josé', 'PAULO', 'Catarina'])
# deve devolver 'José'
menor_nome(['maria', ' josé ', ' PAULO', 'Catarina '])
# deve devolver 'José'
menor_nome(['Bárbara', 'JOSÉ ', 'Bill'])
# deve devolver José
In [81]:
def menor_nome(nomes):
tamanho = len(nomes) # pega a quantidade de nomes na lista
menor = '' # variável para escolher o menor nome
lista_limpa = [] # lista de nomes sem os espaços em branco
# ignora espaços em branco
for str in nomes:
lista_limpa.append(str.strip())
# verifica o menor nome
menor = lista_limpa[0] # considera o primeiro como menor
for str in lista_limpa:
if len(str) < len(menor): # não deixei <= senão pegará um segundo menor de mesmo tamanho
menor = str
return menor.capitalize() # deixa a primeira letra maiúscula
In [83]:
menor_nome(['maria', 'josé', 'PAULO', 'Catarina'])
# deve devolver 'José'
In [84]:
menor_nome(['maria', ' josé ', ' PAULO', 'Catarina '])
# deve devolver 'José'
In [85]:
menor_nome(['Bárbara', 'JOSÉ ', 'Bill'])
# deve devolver José
In [88]:
menor_nome(['Bárbara', 'JOSÉ ', 'Bill', ' aDa '])
Escreva a função conta_letras(frase, contar="vogais"), que recebe como primeiro parâmetro uma string contendo uma frase e como segundo parâmetro uma outra string. Este segundo parâmetro deve ser opcional.
Quando o segundo parâmetro for definido como "vogais", a função deve devolver o numero de vogais presentes na frase. Quando ele for definido como "consoantes", a função deve devolver o número de consoantes presentes na frase. Se este parâmetro não for passado para a função, deve-se assumir o valor "vogais" para o parâmetro.
Exemplos:
conta_letras('programamos em python')
6
conta_letras('programamos em python', 'vogais')
6
conta_letras('programamos em python', 'consoantes')
13
In [125]:
def conta_letras(frase, contar = 'vogais'):
pos = len(frase) - 1 # atribui na variável pos (posição) a posição do array
count = 0 # define o contador de vogais
while pos >= 0: # conta as vogais
if frase[pos] == 'a' or frase[pos] == 'e' or frase[pos] == 'i' or frase[pos] == 'o' or frase[pos] == 'u':
count += 1
pos = pos - 1
if contar == 'consoantes':
frase = frase.replace(' ', '') # retira espaços em branco
return len(frase) - count # subtrai do total as vogais
else:
return count
In [126]:
conta_letras('programamos em python')
Out[126]:
In [127]:
conta_letras('programamos em python', 'vogais')
Out[127]:
In [128]:
conta_letras('programamos em python', 'consoantes')
Out[128]:
In [129]:
conta_letras('bcdfghjklmnpqrstvxywz', 'consoantes')
Out[129]:
In [130]:
len('programamos em python')
Out[130]:
In [131]:
frase = 'programamos em python'
frase.replace(' ', '')
frase
Out[131]:
Como pedido no segundo vídeo da semana, escreva a função primeiro_lex(lista) que recebe uma lista de strings como parâmetro e devolve o primeiro string na ordem lexicográfica. Neste exercício, considere letras maiúsculas e minúsculas.
Dica: revise a segunda vídeo-aula desta semana.
Exemplos:
primeiro_lex(['oĺá', 'A', 'a', 'casa'])
'A'
primeiro_lex(['AAAAAA', 'b'])
'AAAAAA'
In [29]:
def primeiro_lex(lista):
resposta = lista[0] # define o primeiro item da lista como a resposta...mas verifica depois.
for str in lista:
if ord(str[0]) < ord(resposta[0]):
resposta = str
return resposta
In [ ]:
assert primeiro_lex(['oĺá', 'A', 'a', 'casa']), 'A'
In [ ]:
assert primeiro_lex(['AAAAAA', 'b']), 'AAAAAA'
In [35]:
primeiro_lex(['casa', 'a', 'Z', 'A'])
Out[35]:
In [133]:
primeiro_lex(['AAAAAA', 'b'])
Out[133]:
In [142]:
def cria_matriz(tot_lin, tot_col, valor):
matriz = [] #lista vazia
for i in range(tot_lin):
linha = []
for j in range(tot_col):
linha.append(valor)
matriz.append(linha)
return matriz
In [144]:
# import matriz # descomentar apenas no arquivo .py
def soma_matrizes(A, B):
num_lin = len(A)
num_col = len(A[0])
C = cria_matriz(num_lin, num_col, 0) # matriz com zeros
for lin in range(num_lin): # percorre as linhas da matriz
for col in range(num_col): # percorre as colunas da matriz
C[lin][col] = A[lin][col] + B[lin][col]
return C
if __name__ == '__main__':
A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
B = [[10, 20, 30], [40, 50, 60], [70, 80, 90]]
print(soma_matrizes(A, B))
In [ ]:
# No arquivo matriz.py
def cria_matriz(tot_lin, tot_col, valor):
matriz = [] #lista vazia
for i in range(tot_lin):
linha = []
for j in range(tot_col):
linha.append(valor)
matriz.append(linha)
return matriz
# E no arquivo soma_matrizes.py
import matriz
def soma_matrizes(A, B):
num_lin = len(A)
num_col = len(A[0])
C = matriz.cria_matriz(num_lin, num_col, 0) # matriz com zeros
for lin in range(num_lin): # percorre as linhas da matriz
for col in range(num_col): # percorre as colunas da matriz
C[lin][col] = A[lin][col] + B[lin][col]
return C
if __name__ == '__main__':
A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
B = [[10, 20, 30], [40, 50, 60], [70, 80, 90]]
print(soma_matrizes(A, B))
In [ ]:
'''
Multiplicação de matrizes:
1 2 3 1 2 22 28
4 5 6 * 3 4 = 49 64
5 6
1*1 + 2*3 + 3*5 = 22
1*2 + 2*4 + 3*6 = 28
4*1 + 5*3 + 6*5 = 49
4*2 + 5*4 + 6*6 = 64
c11 = a11*b11 + a12*b21 + c13*c31
c12 = a11*b21 + a12*b22 + c13*c23
c21 = a21*b11 + a22*b21 + c23*c31
c22 = a21*b21 + a22*b22 + c23*c23
'''
In [151]:
def multiplica_matrizes (A, B):
num_linA, num_colA = len(A), len(A[0])
num_linB, num_colB = len(B), len(B[0])
assert num_colA == num_linB
C = []
for lin in range(num_linA): # percorre as linhas da matriz A
# começando uma nova linha
C.append([])
for col in range(num_colB): # percorre as colunas da matriz B
# Adicionando uma nova coluna na linha
C[lin].append(0)
for k in range(num_colA):
C[lin][col] += A[lin][k] * B[k][col]
return C
if __name__ == '__main__':
A = [[1, 2, 3], [4, 5, 6]]
B = [[1, 2], [3, 4], [5, 6]]
print(multiplica_matrizes(A, B))
In [153]:
class Carro:
pass
meu_carro = Carro()
meu_carro
Out[153]:
In [155]:
carro_do_trabalho = Carro()
carro_do_trabalho
Out[155]:
In [156]:
meu_carro.ano = 1968
meu_carro.modelo = 'Fusca'
meu_carro.cor = 'azul'
In [157]:
meu_carro.ano
Out[157]:
In [158]:
meu_carro.cor
Out[158]:
In [159]:
carro_do_trabalho.ano = 1981
carro_do_trabalho.modelo = 'Brasília'
carro_do_trabalho.cor = 'amarela'
In [160]:
carro_do_trabalho.ano
Out[160]:
In [162]:
novo_fusca = meu_carro # duas variáveis apontando para o mesmo objeto
In [164]:
novo_fusca #repare que é o mesmo end. de memória
Out[164]:
In [165]:
novo_fusca.ano += 10
In [166]:
novo_fusca.ano
Out[166]:
In [167]:
novo_fusca
Out[167]:
In [168]:
class Pato:
pass
pato = Pato()
patinho = Pato()
if pato == patinho:
print("Estamos no mesmo endereço!")
else:
print("Estamos em endereços diferentes!")
In [172]:
class Carro:
def __init__(self, modelo, ano, cor): # init é o Construtor da classe
self.modelo = modelo
self.ano = ano
self.cor = cor
In [173]:
carro_do_meu_avo = Carro('Ferrari', 1980, 'vermelha')
carro_do_meu_avo
Out[173]:
In [174]:
carro_do_meu_avo.cor
Out[174]:
In [6]:
def main():
carro1 = Carro('Brasília', 1968, 'amarela', 80)
carro2 = Carro('Fuscão', 1981, 'preto', 95)
carro1.acelere(40)
carro2.acelere(50)
carro1.acelere(80)
carro1.pare()
carro2.acelere(100)
class Carro:
def __init__(self, modelo, ano, cor, vel_max):
self.modelo = modelo
self.ano = ano
self.cor = cor
self.vel = 0
self.maxV = vel_max # velocidade máxima
def imprima(self):
if self.vel == 0: # parado dá para ver o ano
print('%s %s %d' % (self.modelo, self.cor, self.ano))
elif self.vel < self.maxV:
print('%s %s indo a %d km/h' % (self.modelo, self.cor, self.vel))
else:
print('%s %s indo muito rapido!' % (self.modelo, self.cor))
def acelere(self, velocidade):
self.vel = velocidade
if self.vel > self.maxV:
self.vel = self.maxV
self.imprima()
def pare(self):
self.vel = 0
self.imprima()
main()
In [7]:
class Cafeteira:
def __init__(self, marca, tipo, tamanho, cor):
self.marca = marca
self.tipo = tipo
self.tamanho = tamanho
self.cor = cor
In [15]:
class Cachorro:
def __init__(self, raça, idade, nome, cor):
self.raça = raça
self.idade = idade
self.nome = nome
self.cor = cor
rex = Cachorro('vira-lata', 2, 'Bobby', 'marrom')
In [16]:
'vira-lata' == rex.raça
Out[16]:
In [17]:
rex.idade > 2
Out[17]:
In [18]:
rex.idade == '2'
Out[18]:
In [19]:
rex.nome == 'rex'
Out[19]:
In [20]:
Bobby.cor == 'marrom'
In [21]:
rex.cor == 'marrom'
Out[21]:
In [22]:
class Lista:
def append(self, elemento):
return "Oops! Este objeto não é uma lista"
lista = []
a = Lista()
b = a.append(7)
lista.append(b)
In [23]:
a
Out[23]:
In [24]:
b
Out[24]:
In [25]:
lista
Out[25]:
In [34]:
import math
class Bhaskara:
def delta(self, a, b, c):
return b ** 2 - 4 * a * c
def main(self):
a_digitado = float(input("Digite o valor de a:"))
b_digitado = float(input("Digite o valor de b:"))
c_digitado = float(input("Digite o valor de c:"))
print(self.calcula_raizes(a_digitado, b_digitado, c_digitado))
def calcula_raizes(self, a, b, c):
d = self.delta(self, a, b, c)
if d == 0:
raiz1 = (-b + math.sqrt(d)) / (2 * a)
return 1, raiz1 # indica que tem uma raiz e o valor dela
else:
if d < 0:
return 0
else:
raiz1 = (-b + math.sqrt(d)) / (2 * a)
raiz2 = (-b - math.sqrt(d)) / (2 * a)
return 2, raiz1, raiz2
In [35]:
main()
In [36]:
main()
In [38]:
import Bhaskara
class TestBhaskara:
def testa_uma_raiz(self):
b = Bhaskara.Bhaskara()
assert b.calcula_raizes(1, 0, 0) == (1, 0)
def testa_duas_raizes(self):
b = Bhaskara.Bhaskara()
assert b.calcula_raizes(1, -5, 6) == (2, 3, 2)
def testa_zero_raizes(self):
b = Bhaskara.Bhaskara()
assert b.calcula_raizes(10, 10, 10) == 0
def testa_raiz_negativa(self):
b = Bhaskara.Bhaskara()
assert b.calcula_raizes(10, 20, 10) == (1, -1)
In [42]:
# Nos estudos ficou pytest_bhaskara.py
import Bhaskara
import pytest
class TestBhaskara:
@pytest.fixture
def b(self):
return Bhaskara.Bhaskara()
def testa_uma_raiz(self, b):
assert b.calcula_raizes(1, 0, 0) == (1, 0)
def testa_duas_raizes(self, b):
assert b.calcula_raizes(1, -5, 6) == (2, 3, 2)
def testa_zero_raizes(self, b):
assert b.calcula_raizes(10, 10, 10) == 0
def testa_raiz_negativa(self, b):
assert b.calcula_raizes(10, 20, 10) == (1, -1)
In [44]:
def fatorial(n):
if n < 0:
return 0
i = fat = 1
while i <= n:
fat = fat * i
i += 1
return fat
import pytest
@pytest.mark.parametrize("entrada, esperado", [
(0, 1),
(1, 1),
(-10, 0),
(4, 24),
(5, 120)
])
def testa_fatorial(entrada, esperado):
assert fatorial(entrada) == esperado
In [ ]:
In [ ]:
In [ ]:
In [ ]:
Exercício 1: Uma classe para triângulos
Defina a classe Triangulo cujo construtor recebe 3 valores inteiros correspondentes aos lados a, b e c de um triângulo.
A classe triângulo também deve possuir um método perimetro, que não recebe parâmetros e devolve um valor inteiro correspondente ao perímetro do triângulo.
t = Triangulo(1, 1, 1)
Um objeto desta classe deve responder às seguintes chamadas:
t.a
t. b
t.c
t.perimetro()
In [13]:
class Triangulo:
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
def perimetro(self):
return self.a + self.b + self.c
In [14]:
t = Triangulo(1, 1, 1)
In [15]:
t.a
Out[15]:
In [16]:
t.b
Out[16]:
In [17]:
t.c
Out[17]:
In [18]:
t.perimetro()
Out[18]:
Exercício 2: Tipos de triângulos
Na classe triângulo, definida na Questão 1, escreva o metodo tipo_lado() que devolve uma string dizendo se o triângulo é:
isóceles (dois lados iguais)
equilátero (todos os lados iguais)
escaleno (todos os lados diferentes)
Note que se o triângulo for equilátero, a função não deve devolver isóceles.
Exemplos:
t = Triangulo(4, 4, 4) t.tipo_lado()
u = Triangulo(3, 4, 5) .tipo_lado()
In [24]:
class Triangulo:
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
def tipo_lado(self):
if self.a == self.b and self.a == self.c:
return 'equilátero'
elif self.a != self.b and self.a != self.c and self.b != self.c:
return 'escaleno'
else:
return 'isósceles'
In [25]:
t = Triangulo(4, 4, 4)
t.tipo_lado()
Out[25]:
In [26]:
u = Triangulo(3, 4, 5)
u.tipo_lado()
Out[26]:
In [27]:
v = Triangulo(1, 3, 3)
v.tipo_lado()
Out[27]:
In [28]:
t = Triangulo(5, 8, 5)
t.tipo_lado()
Out[28]:
In [29]:
t = Triangulo(5, 5, 6)
t.tipo_lado()
Out[29]:
In [30]:
'''
Exercício 1: Triângulos retângulos
Escreva, na classe Triangulo, o método retangulo() que devolve
True se o triângulo for retângulo, e False caso contrário.
Exemplos:
t = Triangulo(1, 3, 5)
t.retangulo()
# deve devolver False
u = Triangulo(3, 4, 5)
u.retangulo()
# deve devolver True
'''
Out[30]:
In [36]:
class Triangulo:
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
def retangulo(self):
if self.a > self.b and self.a > self.c:
if self.a ** 2 == self.b ** 2 + self.c ** 2:
return True
else:
return False
elif self.b > self.a and self.b > self.c:
if self.b ** 2 == self.c ** 2 + self.a ** 2:
return True
else:
return False
else:
if self.c ** 2 == self.a ** 2 + self.b ** 2:
return True
else:
return False
In [37]:
t = Triangulo(1, 3, 5)
t.retangulo()
Out[37]:
In [38]:
t = Triangulo(3, 1, 5)
t.retangulo()
Out[38]:
In [39]:
t = Triangulo(5, 1, 3)
t.retangulo()
Out[39]:
In [40]:
u = Triangulo(3, 4, 5)
u.retangulo()
Out[40]:
In [41]:
u = Triangulo(4, 5, 3)
u.retangulo()
Out[41]:
In [42]:
u = Triangulo(5, 3, 4)
u.retangulo()
Out[42]:
Ainda na classe Triangulo, escreva um método semelhantes(triangulo) que recebe um objeto do tipo Triangulo como parâmetro e verifica se o triângulo atual é semelhante ao triângulo passado como parâmetro.
Caso positivo, o método deve devolver True. Caso negativo, deve devolver False.
Verifique a semelhança dos triângulos através do comprimento dos lados.
Dica: você pode colocar os lados de cada um dos triângulos em uma lista diferente e ordená-las.
Exemplo:
t1 = Triangulo(2, 2, 2)
t2 = Triangulo(4, 4, 4)
t1.semelhantes(t2)
'''
In [23]:
class Triangulo:
'''
O resultado dos testes com seu programa foi:
***** [0.2 pontos]: Testando método semelhantes(Triangulo(3, 4, 5)) para Triangulo(3, 4, 5) - Falhou *****
TypeError: 'Triangulo' object is not iterable
***** [0.2 pontos]: Testando método semelhantes(Triangulo(3, 4, 5)) para Triangulo(6, 8, 10) - Falhou *****
TypeError: 'Triangulo' object is not iterable
***** [0.2 pontos]: Testando método semelhantes(Triangulo(6, 8, 10)) para Triangulo(3, 4, 5) - Falhou *****
TypeError: 'Triangulo' object is not iterable
***** [0.4 pontos]: Testando método semelhantes(Triangulo(3, 3, 3)) para Triangulo(3, 4, 5) - Falhou *****
TypeError: 'Triangulo' object is not iterable
'''
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
# https://stackoverflow.com/questions/961048/get-class-that-defined-method
def semelhantes(self, Triangulo):
list1 = []
for arg in self:
list1.append(arg)
list2 = []
for arg in self1:
list2.append(arg)
for i in list2:
print(i)
In [24]:
t1 = Triangulo(2, 2, 2)
t2 = Triangulo(4, 4, 4)
t1.semelhantes(t2)
In [1]:
def busca_sequencial(seq, x):
'''(list, bool) -> bool'''
for i in range(len(seq)):
if seq[i] == x:
return True
return False
# código com cara de C =\
In [4]:
list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
busca_sequencial(list, 3)
Out[4]:
In [6]:
list = ['casa', 'texto', 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
busca_sequencial(list, 'texto')
Out[6]:
In [14]:
class Musica:
def __init__(self, titulo, interprete, compositor, ano):
self.titulo = titulo
self.interprete = interprete
self.compositor = compositor
self.ano = ano
class Buscador:
def busca_por_titulo(self, playlist, titulo):
for i in range(len(playlist)):
if playlist[i].titulo == titulo:
return i
return -1
def vamos_buscar(self):
playlist = [Musica("Ponta de Areia", "Milton Nascimento", "Milton Nascimento", 1975),
Musica("Podres Poderes", "Caetano Veloso", "Caetano Veloso", 1984),
Musica("Baby", "Gal Costa", "Caetano Veloso", 1969)]
onde_achou = self.busca_por_titulo(playlist, "Baby")
if onde_achou == -1:
print("A música buscada não está na playlist")
else:
preferida = playlist[onde_achou]
print(preferida.titulo, preferida.interprete, preferida.compositor, preferida.ano, sep = ', ')
In [15]:
b = Buscador()
In [16]:
b.vamos_buscar()
Análise matemática do desempenho de um algoritmo
Estudo analítico de:
Análise da Busca Sequencial
Exemplo:
Lista telefônica de São Paulo, supondo 2 milhões de telefones fixos.
Supondo que cada iteração do for comparação de string dure 1 milissegundo.
Pior caso: 2000s = 33,3 minutos
Caso médio (1 milhão): 1000s = 16,6 minutos
A cada passo, busca pelo menor elemento do pedaço ainda não ordenado da lista e o coloca no início da lista
No 1º passo, busca o menor elemento de todos e coloca na posição inicial da lista.
No 2º passo, busca o 2º menor elemento da lista e coloca na 2ª posição da lista.
No 3º passo, busca o 3º menor elemento da lista e coloca na 3ª posição da lista.
Repete até terminar a lista
In [17]:
class Ordenador:
def selecao_direta(self, lista):
fim = len(lista)
for i in range(fim - 1):
# Inicialmente o menor elemento já visto é o i-ésimo
posicao_do_minimo = i
for j in range(i + 1, fim):
if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
posicao_do_minimo = j # ...substitui.
# Coloca o menor elemento encontrado no início da sub-lista
# Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
In [18]:
lista = [10, 3, 8, -10, 200, 17, 32]
o = Ordenador()
In [20]:
o.selecao_direta(lista)
In [21]:
lista
Out[21]:
In [42]:
lista_nomes = ['maria', 'carlos', 'wilson', 'ana']
o.selecao_direta(lista_nomes)
lista_nomes
Out[42]:
In [26]:
import random
print(random.randint(1, 10))
In [33]:
from random import shuffle
x = [i for i in range(100)]
shuffle(x)
x
Out[33]:
In [35]:
o.selecao_direta(x)
x
Out[35]:
In [46]:
def comprova_ordem(list):
flag = True
for i in range(len(list) - 1):
if list[i] > list[i + 1]:
flag = False
return flag
In [47]:
comprova_ordem(x)
Out[47]:
In [48]:
list = [1, 2, 3, 4, 5]
list2 = [1, 3, 2, 4, 5]
comprova_ordem(list)
Out[48]:
In [49]:
comprova_ordem(list2)
Out[49]:
In [40]:
def busca_sequencial(seq, x):
for i in range(len(seq)):
if seq[i] == x:
return True
return False
In [43]:
def selecao_direta(lista):
fim = len(lista)
for i in range(fim-1):
pos_menor = i
for j in range(i+1,fim):
if lista[j] < lista[pos_menor]:
pos_menor = j
lista[i],lista[pos_menor] = lista[pos_menor],lista[i]
return lista
numeros = [55,33,0,900,-432,10,77,2,11]
Exercício 1: Lista ordenada
Escreva a função ordenada(lista), que recebe uma lista com números inteiros como parâmetro e devolve o booleano True se a lista estiver ordenada e False se a lista não estiver ordenada.
In [50]:
def ordenada(list):
flag = True
for i in range(len(list) - 1):
if list[i] > list[i + 1]:
flag = False
return flag
Exercício 2: Busca sequencial
Implemente a função busca(lista, elemento), que busca um determinado elemento em uma lista e devolve o índice correspondente à posição do elemento encontrado. Utilize o algoritmo de busca sequencial. Nos casos em que o elemento buscado não existir na lista, a função deve devolver o booleano False.
busca(['a', 'e', 'i'], 'e')
busca([12, 13, 14], 15)
In [54]:
def busca(lista, elemento):
for i in range(len(lista)):
if lista[i] == elemento:
return i
return False
In [55]:
busca(['a', 'e', 'i'], 'e')
Out[55]:
In [56]:
busca([12, 13, 14], 15)
Out[56]:
Exercício 1: Gerando listas grandes
Escreva a função lista_grande(n), que recebe como parâmetro um número inteiro n e devolve uma lista contendo n números inteiros aleatórios.
In [61]:
def lista_grande(n):
import random
return random.sample(range(1, 1000), n)
In [62]:
lista_grande(10)
Out[62]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
Exercício 2: Ordenação com selection sort
Implemente a função ordena(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo selection sort.
In [71]:
def ordena(lista):
fim = len(lista)
for i in range(fim - 1):
min = i
for j in range(i + 1, fim):
if lista[j] < lista[min]:
min = j
lista[i], lista[min] = lista[min], lista[i]
return lista
In [72]:
lista = [10, 3, 8, -10, 200, 17, 32]
ordena(lista)
lista
Out[72]:
Lista como um tubo de ensaio vertical, os elementos mais leves sobem à superfície como uma bolha, os mais pesados afundam.
Percorre a lista múltiplas vezes; a cada passagem, compara todos os elementos adjacentes e troca de lugar os que estiverem fora de ordem
In [83]:
class Ordenador:
def selecao_direta(self, lista):
fim = len(lista)
for i in range(fim - 1):
# Inicialmente o menor elemento já visto é o i-ésimo
posicao_do_minimo = i
for j in range(i + 1, fim):
if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
posicao_do_minimo = j # ...substitui.
# Coloca o menor elemento encontrado no início da sub-lista
# Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
def bolha(self, lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
Exemplo do algoritmo bubblesort em ação:
Inicial: 5 1 7 3 2
1 5 7 3 2
1 5 3 7 2
1 5 3 2 7 (fim da primeira iteração)
1 3 5 2 7
1 3 2 5 7 (fim da segunda iteração)
1 2 3 5 7
In [84]:
lista = [10, 3, 8, -10, 200, 17, 32]
o = Ordenador()
o.bolha(lista)
lista
Out[84]:
Módulo time:
Para medir um intervalo de tempo
import time
antes = time.time()
algoritmo_a_ser_cronometrado()
depois = time.time()
print("A execução do algoritmo demorou ", depois - antes, "segundos")
In [90]:
class Ordenador:
def selecao_direta(self, lista):
fim = len(lista)
for i in range(fim - 1):
# Inicialmente o menor elemento já visto é o i-ésimo
posicao_do_minimo = i
for j in range(i + 1, fim):
if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
posicao_do_minimo = j # ...substitui.
# Coloca o menor elemento encontrado no início da sub-lista
# Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
def bolha(self, lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
import random
import time
class ContaTempos:
def lista_aleatoria(self, n): # n = número de elementos da lista
from random import randrange
lista = [0 for x in range(n)] # lista com n elementos, todos sendo zero
for i in range(n):
lista[i] = random.randrange(1000) # inteiros entre 0 e 999
return lista
def compara(self, n):
lista1 = self.lista_aleatoria(n)
lista2 = lista1
o = Ordenador()
antes = time.time()
o.bolha(lista1)
depois = time.time()
print("Bolha demorou", depois - antes, "segundos")
antes = time.time()
o.selecao_direta(lista2)
depois = time.time()
print("Seleção direta demorou", depois - antes, "segundos")
In [91]:
c = ContaTempos()
c.compara(1000)
In [93]:
print("Diferença de", 0.16308164596557617 - 0.05245494842529297)
In [94]:
c.compara(5000)
Percorre a lista múltiplas vezes; a cada passagem, compara todos os elementos adjacentes e troca de lugar os que estiverem fora de ordem.
Melhoria: se em uma das iterações, nenhuma troca é realizada, isso significa que a lista já está ordenada e podemos finalizar o algoritmo.
In [97]:
class Ordenador:
def selecao_direta(self, lista):
fim = len(lista)
for i in range(fim - 1):
# Inicialmente o menor elemento já visto é o i-ésimo
posicao_do_minimo = i
for j in range(i + 1, fim):
if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
posicao_do_minimo = j # ...substitui.
# Coloca o menor elemento encontrado no início da sub-lista
# Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
def bolha(self, lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
def bolha_curta(self, lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
trocou = False
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
trocou = True
if not trocou: # que é igual a if trocou == False
return
import random
import time
class ContaTempos:
def lista_aleatoria(self, n): # n = número de elementos da lista
from random import randrange
lista = [random.randrange(1000) for x in range(n)] # lista com n elementos, todos sendo aleatórios de 0 a 999
return lista
def lista_quase_ordenada(self, n):
lista = [x for x in range(n)] # lista ordenada
lista[n//10] = -500 # localizou o -500 no primeiro décimo da lista
return lista
def compara(self, n):
lista1 = self.lista_aleatoria(n)
lista2 = lista1
lista3 = lista2
o = Ordenador()
print("Comparando lista aleatórias")
antes = time.time()
o.bolha(lista1)
depois = time.time()
print("Bolha demorou", depois - antes, "segundos")
antes = time.time()
o.selecao_direta(lista2)
depois = time.time()
print("Seleção direta demorou", depois - antes, "segundos")
antes = time.time()
o.bolha_curta(lista3)
depois = time.time()
print("Bolha otimizada", depois - antes, "segundos")
print("\nComparando lista quase ordenadas")
lista1 = self.lista_quase_ordenada(n)
lista2 = lista1
lista3 = lista2
antes = time.time()
o.bolha(lista1)
depois = time.time()
print("Bolha demorou", depois - antes, "segundos")
antes = time.time()
o.selecao_direta(lista2)
depois = time.time()
print("Seleção direta demorou", depois - antes, "segundos")
antes = time.time()
o.bolha_curta(lista3)
depois = time.time()
print("Bolha otimizada", depois - antes, "segundos")
In [98]:
c = ContaTempos()
c.compara(1000)
In [99]:
c.compara(5000)
Site com algoritmos de ordenação http://nicholasandre.com.br/sorting/
In [102]:
class Ordenador:
def selecao_direta(self, lista):
fim = len(lista)
for i in range(fim - 1):
posicao_do_minimo = i
for j in range(i + 1, fim):
if lista[j] < lista[posicao_do_minimo]:
posicao_do_minimo = j
lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
def bolha(self, lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
def bolha_curta(self, lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
trocou = False
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
trocou = True
if not trocou:
return
import random
import time
class ContaTempos:
def lista_aleatoria(self, n):
from random import randrange
lista = [random.randrange(1000) for x in range(n)]
return lista
def lista_quase_ordenada(self, n):
lista = [x for x in range(n)]
lista[n//10] = -500
return lista
import pytest
class TestaOrdenador:
@pytest.fixture
def o(self):
return Ordenador()
@pytest.fixture
def l_quase(self):
c = ContaTempos()
return c.lista_quase_ordenada(100)
@pytest.fixture
def l_aleatoria(self):
c = ContaTempos()
return c.lista_aleatoria(100)
def esta_ordenada(self, l):
for i in range(len(l) - 1):
if l[i] > l[i+1]:
return False
return True
def test_bolha_curta_aleatoria(self, o, l_aleatoria):
o.bolha_curta(l_aleatoria)
assert self.esta_ordenada(l_aleatoria)
def test_selecao_direta_aleatoria(self, o, l_aleatoria):
o.selecao_direta(l_aleatoria)
assert self.esta_ordenada(l_aleatoria)
def test_bolha_curta_quase(self, o, l_quase):
o.bolha_curta(l_quase)
assert self.esta_ordenada(l_quase)
def test_selecao_direta_quase(self, o, l_quase):
o.selecao_direta(l_quase)
assert self.esta_ordenada(l_quase)
In [ ]:
[5, 2, 1, 3, 4]
2 5 1 3 4
2 1 5 3 4
2 1 3 5 4
2 1 3 4 5
In [ ]:
[2, 3, 4, 5, 1]
2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5
Objetivo: localizar o elemento x em uma lista
In [103]:
class Buscador:
def busca_por_titulo(self, playlist, titulo):
for i in range(len(playlist)):
if playlist[i].titulo == titulo:
return i
return -1
def busca_binaria(self, lista, x):
primeiro = 0
ultimo = len(lista) - 1
while primeiro <= ultimo:
meio = (primeiro + ultimo) // 2
if lista[meio] == x:
return meio
else:
if x < lista[meio]: # busca na primeira metade da lista
ultimo = meio - 1 # já foi visto que não está no elemento meio, então vai um a menos
else:
primeiro = meio + 1
return -1
In [107]:
lista = [-100, 0, 20, 30, 50, 100, 3000, 5000]
b = Buscador()
b.busca_binaria(lista, 30)
Out[107]:
Exercício 1: Busca binária
Implemente a função busca(lista, elemento), que busca um determinado elemento em uma lista e devolve o índice correspondente à posição do elemento encontrado. Utilize o algoritmo de busca binária. Nos casos em que o elemento buscado não existir na lista, a função deve devolver o booleano False.
Além de devolver o índice correspondente à posição do elemento encontrado, sua função deve imprimir cada um dos índices testados pelo algoritmo.
Exemplo:
busca(['a', 'e', 'i'], 'e')
1
busca([1, 2, 3, 4, 5], 6)
2
3
4
busca([1, 2, 3, 4, 5, 6], 4)
2
4
3
In [14]:
def busca(lista, elemento):
primeiro = 0
ultimo = len(lista) - 1
while primeiro <= ultimo:
meio = (primeiro + ultimo) // 2
if lista[meio] == elemento:
print(meio)
return meio
else:
if elemento < lista[meio]: # busca na primeira metade da lista
ultimo = meio - 1 # já foi visto que não está no elemento meio, então vai um a menos
print(meio) # função deve imprimir cada um dos índices testados pelo algoritmo.
else:
primeiro = meio + 1
print(meio)
return False
In [15]:
busca(['a', 'e', 'i'], 'e')
Out[15]:
In [16]:
busca([1, 2, 3, 4, 5], 6)
Out[16]:
In [17]:
busca([1, 2, 3, 4, 5, 6], 4)
Out[17]:
In [ ]:
In [ ]:
Exercício 2: Ordenação com bubble sort
Implemente a função bubble_sort(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo bubble sort.
Além de devolver uma lista ordenada, sua função deve imprimir os resultados parciais da ordenação ao fim de cada iteração do algoritmo ao longo da lista. Observe que, como a última iteração do algoritmo apenas verifica que a lista está ordenada, o último resultado deve ser impresso duas vezes. Portanto, se seu algoritmo precisa de duas passagens para ordenar a lista, e uma terceira para verificar que a lista está ordenada, 3 resultados parciais devem ser impressos.
bubble_sort([5, 1, 4, 2, 8])
[1, 4, 2, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]
In [55]:
def bubble_sort(lista):
fim = len(lista)
for i in range(fim - 1, 0, -1):
for j in range(i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
print(lista)
print(lista)
return lista
In [56]:
bubble_sort([5, 1, 4, 2, 8])
#[1, 4, 2, 5, 8]
#[1, 2, 4, 5, 8]
#[1, 2, 4, 5, 8]
#deve devolver [1, 2, 4, 5, 8]
Out[56]:
In [57]:
bubble_sort([1, 3, 4, 2, 0, 5])
#Esperado:
#[1, 3, 2, 0, 4, 5]
#[1, 2, 0, 3, 4, 5]
#[1, 0, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
Out[57]:
In [51]:
#O resultado dos testes com seu programa foi:
#***** [0.6 pontos]: Verificando funcionamento do bubble sort - Falhou *****
#AssertionError: Expected
#[1, 3, 4, 2, 0, 5]
#[1, 3, 2, 0, 4, 5]
#[1, 2, 0, 3, 4, 5]
#[1, 0, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
# but got
#[1, 3, 4, 2, 0, 5]
#[1, 3, 2, 0, 4, 5]
#[1, 2, 0, 3, 4, 5]
#[1, 0, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
Exercício 1: Ordenação com insertion sort
Implemente a função insertion_sort(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo insertion sort.
In [62]:
def insertion_sort(lista):
fim = len(lista)
for i in range(fim - 1):
posicao_do_minimo = i
for j in range(i + 1, fim):
if lista[j] < lista[posicao_do_minimo]:
posicao_do_minimo = j
lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
return lista
In [69]:
def fatorial(n):
if n <= 1: # base da recursão
return 1
else:
return n * fatorial(n - 1) # chamada recursiva
import pytest
@pytest.mark.parametrize("entrada, esperado", [
(0, 1),
(1, 1),
(2, 2),
(3, 6),
(4, 24),
(5, 120)
])
def testa_fatorial(entrada, esperado):
assert fatorial(entrada) == esperado
In [66]:
#fatorial.py
def fatorial(n):
if n <= 1: # base da recursão
return 1
else:
return n * fatorial(n - 1) # chamada recursiva
import pytest
@pytest.mark.parametrize("entrada, esperado", [
(0, 1),
(1, 1),
(2, 2),
(3, 6),
(4, 24),
(5, 120)
])
def testa_fatorial(entrada, esperado):
assert fatorial(entrada) == esperado
In [71]:
# fibonacci.py
# Fn = 0 if n = 0
# Fn = 1 if n = 1
# Fn+1 + Fn-2 if n > 1
def fibonacci(n):
if n < 2:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
import pytest
@pytest.mark.parametrize("entrada, esperado", [
(0, 0),
(1, 1),
(2, 1),
(3, 2),
(4, 3),
(5, 5),
(6, 8),
(7, 13)
])
def testa_fibonacci(entrada, esperado):
assert fibonacci(entrada) == esperado
In [72]:
# busca binária
def busca_binaria(lista, elemento, min = 0, max = None):
if max == None: # se nada for passado, o tamanho máximo é o tamanho da lista
max = len(lista) - 1
if max < min: # situação que não encontrou o elemento
return False
else:
meio = min + (max - min) // 2
if lista[meio] > elemento:
return busca_binaria(lista, elemento, min, meio - 1)
elif lista[meio] < elemento:
return busca_binaria(lista, elemento, meio + 1, max)
else:
return meio
In [75]:
a = [10, 20, 30, 40, 50, 60]
import pytest
@pytest.mark.parametrize("lista, valor, esperado", [
(a, 10, 0),
(a, 20, 1),
(a, 30, 2),
(a, 40, 3),
(a, 50, 4),
(a, 60, 5),
(a, 70, False),
(a, 70, False),
(a, 15, False),
(a, -10, False)
])
def testa_busca_binaria(lista, valor, esperado):
assert busca_binaria(lista, valor) == esperado
Ordenação por Intercalação:
Divida a lista na metade recursivamente, até que cada sublista contenha apenas 1 elemento (portanto, já ordenada).
Repetidamente, intercale as sublistas para produzir novas listas ordenadas.
Repita até que tenhamos apenas 1 lista no final (que estará ordenada).
Ex:
6 5 3 1 8 7 2 4
5 6 1 3 7 8 2 4
1 3 5 6 2 4 7 8
1 2 3 4 5 6 7 8
In [76]:
def merge_sort(lista):
if len(lista) <= 1:
return lista
meio = len(lista) // 2
lado_esquerdo = merge_sort(lista[:meio])
lado_direito = merge_sort(lista[meio:])
return merge(lado_esquerdo, lado_direito) # intercala os dois lados
def merge(lado_esquerdo, lado_direito):
if not lado_esquerdo: # se o lado esquerdo for uma lista vazia...
return lado_direito
if not lado_direito: # se o lado direito for uma lista vazia...
return lado_esquerdo
if lado_esquerdo[0] < lado_direito[0]: # compara o primeiro elemento da posição do lado esquerdo com o primeiro do lado direito
return [lado_esquerdo[0]] + merge(lado_esquerdo[1:], lado_direito) # merge(lado_esquerdo[1:]) ==> pega o lado esquerdo, menos o primeiro elemento
return [lado_direito[0]] + merge(lado_esquerdo, lado_direito[1:])
Base da recursão é a condição que faz o problema ser definitivamente resolvido. Caso essa condição, essa base da recursão, não seja satisfeita, o problema continua sendo reduzido em instâncias menores até que a condição passe a ser satisfeita.
Chamada recursiva é a linha onde a função faz uma chamada a ela mesma.
Função recursiva é a função que chama ela mesma.
A linha 2 tem a condição que é a base da recursão
A linha 5 tem a chamada recursiva
Para o algoritmo funcionar corretamente, é necessário trocar a linha 3 por “return 1”
if (n < 2):
if (n <= 1):
No
looping infinito
Resultado: 6. Chamadas recursivas: nenhuma.
Resultado: 20. Chamadas recursivas: 24
1
In [116]:
def x(n):
if n == 0:
#<espaço A>
print(n)
else:
#<espaço B>
x(n-1)
print(n)
#<espaço C>
#<espaço D>
#<espaço E>
In [117]:
x(10)
In [126]:
def x(n):
if n >= 0 or n <= 2:
print(n)
# return n
else:
print(n-1)
print(n-2)
print(n-3)
#return x(n-1) + x(n-2) + x(n-3)
In [127]:
print(x(6))
In [138]:
def busca_binaria(lista, elemento, min=0, max=None):
if max == None:
max = len(lista)-1
if max < min:
return False
else:
meio = min + (max-min)//2
print(lista[meio])
if lista[meio] > elemento:
return busca_binaria(lista, elemento, min, meio - 1)
elif lista[meio] < elemento:
return busca_binaria(lista, elemento, meio + 1, max)
else:
return meio
In [139]:
a = [-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]
In [140]:
a
Out[140]:
In [141]:
busca_binaria(a, 99)
Out[141]:
Exercício 1: Soma dos elementos de uma lista
Implemente a função soma_lista(lista), que recebe como parâmetro uma lista de números inteiros e devolve um número inteiro correspondente à soma dos elementos desta lista.
Sua solução deve ser implementada utilizando recursão.
In [178]:
def soma_lista_tradicional_way(lista):
soma = 0
for i in range(len(lista)):
soma += lista[i]
return soma
In [179]:
a = [-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]
soma_lista_tradicional_way(a)
Out[179]:
In [181]:
b = [-10, -2, 0, 5]
soma_lista_tradicional_way(b)
Out[181]:
In [199]:
def soma_lista(lista):
if len(lista) == 1:
return lista[0]
else:
return lista[0] + soma_lista(lista[1:])
In [200]:
a = [-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]
soma_lista(a) # retorna 2952
Out[200]:
In [201]:
b = [-10, -2, 0, 5]
soma_lista(b)
Out[201]:
Exercício 2: Encontrando ímpares em uma lista
Implemente a função encontra_impares(lista), que recebe como parâmetro uma lista de números inteiros e devolve uma outra lista apenas com os números ímpares da lista dada.
Sua solução deve ser implementada utilizando recursão.
Dica: você vai precisar do método extend() que as listas possuem.
In [57]:
def encontra_impares_tradicional_way(lista):
lista_impares = []
for i in lista:
if i % 2 != 0: # é impar!
lista_impares.append(i)
return lista_impares
In [58]:
a = [5, 66, 77, 99, 102, 239, 567, 875, 934]
encontra_impares_tradicional_way(a)
Out[58]:
In [59]:
b = [2, 5, 34, 66, 100, 102, 999]
encontra_impares_tradicional_way(b)
Out[59]:
In [2]:
stack = ['a','b']
stack.extend(['g','h'])
stack
Out[2]:
In [ ]:
In [ ]:
In [1]:
def encontra_impares(lista):
if len(lista) == 0:
return []
if lista[0] % 2 != 0: # se o elemento é impar
return [lista[0]] + encontra_impares(lista[1:])
else:
return encontra_impares(lista[1:])
In [2]:
a = [5, 66, 77, 99, 102, 239, 567, 875, 934]
encontra_impares(a)
Out[2]:
In [4]:
encontra_impares([5])
Out[4]:
In [5]:
encontra_impares([1, 2, 3])
Out[5]:
In [6]:
encontra_impares([2, 4, 6, 8])
Out[6]:
In [7]:
encontra_impares([9])
Out[7]:
In [8]:
encontra_impares([4, 11])
Out[8]:
In [9]:
encontra_impares([2, 10, 20, 7, 30, 12, 6, 6])
Out[9]:
In [10]:
encontra_impares([])
Out[10]:
In [11]:
encontra_impares([4, 331, 1001, 4])
Out[11]:
Exercício 3: Elefantes
Este exercício tem duas partes:
Implemente a função incomodam(n) que devolve uma string contendo "incomodam " (a palavra seguida de um espaço) n vezes. Se n não for um inteiro estritamente positivo, a função deve devolver uma string vazia. Essa função deve ser implementada utilizando recursão. Utilizando a função acima, implemente a função elefantes(n) que devolve uma string contendo a letra de "Um elefante incomoda muita gente..." de 1 até n elefantes. Se n não for maior que 1, a função deve devolver uma string vazia. Essa função também deve ser implementada utilizando recursão. Observe que, para um elefante, você deve escrever por extenso e no singular ("Um elefante..."); para os demais, utilize números e o plural ("2 elefantes...").
Dica: lembre-se que é possível juntar strings com o operador "+". Lembre-se também que é possível transformar números em strings com a função str().
Dica: Será que neste caso a base da recursão é diferente de n==1?
Por exemplo, uma chamada a elefantes(4) deve devolver uma string contendo:
Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais
2 elefantes incomodam incomodam muita gente
3 elefantes incomodam incomodam incomodam muito mais
3 elefantes incomodam incomodam incomodam muita gente
4 elefantes incomodam incomodam incomodam incomodam muito mais
In [19]:
def incomodam(n):
if type(n) != int or n <= 0:
return ''
else:
s1 = 'incomodam '
return s1 + incomodam(n - 1)
In [20]:
incomodam('-1')
Out[20]:
In [21]:
incomodam(2)
Out[21]:
In [22]:
incomodam(3)
Out[22]:
In [23]:
incomodam(8)
Out[23]:
In [24]:
incomodam(-3)
Out[24]:
In [25]:
incomodam(1)
Out[25]:
In [26]:
incomodam(7)
Out[26]:
In [140]:
def incomodam(n):
if type(n) != int or n <= 0:
return ''
else:
s1 = 'incomodam '
return s1 + incomodam(n - 1)
def elefantes(n):
if type(n) != int or n <= 0:
return ''
if n == 1:
return "Um elefante incomoda muita gente"
else:
return elefantes(n - 1) + str(n) + " elefantes " + incomodam(n) + ("muita gente" if n % 2 > 0 else "muito mais") + "\r\n"
In [141]:
elefantes(1)
Out[141]:
In [142]:
print(elefantes(3))
In [143]:
elefantes(2)
Out[143]:
In [144]:
elefantes(3)
Out[144]:
In [145]:
print(elefantes(4))
In [ ]:
In [ ]:
In [ ]:
In [24]:
type(str(3))
Out[24]:
In [ ]:
In [4]:
def incomodam(n):
if type(n) != int or n < 0:
return ''
else:
return print('incomodam ' * n)
def elefantes(n):
texto_inicial = 'Um elefante incomoda muita gente\n'
texto_posterior1 = '%d elefantes ' + incomodam(n) + 'muito mais\n\n'
texto_posterior2 = 'elefantes ' + incomodam(n) + 'muita gente\n'
if n == 1:
return print(texto_inicial)
else:
return print(texto_inicial) + print(texto_posterior1)
In [5]:
elefantes(1)
In [3]:
elefantes(2)
Exercício 1: Fibonacci
Implemente a função fibonacci(n), que recebe como parâmetro um número inteiro e devolve um número inteiro correspondente ao n-ésimo elemento da sequência de Fibonacci. Sua solução deve ser implementada utilizando recursão.
Exemplo:
fibonacci(4)
fibonacci(2)
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
Exercício 2: Fatorial
Implemente a função fatorial(x), que recebe como parâmetro um número inteiro e devolve um número inteiro correspondente ao fatorial de x.
Sua solução deve ser implementada utilizando recursão.
In [ ]:
In [ ]: