Comecemos pelos dois primeiros (retirar duplicados de uma cadeia de caracteres, efectuar a diferença entre duas cadeias de caracteres) e pelo exercício do produto escalar.
def retira_dup(cadeia):
nova_cad = ''
for i in range(len(cadeia)):
if cadeia[i] not in cadeia[i+1:]:
nova_cad += cadeia[i]
return nova_cad
def dif_cad(cad1,cad2):
cad3 = ''
for car in cad2:
if car not in cad1:
cad3 += car
return cad3
def prod_esc(vec1,vec2):
soma = 0
for i in range(len(vec1)):
soma += vec1[i] * vec2[i]
return soma
Estes três casos são instâncias de um padrão de programação simples, designado por ciclo-acumulador. O acumulador pode ser de um dado tipo (cadeia de caracteres, inteiros) e vamos acrescentando ao acumulador mais um elemento, eventualmente condicionado a um teste (dois primeiros exemplos.Mesmo com estes exemplos triviais podemos propor implementações alternativas:
def retira(cadeia):
nova_cad = ''
for car in cadeia:
if car not in nova_cad:
nova_cad += ca
return nova_cad
def prod_esc(v1,v2):
comp = min(len(v1), len(v2))
soma = 0
for i in range(comp):
soma += v1[i] * v2[i]
return soma
def prod_esc_2(vec1,vec2):
comp = min(len(vec1),len(vec2))
aux = tuple()
for i in range(comp):
aux += (vec1[i] * vec2[i],)
return sum(aux)
No primeiro caso, a travessia da cadeia é feita de modo diferente (por conteúdo). No segundo caso, o programa passa a funcionar correctamente mesmo quando os vectores têm dimensões diferentes. No terceiro exemplo, usamos um tuplo para ir armazenando os produtos internos que no final são somados.Há muitos exemplos desta forma. Por exemplo, criar uma lista só com o elementos não nulos de outra lista:
def so_posit(vec):
vec_posit = ()
for val in vec:
if val > 0:
vec_posit += (val,)
return vec_posit
Um outro exercício pede-nos para retirar espaços entre palavras num texto guardado como uma (eventualmente longa) cadeia de caracteres. Este problema, aparentemente simples tem algumas dificuldades escondidas. Uma ideia simples consiste em detectar um espaço em branco e enquanto existirem espaços em brancos não fazer nada, até ao momento que volta a aparecer um espaço em branco. Esta solução pode ser implementada recorrendo a um ciclo diferente do ciclo for a que estamos habituados. Trata-se do ciclo while, que é executado enquanto uma dada condição for verificada. Vejamos então o código:
def retira_espacos_1(cadeia):
nova_cadeia = ''
dim = len(cadeia)
i = 0
while i < dim:
nova_cadeia += cadeia[i]
if cadeia[i] == ' ':
while i < dim and cadeia[i] == ' ':
i += 1
else:
i += 1
return nova_cadeia
Não se pense que não se pode aplicar uma solução com ciclos for. Vamos mostrar uma solução possível que faz aparecer um elemento que em inglês se designa por flag. Trata-se de um booleano que nos permite separar duas situações (caracteres brancos ou não). Na solução apresentada mais em baixo também generalizámos para o conceito de separador incluir um caractere de tabulação (\t).
def retira_espacos_2(cadeia):
sep = ' \t'
nova_cadeia = ''
branco = False
for car in cadeia:
if car in sep and not branco:
branco = True
nova_cadeia += ' '
elif car not in sep:
nova_cadeia += car
branco = False
return nova_cadeia
O problema de obter a transposta de uma matriz pode ser resolvido facilmente no pressuposto de que a matriz está representada como um tuplo de tuplos sendo que cada elemento representa uma linha da matriz. A ideia é percorrer a matriz de modo não natural , por colunas, transformando cada coluna numa … linha!
def transpose(matrix):
res = ()
for j in range(len(matrix[0])):
# por cada coluna
line = ()
for i in range(len(matrix)):
# constrói nova linha
line += (matrix[i][j],)
# junta linha
res += (line,)
return res
Sabendo como obter a transposta de uma matriz põe ajudar-nos a resolver o problema do quadrado mágico: verificar se todas as linhas, colunas e diagonais têm somas iguais ao valor do número mágico. Numa primeira abordagem a solução pode ser:
def magico(matriz):
# verifica linhas
# verifica colunas
# verifica diagonais
pass
Vamos tentar resolver cada sub-problema de modo isolado. começamos pelo mais fácil: as linhas.
def magico(matriz):
tam = len(matriz)
numero = sum(matriz[0])
# verifica linhas
for i in matriz:
soma = sum(i)
if soma != numero:
return False, None
# verifica colunas
# verifica diagonais
No caso das colunas a questão é mais difícil pois não existe modo de percorrer de forma elementar as colunas. A menos que transformemos o problema de modo a que fique idêntico ao anterior, transformando as colunas em linhas. Mas isso é o que conseguimos com a operação transposta!!!
def magico(matriz):
tam = len(matriz)
numero = sum(matriz[0])
# verifica linhas
for i in matriz:
soma = sum(i)
if soma != numero:
return False, None
# verifica colunas
for i in transpose(matriz):
soma = sum(i)
if numero != soma:
return False, None
# verifica diagonais
Fica o problema das diagonais. São duas: a principal e a secundária. Os elementos da primeira têm os índices todos iguais. Quanto à segunda, os índices somam a dimensão da matriz mais um. Isto é assim porque o segundo índice varia de 1 a n o primeiro varia de n a 1! Daí a solução final:
def magico(matriz):
tam = len(matriz)
numero = sum(matriz[0])
# verifica linhas
for i in matriz:
soma = sum(i)
if soma != numero:
return False, None
# verifica colunas
for i in transpose(matriz):
soma = sum(i)
if numero != soma:
return False, None
# verifica diagonais
soma = 0
for i in range(tam):
soma = soma + matriz[i][i]
if numero != soma:
return False, None
soma = 0
for i in range(tam):
soma = soma + matriz[tam-i-1][i]
if numero != soma:
return False, None
Este exercício mostra, ainda que seja de modo primitivo, a ideia de dividir um problema em sub-problemas, teoricamente mais simples. Vejamos a mesma ideia num último exemplo que envolve um programa que conta o número de caracteres, palavras e linhas existentes num texto.
def wc_1(texto):
if texto:
# conta caracteres
num_car = conta_car(texto)
# conta palavras
num_pal = conta_pal(texto)
# conta linhas
num_lin = conta_linhas(texto)
return num_car, num_pal, num_lin
else:
return 0,0,0
Num texto não vazio, contamos separadamente cada condição. Faltam as funções que resolvem cada um dos casos:
def conta_car(texto):
return len(texto)
def conta_linhas(texto):
return texto.count(‘\n’) + 1
def conta_pal(texto):
sep_pal = '\n\t '
pal = False
num_pal = 0
for car in texto:
if (car not in sep_pal) and not pal:
num_pal += 1
pal = True
elif car in sep_pal and pal:
pal = False
return num_pal
Também aqui as duas primeiras situações são triviais e apenas a contagem de palavras levanta algumas dificuldades que resolvemos recorrendo à técnica da flag já acima referida. É evidente que esta solução não é muito eficiente pois o texto é percorrido mais do que uma vez. Mas se entendeu a solução que apresentámos não teria dificuldade em mudar para aquela que a seguir apresentamos e que já não sofre da ineficiência referida:
def wc_2(texto):
blank = ' \n\t'
if len(texto) == 0:
return 0,0,0
cars = 0
palavras = 1
linhas = 1
for i in range(len(texto)-1):
cars+= 1
if texto[i] in blank and texto[i+1] not in blank:
palavras += 1
if texto[i] == '\n':
linhas += 1
return cars, palavras, linhas
Sem comentários:
Enviar um comentário