Programação com Python: Exercícios Complementares e Programação

Durante a semana passada andámos a resolver exercícios complementares envolvendo cadeias de caracteres e tuplos. Esses exercícios permitiram consolidar o conhecimento sobre os objectos de cada um destes tipos e respectivas operações (na realidade, uma parte delas). Vamos apresentar soluções para esses exercícios aproveitando a ocasião para, nalguns casos mais complexos, ilustrar formas de dominar a complexidade.

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

Programação com Python

terça-feira, 1 de novembro de 2016

Exercícios Complementares e Programação

Sem comentários:

Enviar um comentário

Bem Vindo

Acerca de mim

Pesquisar neste blogue

Arquivo do blogue

Seguidores