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)) ))