Departamento de Ciência da
Computação - IME - USP
Escreva uma função
def substitui(str1, str2, coringa):
''' (str,str,str) -> str '''
que recebe três sequências de caracteres (strings) não vazias, sendo
que a terceira é um caractere coringa. A função deve devolver uma
sequência que é uma cópia da primeira sequência, porém substituindo-se
as ocorrências dos caracteres da segunda sequência pelo caractere
coringa, obedecendo a ordem de ocorrência em ambas as sequências.
Exemplos:
str1: "Lá vem o pato pato aqui pato acolá" str2: "papa" coringa: "X" Saída: "Lá vem o XXto XXto aqui pato acolá" str1: "Era uma casa muito engraçada não tinha teto, não tinha nada" str2: "cratera" coringa: "*" Saída: "Era uma *asa muito eng**çada não *inha t*to, não tinha nada" str1: "5248942" str2: "130" coringa: "X" Saída: "5248942" str1: "ABCEFG" str2: "ABCDEFGHIJK" coringa: "?" Saída: "???EFG"
#--------------------------------------------------------------------
# SOLUÇÃO 1:
#
#--------------------------------------------------------------------
def substitui(str1, str2, coringa):
''' (str, str, str) -> str
'''
novo_str = '' # string vazio
i = 0
j = 0
while i < len(str1) and j < len(str2):
if str1[i] == str2[j]:
novo_str += coringa
j = j + 1
else:
novo_str += str1[i]
i = i + 1
# copia o resto do string str1
while i < len(str1):
novo_str += str1[i]
i = i + 1
return novo_str
#--------------------------------------------------------------------
# SOLUÇÃO 2: usa fatiamento para copiar o final do novo string
#
#--------------------------------------------------------------------
def substitui(str1, str2, coringa):
''' (str, str, str) -> str
'''
novo_str = "" # string vazio
i = 0
j = 0
while i < len(str1) and j < len(str2):
if str1[i] == str2[j]:
novo_str += coringa
j = j + 1
else:
novo_str += str1[i]
i = i + 1
# copia o resto do string str1 através de fatiamento
novo_str += str1[i:]
return novo_str
#--------------------------------------------------------------------
# SOLUÇÃO 3.
#
#--------------------------------------------------------------------
def substitui(str1, str2, coringa):
''' (str, str, str) -> str
'''
novo_str = "" # string vazio
len1 = len(str1)
len2 = len(str2)
j = 0
for i in range(len1):
# determine próximo caractere de novo_str
if j < len2 and str1[i] == str2[j]:
caractere = coringa
j = j + 1
else:
caractere = str1[i]
# concatena com novo_str
novo_str += caractere
return novo_str
#--------------------------------------------------------------------
# SOLUÇÃO 4:
#
#--------------------------------------------------------------------
def substitui(str1, str2, coringa):
''' (str, str, str) -> str
'''
novo_str = "" # string vazio
j = 0
for i in range(len(str1)):
# determine próximo caractere de novo_str
if j < len(str2) and str1[i] == str2[j]:
novo_str += coringa
j = j + 1
else:
novo_str += str1[i]
return novo_str
Dadas duas sequências x1, x2,...,xn e y1, y2,..., yn, n > 0, de números reais, os respectivos valores médios são dados por
x = (x1 + x2 + . . . + xn)/n e y = (y1 + y2 + . . . + yn)/n
A diferença xi − x (e, similarmente, yi − y), i= 1, 2,...,n, é denominada variação.
O coeficiente de correlação entre os valores das sequências x1, x2,...,xn e y1, y2,..., yn é definido por:
r = [∑i=1,2,...n (xi − x) × (yi − y)] / [(∑i=1,2,...n (xi − x)2)0.5 × (∑i=1,2,...n (yi − y)2)0.5]
Dada uma tabela com as notas de um turma, gostaríamos de verificar se há alguma correlação entre as notas de EP e notas de prova. Em estatística, o coeficiente de correlação pode ser utilizado para tal fim. Suponha que a primeira coluna da tabela contém o nome dos alunos e as demais colunas contêm as notas de EPs e Provas. Por exemplo, a tabela abaixo é de uma turma com 5 alunos e contém as notas do EP1, P1, EP2 e P2. O traço indica uma nota que não está disponível.
NOME EP1 P1 EP2 P2
Fulano 5.0 5.0 3.0 -
Beltrano 0.0 10.0 9.0 8.0
Sicrano 10.0 10.0 10.0 10.0
Batman 9.0 9.0 - 8.0
Pinguin 1.0 2.0 3.0 4.0
Para resolver o problema acima, foi escrito o seguinte programa que lê e imprime uma tabela, lê o índice das colunas que correspondem às sequências para as quais deseja-se calcular o coeficiente de correlação, e então calcula e imprime o coeficiente de correlação. A exemplo do EP3, um valor que não está disponível é representado pelo valor None e deve ser ignorado nos cálculos.
import math
def main():
tabela = le_tabela()
imprime_tabela(tabela)
cx = int(input("Coluna da primeira seq: "))
cy = int(input("Coluna da segunda seq: "))
corr = coeficiente_correlacao(tabela, cx, cy)
if corr is None:
print("O coeficiente não pode ser calculado")
else:
print("A correlação é %f" %corr)
Suponha também que as funções abaixo já estão prontas:
def le_tabela():
''' (None) -> tabela
Lê, de um arquivo cujo nome é fornecido pelo usuário, uma tabela como
a especificada acima. Devolve a tabela em uma lista de listas, correspondendo
às linhas da tabela. Um valor não disponível é representado por None. '''
'''
def imprime_tabela(tabela):
''' (tabela) -> None
Recebe uma tabela e imprime-a.
'''
Você deverá completar o programa escrevendo duas funções especificadas nos itens (a) e (b) a seguir.
item (a)
Escreva uma função
def adiciona_coluna_variação(tabela, col):
que recebe uma tabela (tabela) como a definida anteriormente e adiciona uma coluna à tabela.
A coluna a ser adicionada corresponde à variação de cada valor da coluna de índice col.
A variação de um valor None é None.
Para o cálculo da média dos valores na coluna de índice col, desconsidere os valores None
#--------------------------------------------------------------------
# SOLUÇÃO 1: Versão com "for variavel in range():..."
#
#--------------------------------------------------------------------
def adiciona_coluna_variação(tabela,col):
''' (tabela) -> tabela
Recebe um tabela 'tabela' e o índice 'col' de uma coluna e acrescenta
a tabela uma coluna correspondente à variações dos valores na coluna de
índice 'col'. Um desvio será None se o valor na coluna for None.
'''
# calcule a media
media = media_coluna(tabela,col)
n_lin = len(tabela) # número de linhas da tabela
# calcule variação e adicione an coluna
for i in range(n_lin):
valor = tabela[i][col]
if valor != None: # implica que media != None
tabela[i].append(valor-media)
else:
tabela[i].append(None)
#---------------------------------------------------------------------
def media_coluna(tabela,col):
''' (tabela, int) -> float ou None
Recebe uma tabela 'tabela' e calcula a média dos valores na coluna 'col'.
Os valores na coluna que são None são desconsiderados. Se a coluna não
possui nenhum valor diferente de None a função retorna None
'''
# calcule a soma e o numero de valores na coluna
soma_valores = 0
no_valores = 0
n_lin = len(tabela) # número de linhas da tabela
for i in range(n_lin):
valor = tabela[i][col]
if valor != None:
soma_valores += valor
no_valores += 1
# verifique a a matriz possui algum valor
if no_valores > 0:
return soma_valores / no_valores
# se chegou aqui no_valores == 0
return None
#--------------------------------------------------------------------
# SOLUÇÃO 2: Versão com "for elemento in lista: ..."
#
#--------------------------------------------------------------------
def adiciona_coluna_variação(tabela,col):
''' (tabela) -> tabela
Recebe um tabela 'tabela' e o índice 'col' de uma coluna e acrescenta
a tabela uma coluna correspondente à variações dos valores na coluna de
índice 'col'. Um desvio será None se o valor na coluna for None.
'''
# calcule a media
media = media_coluna(tabela,col)
for linha in tabela:
if linha[col] != None: # implica que media != None
linha.append(linha[col]-media)
else:
linha.append(None)
#---------------------------------------------------------------------
def media_coluna(tabela,col):
''' (tabela, int) -> float ou None
Recebe uma tabela 'tabela' e calcula a média dos valores na coluna 'col'.
Os valores na coluna que são None são desconsiderados. Se a coluna não
possui nenhum valor diferente de None a função retorna None
'''
# calcule a soma e o numero de valores na coluna
soma_valores = 0
no_valores = 0
for linha in tabela:
# desconsidere os valores que são None
if linha[col] != None:
soma_valores += linha[col]
no_valores += 1
# verifique se a matriz possui algum valor
if no_valores > 0:
return soma_valores / no_valores
# se chegou aqui no_valores == 0
return None
item (b)
Escreva uma função
def coeficiente_correlacao(tabela, col1, col2):
que recebe uma tabela (tabela) e os índices col1 e col2 de duas colunas da tabela.
A função deve:
OBS.: No cálculo do coeficiente, os termos que envolvem um valor None não devem ser considerados. Caso não seja possível calcular o coeficiente, deve-se devolver None. Use a função do item anterior, mesmo que você não a tenha feito.
#--------------------------------------------------------------------
# SOLUÇÃO 1: Solução ideal. Usa um filtro.
#
#--------------------------------------------------------------------
import math
def adiciona_coluna_variacao(tabela, col):
soma = 0
for linha in tabela:
soma += linha[col]
if len(tabela) > 0:
media = soma / len(tabela)
for linha in tabela:
linha.append(linha[col] - media)
def filtro(tabela, col):
subtab = []
for linha in tabela:
if linha[col] is not None:
subtab.append(linha)
return subtab
def coeficiente_correlacao(tabela, col1, col2):
subtab = filtro(filtro(tabela, col1), col2)
if len(subtab) == 0: return None
adiciona_coluna_variacao(subtab, col1)
adiciona_coluna_variacao(subtab, col2)
somaxy = 0
somax2 = 0
somay2 = 0
for linha in subtab:
somaxy += linha[-2] * linha[-1]
somax2 += linha[-2] * linha[-2]
somay2 += linha[-1] * linha[-1]
if somax2 != 0 and somay2 != 0:
return somaxy/math.sqrt(somax2*somay2)
else:
return None
#--------------------------------------------------------------------
# trecho de codigo para testar as funções
# não faz parte da solução
tabela = [['Fulano ', 2, 2, None, 8], ['Beltrano', 1, None, None, 4], ['Sicrano ', None, 2, 3, 4], ['Batman ', 1, 3, 4, 4], ['Pinguin ', None, 2, 3, 4]]
for linha in tabela:
print(linha[0], end='')
for x in linha[1:]:
if x is not None:
print('%3d' %x, end='');
else:
print(' -', end='')
print()
print()
print('correlacao 1, 2:', coeficiente_correlacao(tabela, 1, 2))
print('correlacao 1, 3:', coeficiente_correlacao(tabela, 1, 3))
print('correlacao 1, 4:', coeficiente_correlacao(tabela, 1, 4))
print('correlacao 2, 3:', coeficiente_correlacao(tabela, 2, 3))
print('correlacao 2, 4:', coeficiente_correlacao(tabela, 2, 4))
print('correlacao 3, 4:', coeficiente_correlacao(tabela, 3, 4))
#--------------------------------------------------------------------
# SOLUÇÃO 2: Versão com "for variável in range(...):..."
#
#--------------------------------------------------------------------
def correlacao(tabela,col1,col2):
''' (tabela, int, int) -> float ou None
Recebe uma tabela 'tabela' e índices 'col1' e 'col2' de duas colunas
da tabela e calcula e retorna o coeficiente de correlação entre as
sequências de valores nessas colunas. Retorna None
'''
# adicione a coluna com as variações dos valores na coluna col1
adiciona_coluna_variação(tabela,col1)
# adicione a coluna com as variações dos valores na coluna col2
adiciona_coluna_variação(tabela,col2)
# imprima a nova tabela
print_tabela(tabela)
soma_numerador = 0
somax2 = 0
somay2 = 0
# índices das colunas com as variaçõa...
idx_var_col1 = len(tabela[0])-2 # índice da coluna com a variação da coluna col1
idx_var_col2 = len(tabela[1])-1 # índice da coluna com a variação da coluna col2
no_lin = len(tabela) # número de linhas da tabela
for i in range(no_lin):
valor_col1 = tabela[i][idx_var_col1]
valor_col2 = tabela[i][idx_var_col2]
if valor_col1 != None and valor_col2 != None:
soma_numerador += valor_col1 * valor_col2
if valor_col1 != None:
somax2 += valor_col1 * valor_col1
if valor_col2 != None:
somay2 += valor_col2 * valor_col2
# cuidado para não dividir por zero
if somax2 > 0 and somay2 > 0:
return soma_numerador / math.sqrt(somax2 * somay2)
return None
#--------------------------------------------------------------------
# SOLUÇÃO 3: Versão com "for elemento in lista:..."
#
#--------------------------------------------------------------------
def correlacao(tabela,col1,col2):
''' (tabela, int, int) -> float ou None
Recebe uma tabela 'tabela' e índices 'col1' e 'col2' de duas colunas
da tabela e calcula e retorna o coeficiente de correlação entre as
sequências de valores nessas colunas. Retorna None
'''
# adicione a coluna com as variações dos valores na coluna col1
adiciona_coluna_variação(tabela,col1)
# adicione a coluna com as variações dos valores na coluna col2
adiciona_coluna_variação(tabela,col2)
# imprima a nova tabela
print_tabela(tabela)
no_valores = 0 # número de valores
soma_numerador = 0
somax2 = 0
somay2 = 0
# índices das colunas com as variaçõa...
#idx_var_col1 = -2 índice da coluna com a variação da coluna col1
#idx_var_col2 = -1 índice da coluna com a variação da coluna col2
for linha in tabela:
if linha[-2] != None and linha[-1] != None:
soma_numerador += linha[-2]*linha[-1]
somax2 += linha[-2]*linha[-1]
somay2 += linha[-2]*linha[-1]
# cuidado para não dividir por zero
if somax2 > 0 and somay2 > 0:
return soma_numerador / math.sqrt(somax2 * somay2)
return None
item (a)
Escreva uma função
def simetrica(M):que recebe uma matriz 'M e devolve True caso a matriz seja simétrica em relação à sua coluna central, e devolve False em caso contrário. Suponha que a matriz é de inteiros, quadrada e de dimensão ímpar.
Exemplo: A matriz abaixo à esquerda é simétrica em relação à sua coluna central. Já a matriz à direita não é.
8 1 0 1 8 2 1 0 1 2
0 2 1 2 0 3 2 0 2 3
0 3 2 3 0 4 3 0 4 3
0 4 3 4 0 5 4 0 4 5
0 5 4 5 0 1 0 0 0 1
#--------------------------------------------------------------------
# SOLUÇÃO 1:
#
#--------------------------------------------------------------------
def simetrica(M):
''' (matriz) -> bool
Recebe uma matriz quadrada de ordem ímpar é retorna
True se a matriz fo simétrica em relação a coluna central
e False em caso contrário.
'''
# a matriz é simétrica até que se prove o contrário
simetrica = True
n = len(M) # dimensão da matriz
i = 0
while i < n and simetrica:
j = 0
while j < n // 2 and simetrica:
if M[i][j] != M[i][n-j-1]:
simetrica = False
j = j + 1
i = i + 1
return simetrica
#--------------------------------------------------------------------
# SOLUÇÃO 2:
#
#--------------------------------------------------------------------
def simetrica(M):
''' (matriz) -> bool
Recebe uma matriz quadrada de ordem ímpar é retorna
True se a matriz fo simétrica em relação a coluna central
e False em caso contrário.
'''
n = len(M) # dimensão da matriz
for i in range(n):
for j in range(n//2):
if M[i][j] != M[i][n-j-1]:
return False
return True
#--------------------------------------------------------------------
# SOLUÇÃO 3: Versão "pythoniana"
#
#--------------------------------------------------------------------
def simetrica(M):
''' (matriz) -> bool
Recebe uma matriz quadrada de ordem ímpar é retorna
True se a matriz fo simétrica em relação a coluna central
e False em caso contrário.
'''
return all( x == list(reversed(x)) for x in M )
item (b)
Escreva uma função
def recorta(M, k, i, j):
que recebe uma matriz M de inteiros,
um inteiro positivo ímpar k,
os índices i (linha) e j (coluna) de uma posição da matriz,
e devolve uma matriz que é uma cópia da submatriz de M,
quadrada e de dimensão k, centrada na posição [i][j] da matriz.
Você pode supor que a submatriz k × k está inteiramente contida em M.
Exemplo: Supondo que M é a matriz abaixo à esquerda, k é 3, e i e j são 2 e 1, respectivamente, a submatriz a ser devolvida é a que está abaixo à direita:
2 1 0 1 2
M = 3 2 0 2 3 3 2 0
4 3 0 4 3 4 3 0
5 4 0 4 5 5 4 0
#--------------------------------------------------------------------
# SOLUÇÃO 1:
#
#--------------------------------------------------------------------
def recorta(M, k, i, j):
''' (matriz, int, int, int) -> matriz
Recebe uma matriz M, um inteiro ímpar k e uma posição
e um posição (i,j) da matriz e retorna a submatriz quadrada
de dimensão k centrada em (i,j).
Pré-condicão: a função supõe que
k//2 <= i < len(M) - k//2
k//2 <= j < len(M) - k//2
'''
# submatriz que será retornada
submatriz = []
# a submatriz é centrada em [i][j] tem "raio" é k//2
raio = k//2
# canto superior direito da submatriz
inicio_lin = i - raio
inicio_col = j - raio
# canto inferior esquerdo da submatriz
fim_lin = i + raio + 1
fim_col = j + raio + 1
# percorra a submatriz a ser clonada
for ii in range(inicio_lin,fim_lin):
# cria a linha ii-raio da submatriz
linha = [] # lista vazia
for jj in range(inicio_col,fim_col):
linha.append(M[ii][jj])
submatriz.append(linha)
return submatriz
#--------------------------------------------------------------------
# SOLUÇÃO 2:
#
#--------------------------------------------------------------------
def recorta(M, k, i, j):
''' (matriz, int, int, int) -> matriz
Recebe uma matriz M, um inteiro ímpar k e uma posição
e um posição (i,j) da matriz e retorna a submatriz quadrada
de dimensão k centrada em (i,j).
Pré-condicão: a função supõe que
k//2 <= i < len(M) - k//2
k//2 <= j < len(M) - k//2
'''
# submatriz que será retornada
submatriz = []
# a submatriz é centrada em [i][j] e tem "raio" é k//2
raio = k//2
# percorra a submatriz a ser clonada
for ii in range(i-raio, i+raio+1):
# cria a linha ii-raio da submatriz
submatriz.append([]) # lista vazia
for jj in range(j-raio, j+raio+1):
submatriz[ii-raio].append(M[ii][jj])
return submatriz
#--------------------------------------------------------------------
# SOLUÇÃO 3: Versão "pythoniana"
#
#--------------------------------------------------------------------
def recorta(M, k, i, j):
''' (matriz, int, int, int) -> matriz
Recebe uma matriz M, um inteiro ímpar k e uma posição
e um posição (i,j) da matriz e retorna a submatriz quadrada
de dimensão k centrada em (i,j).
Pré-condicão: a função supõe que
k//2 <= i < n - k//2
k//2 <= j < n - k//2
'''
# a submatriz é centrada em [i][j] e tem "raio" é k//2
raio = k//2
return [ M[x][j-raio:j+raio+1] for x in range(i-raio, i+raio+1) ]
item (c)
Escreva um programa que lê uma matriz M de inteiros,
um inteiro positivo ímpar k, e imprime o número de submatrizes k × k de M
que são simétricas em relação à sua coluna central.
Para fazer este item, você pode supor que é dada uma função
def le_matriz():
que lê e devolve uma matriz, e pode usá-la sem escrevê-la.
Além disso, use as funções dos itens anteriores, mesmo que você não as tenha feito.
Exemplo: A matriz 5 × 4 abaixo (à esquerda) contém duas submatrizes 3 × 3 simétricas em relação a sua coluna central (as duas abaixo à direita).
1 1 1 1 1 1 1 . . . . .
1 0 1 1 1 0 1 . . . . .
M = 0 0 0 0 0 0 0 . . 0 0 0
1 0 0 0 . . . . . 0 0 0
2 2 2 2 . . . . . 2 2 2
#--------------------------------------------------------------------
# SOLUÇÃO 1:
#
#--------------------------------------------------------------------
def main():
''
Programa que lê uma matriz M e um número inteiro ímpar k e imprime
o numero de submatrizes k x k de M que são simétricas em relação à
coluna central.
Pré-condição: o programa supõe que k é menor um igual ao
número de linhas e colunas de M, ou seja
k <= min(len(M), len(M[0]).
'''
# leia a matriz e dimensão das submatrizes
M = le_matriz()
k = int(input("Digite um número ímpar: "))
# contador de submatrizes simétricas
cont = 0
# número de linhas e colunas da matriz
n_lin = len(M)
n_col = len(M[0])
# a submatriz é centrada em [i][j] e tem "raio" é k//2
raio = k//2
# percorra todos os possíveis centros de submatriz de dimensão k
for i in range(raio, n_lin - raio):
for j in range(raio, n_col - raio):
# recorta submatriz de dimensao k centrada em [i][j]
R = recorte(M,k,i,j)
# verifique se submatriz é simétrica
if simetrica(R):
cont = cont + 1
print("Há %d submatrizes simétricas de tamanho %d x %d"%(cont,k,k))
#--------------------------------------------------------------------
# SOLUÇÃO 2: Versão "pythoniana".
#
#--------------------------------------------------------------------
def main():
''
Programa que lê uma matriz M e um número inteiro ímpar k e imprime
o numero de submatrizes k x k de M que são simétricas em relação à
coluna central.
Pré-condição: o programa supõe que k é menor um igual ao
número de linhas e colunas de M, ou seja
k <= min(len(M), len(M[0]).
'''
# leia a matriz e dimensão das submatrizes
M = le_matriz()
k = int(input("Digite um número ímpar: "))
print("Há %d submatrizes simétricas de tamanho %d x %d" \
%(conta_simetricas(M,k),k,k))
#---------------------------------------------------------------
def conta_simetricas(M, k):
""" (matriz, int) -> int
Recebe uma matriz M e um número inteiro k e retorna
o número de submatrizes quadradas de dimensão k da matriz que são
simétricas em relação à coluna central.
"""
# submatrizes centradas em [i][j] e com "raio" é k//2
raio = k//2
return sum(map( simetrica, \
(recorta(M, k, i, j) for j in range(raio, len(M[0])-raio) \
for i in range(raio, len(M)-raio)) ))