Teste # 2 - Solução dos problemas (TP1 e TP2)

Turma TP1

P2

O problema 2 pedia para criar um programa que transformasse uma cadeia de caracteres numa outra na qual a primeira ocorrência de um dado caractere fosse replicada um numero de vezes na nova cadeia igual à posição onde ocorre na cheia original mais um. Era necessário manter a ordem relativa das ocorrências dos diferentes caracteres. Este exercício tinha uma solução simples baseada no padrão tantas vezes trabalhado de ciclo - acumulador.

 def mul_car(cadeia):
    cad = ''
    for i in range(1,len(cadeia)+1):
        elem = cadeia[i-1]
        if elem not in cad:
            cad += elem * i
    return cad

cad é o acumulador onde vamos acrescentando às soluções parciais as ocorrências do novo caractere. notar a existência da condicional que serve para filtrar os caracteres individuais já utilizados.

Quem conhece Python de um modo mais profundo podia propor uma versão alternativa baseada em listas por compreensão: def mul_car2(cadeia): return ''.join([cadeia[i] * (i+1) for i in range(len(cadeia)) if cadeia[i] not in cadeia[:i]]) Note-se o desaparecimento explicito do acumulador e o modo como se transforma a lista resultado numa cadeia de caracteres.

P3

A sobreposição de duas imagens a preto e branco, representadas como listas de listas de uns e zeros não representa problema de maior. A sobreposição significa que basta que numa dada posição (um dado pixel) esteja a 1 (preto) o resultado na nova imagem deve também ser 1. Percorrendo naturalmente a imagem com dois ciclos for e alternado um a um chegamos ao resultado desejado.

def sobreposicao(img1, img2):
    nova_img = []
    for i in range(len(img1)):
        nova_linha = []
        for j in range(len(img1[0])):
            nova_linha.append(img1[i][j] or img2[i][j])
        nova_img.append(nova_linha)
    return nova_img

Também aqui podemos recorrer a listas por compreensão para obter um programa mais curto:

def sobreposicao2(img1,img2):
    return [ [(img1[i][j] or img2[i][j]) for j in range(len(img1[0]))] for i in range(len(img1))]

Notar a existência de dois ciclos e como o ciclo mais interior aparece primeiro.

Turma TP2

P2

Anagrama é um conceito conhecido: palavras formadas por permutações das mesmas letras e em igual quantidade. O exemplo clássico em português é dado pelas palavras “roma” e “amor”. Uma solução ingénua para esta questão seria testar o igual comprimento das palavras e depois verificar se cada caractere de uma ocorre na outra.

def anagramas1(cad1,cad2):
    """versão errada!"""
    if len(cad1) != len(cad2):
        return False
    for elem in cad1:
        if elem not in cad2):
            return False
    return True

Para verificar que está errada basta testar com as palavras ‘aab’ e ‘bba’. Em vez de falso vai dar verdadeiro. O problema está no facto de o numero de ocorrência de cada caractere em cada uma das palavras ter que ser o mesmo. Daí que uma solução simples seja:

def anagramas2(cad1,cad2):
    if len(cad1) != len(cad2):
        return False
    for elem in cad1:
        if cad1.count(elem) != cad2.count(elem):
            return False
    return True

Claro que podemos pensar em alternativas. Por exemplo, transformar as cadeias em listas, ordená-las e verificar se resulta em duas listas … iguais:

def anagramas3(cad1,cad2):
    list_cad1 = list(cad1)
    list_cad2 = list(cad2)
    list_cad1.sort()
    list_cad2.sort
    return list_cad1 == list_cad2

Para os pitónicos puristas (peritos??) temos outra solução:

from collections import Counter

def anagramas4(cad1, cad2):
    return Counter(cad1) == Counter(cad2)

Counter é um typo que se pode definir como uma colecção não ordenada que implementada como um dicionário em que as chaves são os elementos e o valor o numero de ocorrências da chave. O conceito de dicionário será dado na próxima aula!

Quem não souber da existência de Counter pode implementar a sua solução:

def conta_elems(seq):
    conta = {}
    for elem in seq:
        counts[elem] = counts.get(elem, 0) + 1
    return conta

def anagramas4b(cad1, cad2):
    return conta_elems(cad1) == conta_elems(cad2)

Parece que já temos mulitas alternativas e que dificilmente arranjaremos outra substancialmente diferente. Ou será que não??? Olhemos o código abaixo:

def anagramas5(cad1, cad2):
    return [False,True][sum([ord(x) for x in cad1]) == sum([ord(x) for x in cad2])]

Experimente e … surpresa! Parece que funciona. Mas como? Como se pode ver usamos listas por compreensão para transformar cada lista na lista dos seus códigos numéricos. Esses códigos são somados e verificamos se são ou não iguais. O resultado por isso ou é True ou é False. Como disse nas aulas, True é representado por 1 e False por zero. Então o que temos no final é a forma [False,True][1] ou [False,True][0], isto é estamos a obter por indexação o elemento da lista [False,True] ou na posição zero (False) ou na posição um (True). Engenhoso, mas por ventura não muito claro e dependente do modo como estão implementados os booleanos.

P3

A intersecção de duas imagens é semelhante à sobreposição. A diferença agora é que devemos ter um apenas nas situações em que as duas imagens estejam, na mesma posição, iguais a um. Assim uma solução simples será:

def interseccao(img1, img2):
    nova_img = []
    for i in range(len(img1)):
        nova_linha = []
        for j in range(len(img1[0])):
            nova_linha.append(img1[i][j] and img2[i][j])
        nova_img.append(nova_linha)
    return nova_img

Também aqui podíamos recorrer a uma solução com listas por compreensão. Ao leitor o cuidado de o fazer.

Um problema, várias soluções

Sempre que estamos diante de um problema novo a melhor maneira de o resolver é tentar identificar um modelo de solução por analogia com problemas antigos já resolvidos. Para além disso, quando os problemas têm uma certa complexidade, pois necessitamos fazer muitas coisas e sujeitos a diferentes restrições, nada melhor do que dividir o problema em sub-problemas mais simples e/ou tentar resolver primeiro uma versão mais simples que depois completamos. Isto são princípios que temos vindo a explorar ao longo das aulas. Também é um facto que conhecendo melhor a linguagem de programação podemos encontrar variantes para a nossa solução inicial, eventualmente mais eficientes. Vamos ver este último aspecto com exemplos simples das aulas.

Contar quantos elementos de uma lista são menores do que um elemento de referência.

A solução trivial passa por percorrer (recorrendo a um ciclo) a lista e ir contando sempre que aparecer um elemento menor (uso de um acumulador. Mas mesmo esta situação pode ser feita de diferentes maneiras: percorrer a lista por índice ou percorrer por conteúdo:

def conta_menores1(num,lista_num):
    acum = 0
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum += 1
    return acum


def conta_menores2(num,lista_num):
    acum = 0
    for i in lista_num:
        if i < num:
            acum += 1
    return acum

A segunda versão é a preferível do ponto de vista da eficiência, sendo que, na nossa opinião, é mais clara. Quem conhecer o conceito de listas por compreensão pode sugerir outra solução:

def conta_menores3(num, lista_num):
    return sum([ 1 for i in lista_num if i < num])

Será que podemos arranjar ainda outra solução. Na aula um aluno sugeriu uma alternativa muito interessante:

def conta_menores4(num, lista_num):
    lista_num.sort()
    return lista_num.index(num)

Nesta solução ordenamos a lista e depois calculamos a posição do número da lista que vai ser igual ao número de elementos menores. Mas esta solução tem um problema: só funciona se o número de referência estiver na lista. Consegue perceber porquê?? Tratemos agora de uma variante deste problema.

Listagem dos menores

Podemos ter soluções semelhantes às anteriores. O que muda é a natureza do acumulador (agora terá que ser um contentor, tuplo ou lista.

def lista_menores1(num,lista_num):
    acum = []
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum += [lista_num[i]]
    return acum


def lista_menores2(num,lista_num):
    acum = []
    for i in lista_num:
        if i < num:
            acum += [i]
    return acum

Aqui podemos variar a forma de juntar o elemento à lista, recorrendo ao método append em substituição da operação de concatenação:

def lista_menores3(num,lista_num):
    acum = []
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum.append(lista_num[i])
    return acum

def lista_menores4(num,lista_num):
    acum = []
    for i in lista_num:
        if i < num:
            acum.append(i)
    return acum

E uma vez mais a solução com listas por compreensão (a nossa preferida):

def lista_menores5(num, lista_num):
    return [i for i in lista_num if i < num]

Será que a sugestão do nosso aluno também se aplica aqui (no pressuposto de que o elemento está na lista)? Claro:

def lista_menores4(num,lista_num):
    lista_num.sort()
    return lista_num[:lista_num.index(num)]

Soma cumulativa

Agora a questão é a de dada uma lista construir uma nova lista em que na posição i vamos ter a soma dos elementos da lista original entre as posições inicial e i (inclusivé). A solução mais simples baseia-se no recurso ao padrão ciclo-acumulador que contem no interior do ciclo outro padrão ciclo-acumulador. Este último é usado para o cálculo da soma cumulativa.

def soma_cumulativa(lista):
    acum = []
    for i in range(len(lista)):
        # soma de 0 a i
        soma = 0
        for j in range(i+1):
            soma += lista[j]
        # junta soma ao acumulador
        acum.append(soma)
    return acum 

Conhecendo a existência da função sum podemos simplificar a nossa primeira solução:

def soma_cumulativa2(lista):
    acum = []
    for i in range(len(lista)):
        # soma de 0 a i
        soma = sum(lista[:i+1])
        # junta soma ao acumulador
        acum.append(soma)
    return acum 

E, também aqui, o recurso a listas por compreensão da origem a um programa mais curto:

def soma_cumulativa3(lista):
    return [sum(lista[:i+1]) for i in range(len(lista))]

Será que podemos fazer melhor? Podemos. Uma pequena reflexão sobre o problema mostra que existe uma relação simples entre duas somas cumulativas consecutivas: basta somar à soma anterior (de 0 a i) o valor do elemento na posição (i+1):

def soma_cumulativa4(lista):
    acum = [lista[0]]
    for i in lista[1:]:
        acum.append(acum[-1]+i)
    return acum 

E pronto. Esperamos que tenham ficado com uma ideia de que em programação mesmo os problemas mais simples podem ter várias alternativas.

Vamos ao Casino?

Nas aulas abordámos o método de Monte Carlo e vimos como nos pode auxiliar a calcular o valor aproximado de pi. Eis o código:

def monte_carlo_pi(num_dardos):
    """
    Calcula o valor de pi pelo método de Monte Carlo.
    """
    # define e inicializa acumulador
    conta_dardos_in = 0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.random()
        y= random.random()
        # dentro ou fora?
        d = (x**2 + y**2)**0.5
        if d <= 1:
            conta_dardos_in = conta_dardos_in + 1
    res_pi = 4 * (conta_dardos_in/num_dardos)
    return res_pi

A ideia consiste em ter um quarto de círculo de raio um (cuja área é igual a pi/4) inscrito num quadrado de lado um. Simulamos de seguida o lançamento de dardos cuja posição de impacto é escolhida com base numa distribuição uniforme (todos os pontos são equi-prováveis). A percentagem de dardos que cai dentro do círculo, multiplicado por 4 dá-nos o valor pretendido.

Este método pode ser aplicado nas mais diversas situações e problemas. Por exemplo, determinar a probabilidade de um dardo lançado aleatoriamente cair dentro de uma certa zona. Procurámos resolver esta questão no caso das áreas 1 e 3 da figura abaixo.

A ideia para a solução não é diferente da anterior: contar a percentagem dos dardos que caem dentro de uma das áreas pretendidas:

def monte_carlo_reg_2(num_dardos):
    """
    Calcula o valor de uma área  pelo método de Monte Carlo.
    """
    # define e inicializa acumulador 
    conta_dardos_in = 0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.uniform(0,2)
        y= random.uniform(0,2)
        # dentro ou fora
        zona_1 = (x <= 1 and y >=1)
        zona_3 = (x >= 1 and y <= 1) or (x>= 1 and y <= x)
        if zona_1 or zona_3:
            conta_dardos_in = conta_dardos_in + 1
    res = conta_dardos_in/num_dardos
    return res

Com estes dois exemplos o leitor está preparado para dar o salto para uma generalização da abordagem. Imaginemos que queremos calcular um dado integral:

Sabemos que o valor do integral é dado pela área debaixo de f(x), para x entre a e b. Então conhecido f(x) podemos encontrar uma figura geométrica de área conhecida e que envolva f(x). Feito isto só temos que calcular a percentagem de dados que ficam debaixo da curva e multiplicar pela área. E o programa que o faz é o seguinte:

def monte_carlo_int(funcao, min_x, max_x, min_y, max_y, num_dardos):
    """
    Calcula o valor de um integral  pelo método de Monte Carlo.
    """
    # define e inicializa acumulador 
    conta_dardos_in = 0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.uniform(min_x,max_x)
        y= random.uniform(min_y,max_y)
        # dentro ou fora
        zona_limite = funcao(x) 
        if y < zona_limite:
            conta_dardos_in = conta_dardos_in + 1
    area = (max_x - min_x) * (max_y -min_y)
    res = area * (conta_dardos_in/num_dardos ) 
    return res

Podemos testar o programa para um caso concreto, o da função y = e^x. A imagem mostra o seu comportamento entre x= 0 e x = 1, e ainda alguns dardos que foram “lançados”:

Como chamamos o programa? Fácil. Definimos a função, os respectivos valores máximos e mínimos para x e y e o número de dardos:

def my_exp(x):
    return pow(math.e, x)

minx = 0
maxx = 1
miny = 0 
maxy = math.e

print(monte_carlo_int(my_exp, minx,maxx,miny,maxy,1000000))

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

Devagar se vai ao longe

Uma das questões mais frequentes com que um programador novato se depara é o de saber como dominar a complexidade de um problema. Vamos tentar ajudar a ultrapassar essa dificuldade recorrendo a dois princípios simples: aproximar a solução por etapas e esquecer inicialmente alguns aspectos do problema que serão resolvidos posteriormente.

Suponhamos que nos pedem para escrever um programa que nos permita visualizar de modo natural uma matriz, mas não apenas os seus valores mas também a posição de cada elemento na matriz. Um exemplo seria:

Vamos então à solução. Comecemos por tomar uma decisão simples e razoável: mostrar a matriz linha a linha:

def mostra_mat(matriz):
    num_linhas = len(matriz)
    for linha in range(num_linhas):
        # mostra linha
        pass

(a instrução pass… não faz nada, mas permite que o programa esteja sintaticamente correcto!). Parece que não avançamos muito, mas também temos segurança sobre a correcção deste programa. Temos agora que tomar uma segunda decisão: como mostrar uma linha? E decidimos fazê-lo... coluna a coluna!

def mostra_mat(matriz):
    num_linhas = len(matriz)
    num_colunas = len(matriz[0])
    for linha in range(num_linhas):
        # mostra linha
        for coluna in range(num_colunas):
            # mostra coluna
            pass

Está na hora de concretizar. Vamos supor que a matriz está representada por um tuplo de tuplos, ou seja, cada elemento do duplo representa uma linha. Esquecendo o detalhe das posições vamos resolver o problema de mostrar apenas o conteúdo. Por cada linha, vamos imprimir os elementos de todas as colunas. Como queremos que tudo fique na mesma linha, usaremos a palavra chave end da instrução de print com a indicação de que os elementos devem estar separados por uma tabulação.

def mostra_mat(matriz):
    num_linhas = len(matriz)
    num_colunas = len(matriz[0])
    for linha in range(num_linhas):
        # mostra linha
        for coluna in range(num_colunas):
            # mostra coluna
            print(matriz[linha][coluna],end='\t')
        print()

Notar o uso do print() no fim da impressão da linha no final do segundo ciclo for, precisamente para forçar a mudança de linha. Já só falta resolver a questão dos índices da matriz. Mas agora isso é muito fácil, pois em cada momento, os nomes linha e coluna têm os valores de que precisamos:

def mostra_mat(matriz):
    num_linhas = len(matriz)
    num_colunas = len(matriz[0])
    for linha in range(num_linhas):
        # mostra linha
        for coluna in range(num_colunas):
            # mostra coluna
            print('(',linha,',',coluna,'): ',matriz[linha][coluna],end='\t')
        print()

Claro que se não gostarmos muito do aspecto podemos melhorar um pouco a saída, evitando o aparecimento de muitos espaços em branco:

def mostra_mat_2(matriz):
    num_linhas = len(matriz)
    num_colunas = len(matriz[0])
    for linha in range(num_linhas):
        # mostra linha
        for coluna in range(num_colunas):
            # mostra coluna
            print('(%d,%d): %s' % (linha,coluna,matriz[linha][coluna]),end='\t')
        print()

Moral da história: devagar se vai ao longe!

Padrão Ciclo - Acumulador

Acontece com muita frequência que ao fim de resolvermos vários problemas verificamos existir um padrão comum a todas as soluções. Una vez descoberto o padrão passamos a olhar para novos problemas entanto perceber em que medida esse padrão se pode aplicar, adaptado claro está à nova questão. Vejamos uns exemplos simples.

Comecemos pelo caso de um programa que retira de uma cadeia de caracteres os elementos repetidos.

def tira_repete_1(cadeia):
    acum = ''
    for car in cadeia:
        if car not in acum:
            acum = acum + car
    return acum

A ideia é ir juntando caracteres formando um novo objecto associado ao nome atum cada vez que o ciclo é percorrido, caso o elemento ainda não esteja na nova cadeia.

[ Mesmo um problema tão simples pode ter várias variantes em função do que a linguagem concreta permite:

def tira_repete_2(cadeia):
    acum = ''
    for i in range(len(cadeia)):
        if cadeia[i] not in cadeia[i+1:]:
            acum = acum + cadeia[i]
    return acum

def tira_repete_3(cadeia):
    acum = ''
    for i in range(len(cadeia)):
        if cadeia.find(cadeia[i],i+1) == -1:
            acum = acum + cadeia[i]
    return acum

def tira_repete_4(cadeia):
    return ''.join([cadeia[i] for i in range(len(cadeia)) if cadeia[i] not in cadeia[i+1:]])

Mas este aspecto não é o objectivo deste texto e por isso não comentamos as diferenças.]

Admitamos agora que nos pedem para calcular o produto escalar de dois vectores.

Um programa simples para resolver esta questão é o seguinte:

def prod_esc(vec1,vec2):
    acum = 0
    for i in range(len(vec1)):
        acum = acum + (vec1[i] * vec2[i])
    return acum

Nesta solução vamos acumulando a soma parcial em acum. A cada etapa do ciclo vamos acrescentando à soma parcial o novo termo vec1[i] * vec2[i].

[ Esta solução supõe que os vectores têm a mesma dimensão. Caso não seja verdade uma alternativa seria:

def prod_esc(vec1,vec2):
    dim = min(len(vec1), len(vec2))
    acum = 0
    for i in range(dim):
        acum = acum + (vec1[i] * vec2[i])
    return acum

]

Estes dois exemplos mostram uma solução comum: um acumulador onde vamos juntando o resultado parcial efectuado em cada etapa do ciclo. Armados desta conhecimento vamos tentar uma nova questão: calcular o factorial de um inteiro não negativo, ou seja, n!. Como fazer? Sabemos que por definição n! = n X (n-1) X (n-2) X … X 1. Olhando para a fórmula verificamos que ela envolve produtos repetidos. Podemos então recorrer a um ciclo, controlado por uma variável i, em que na etapa i do ciclo já calculámos os factorial … de i.

def fact(n):
    acum = 1
    for i in range(1,n+1):
        acum = acum * i
    return acum

Olhando para estes três exemplos também resulta claro qual deve ser o valor inicial do acumulador: deve ser o elemento neutro para a operação realizada no interior do ciclo (cadeia vazia para concatenação de cadeias, 0 para somas, 1 para produtos.).

Quem faz também desfaz...

Vamos fazer o exercício inverso da encriptação: dado um texto encriptado de acordo com um dado método refazer o texto original. Vamos fazer o exercício para cada um dos três métodos de que falámos.

Separação Pares - Ímpares

Este parece ser um caso trivial. Divididos o texto ao meio e depois tiramos alternadamente os caracteres de cada uma das componentes.

def desencripta_1(texto):
    # divide ao meio e separa
    meio = len(texto)//2
    pares = texto[:meio]
    impares = texto[meio:]
    # constrói texto
    novo_texto = ''
    for i in range(meio):
        novo_texto = novo_texto + pares[i] + impares[i]
    return novo_texto

Acontece que se testarmos com vários exemplos verificamos que nalguns casos o resultado não é o esperado. Não precisamos de reflectir muito para verificar que o problema acontece quando o texto tem um número ímpar da caracteres. Neste caso, o número de elementos na posição par é superior em uma unidade do número de elementos nas posições ímpares. Temos pois que ter cuidado quando fazemos a divisão ao meio, diferente em cada um dos casos. Resolvida esta questão uma solução será:

def desencripta_12(texto):
    # divide ao meio e separa
    comp = len(texto)
    meio, imp = divmod(comp,2)
    pares = texto[:meio]
    impares = texto[meio+imp:]
    # constrói texto
    novo_texto = ''
    for i in range(meio):
        novo_texto = novo_texto + pares[i] + impares[i]
    if imp:
        novo_texto = novo_texto + texto[meio]
    return novo_texto

Como se pode ver usamos a operação divido que nos permite obter as duas componentes através do mecanismo de desempacotamento:

meio,imp = divmod(com,2)

O nome imp estará associado ao objecto 1 (se texto tiver comprimento ímpar) ou ao objecto 0 (caso tenha comprimento par).

Distância Fixa

Neste método, se um caractere é deslocado n posições para a frente na codificação, então na descodificação cada caractere deve ser deslocado n posições para … trás!

def desencripta_2(texto_encriptado,chave):
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    texto_normal = ''
    for car in texto_encriptado:
        indice = alfabeto.find(car) 
        texto_normal = texto_normal + alfabeto[(indice - chave)%len(alfabeto)]
    return texto_normal

Assumimos um alfabeto co mas 26 letras minúsculas mais o espaço em branco, mas a solução pode ser adaptada a qualquer alfabeto sem problemas.

Chave Aleatória

Este caso aparenta ser o mais complexo. Vejamos se é verdade. Comecemos por mostrar o código que permite definir uma chave e encriptar um texto:

def encripta_3(texto, alfabeto,chave):
    #chave = define_chave(alfabeto)
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + chave[ind]    
    return novo_texto

import random

def define_chave(alfabeto):
    simbolos = alfabeto
    chave = ''
    for car in alfabeto:
        novo_simb = random.choice(simbolos)
        ind = simbolos.index(novo_simb)
        simbolos = simbolos[:ind] + simbolos[ind+1:]
        chave = chave + novo_simb    
    return chave

Como a correspondência é um para um, se, por exemplo, a “b” no texto original corresponde “h” na chave então quando encontramos no texto codificado um “h” devemos ter um “b” no texto original. Afinal a solução não é assim tão complexa:

def desencripta_3(texto_encriptado,alfabeto,chave):
    texto_normal = ''
    for car in texto_encriptado:
        indice = chave.find(car) 
        texto_normal = texto_normal + alfabeto[indice]
    return texto_normal

Mas se pensarmos um pouco mais no que dissemos sobre a correspondência um a um, chegamos à conclusão que codificar e descodificar são o mesmo processo pelo que apenas precisamos de um programa. Dito de outro modo:

def desencripta_31(texto,alfabeto,chave):
    return encripta_3(texto,chave,alfabeto)

E pronto. Divirta-se a escrever variantes das soluções propostas. Por exemplo, usando sempre o alfabeto como parâmetro.

Codificar textos

Durante as aulas introduzimos as cadeias de caracteres. Elas são o modo natural de guardar textos. Uma tarefa relevante é a de codificar um texto de modo que possa ser transmitido com segurança. Vamos ver como a tarefa de encriptar um documento pode ser resolvida com facilidade em Python. Iremos usar três métodos diferentes, que naturalmente vão requerer algoritmos distintos. O primeiro, limita-se a separar o texto em duas partes em função da posição par ou ímpar do caractere no texto. Uma vez esta decomposição feita o texto é recomposto juntando as duas partes. O segundo método precisa conhecer o alfabeto usado e estabelece uma correspondência entre cada caractere do alfabeto e um outro caractere do mesmo alfabeto que se encontra n posições à sua frente. Finalmente o terceiro método usa uma correspondência entre caracteres não baseada num distância fixa mas antes definida estocasticamente. Vejamos então algumas soluções possíveis.

Separação pares ímpares

Comecemos com um pedaço de código que deixa claro qual a estratégia a seguir.

def encripta_0(texto):
    # selecciona pares
    # selecciona ímpares
    # junta pares e ímpares
    pass

Olhemos agora para cada um dos sub-problemas. Como extrair os caracteres que se encontram nas posições pares do texto. Não é preciso pensar muito para decidir que podemos recorrer ao modelo baseado na ideia de ciclo + acumulador:

def encripta_0(texto):
    # selecciona pares
    pares = ''
    for i in range(len(texto)):
        # índice par?
        if i%2 == 0:
            pares = pares + texto[i]
    # selecciona ímpares
    # junta pares e ímpares
    pass

Resolver o problema para os mares é semelhante, pelo que chegamos à nossa primeira solução.

def encripta_0(texto):
    # selecciona pares
    pares = ''
    for i in range(len(texto)):
        # índice par?
        if i%2 == 0:
            pares = pares + texto[i]
    # selecciona ímpares
    impares = ''
    for i in range(len(texto)):
        # índice ímpar?
        if i%2 != 0:
            impares = impares + texto[i]    
    # junta pares e ímpares
    novo_texto = pares + impares
    return novo_texto

Porque é que esta solução não nos agrada? Desde logo porque o texto é percorrido duas vezes. Isso decorre do facto de termos isolado a construção dos pares da dos ímpares. Mas é óbvio que podemos fazer a divisão par/ímpar percorrendo o texto uma só vez:

def encripta_1(texto):
    pares = ''
    impares = ''
    for i in range(len(texto)):
        if i % 2 == 0:
            pares = pares + texto[i]
        else:
            impares = impares + texto[i]
    return pares + impares

A solução pode ser ainda outra se usarmos o conhecimento que temos da operação de fatiamento:

def encripta_11(texto):
    pares = texto[0::2]
    impares = texto[1::2]
    return pares + impares

ou ainda, eliminando os nomes auxiliares:

def encripta_12(texto):
    return texto[0::2] + texto[1::2]

Distância Fixa

Nesta abordagem vamos necessitar conhecer o alfabeto, ou seja, os símbolos que podem aparecer no texto. Para simplificar vamos supor que o nosso alfabeto é formado pelas letras minúsculas mais o espaço em branco. O modelo ciclo - acumulador permite um primeiro esboço de solução:

def codifica(texto,n):
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    novo_texto = ''
    for car in texto:
        # por cada caractere do texto procura o equivalente n posições “à frente”
        # junta ao acumulador
    return novo_texto

O sub-problema realmente diferente consiste em encontrar o novo caractere. Um ideia básica é usar o seu índice no alfabeto e somar-lhe n. O único problema que pode surgir é com os caracteres no final. Por exemplo, caso n=2 o equivalente a z deve ser o a. Podemos resolver esta questão usando a operação módulo:

def codifica(texto,n):
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    novo_texto = ''
    for car in texto:
        novo_indice = (alfabeto.index(car) + n) % len(alfabeto)
        novo_car = alfabeto[novo_indice]
        novo_texto = novo_texto + novo_car
    return novo_texto

É claro que podemos chegar a outra solução. Por exemplo, podemos construir primeiro a correspondência e só depois encriptar.

def codifica_2(texto,n):
    alfabeto = 'abcdefghijklmnopqrstuvxyz '
    # constrói código
    cod_alfabeto = ''
    for car in alfabeto:
        indice = alfabeto.index(car)
        novo_indice = (indice + n) % len(alfabeto)
        cod_alfabeto = cod_alfabeto + alfabeto[novo_indice]
        
    # encripta
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + cod_alfabeto[ind]
    return novo_texto

Faz ainda sentido que o alfabeto seja um parâmetro do programa principal:

def codifica_3(texto,alfabeto, n):
    # define chave
    alfa_chave = chave(alfabeto,n)
    # encripta
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + alfa_chave[ind]
    return novo_texto

def chave(alfabeto,n):
    alfa_chave = ''
    for car in alfabeto:
        indice = alfabeto.index(car)
        novo_indice = (indice + n) % len(alfabeto)
        alfa_chave = alfa_chave + alfabeto[novo_indice] 
    return chave

Notar que criámos uma definição auxiliar para a construção da chave. Chave Aleatória

A ideia agora é estabelecer uma relação um para um entre o alfabeto e a chave de modo aleatório. Na linha do último exemplo vamos ver como podemos criar a chave. Em Python existem várias formas de o poder fazer, umas bem simples, mas vamos buscar uma solução à luz do que foi dados nas aulas. Vamos então caçar com gato…. A ideia é trivial: gerar uma permutação do alfabeto inicial recorrendo a uma cópia desse alfabeto ao qual vamos buscar aleatoriamente um símbolo para a chave. De seguida esse símbolo é retirado para garantir que geramos uma permutação.

import random

def define_chave(alfabeto):
    simbolos = alfabeto
    chave = ''
    for car in alfabeto:
        novo_simb = random.choice(simbolos)
        ind = simbolos.index(novo_simb)
        simbolos = simbolos[:ind] + simbolos[ind+1:]
        chave = chave + novo_simb    
    return chave

Tendo a chave, a encriptação é semelhante ao exemplo anterior.

def encrita_3(texto, alfabeto):
    chave = define_chave(alfabeto)
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + chave[ind]    
    return novo_texto

Teste 1 - TP2

Pergunta 1
Em Python tudo são objectos. Os objectos têm atributos que dependem do tipo do objecto. No entanto existem três que todos têm: identidade, valor e tipo. O nome de um objecto é também um atributo que o objecto obtém através de uma atribuição. Quando fazemos x = x + 1 isso é informaticamente possível porque à esquerda do sinal de atribuição o ‘x’ remete para o nome, enquanto que à direita do sinal de atribuição remete o valor.

Pergunta 2
Uma questão trivial que pedia para usar Python como se de uma vulgar calculadora se tratasse.

import math

def distancia(lat1,long1,lat2,long2):
    termo1 = math.sin(lat1) * math.sin(lat2)
    termo2 = math.cos(lat1) * math.cos(lat2) * math.cos(long1 - long2)
    return 6371.01 * math.acos(termo1 + termo2)

Pergunta 3
Desenhar um tiragulo rectângulo é semelhante a desenhar um triângulo, só que agora basta termos as duas medidas dos catetos. Tornar o desenho livre da dimensão dos lados, da orientação, da cor, obriga a usar esses elementos como parâmetros e a uma preparação para o desenho antes de concretizar. É isso que faz o código seguinte:

import turtle

def tri_rect(x,y,orienta,cor,lado_1,lado_2):
    # inicialização
    turtle.penup()
    turtle.goto(x,y)
    turtle.setheading(orienta)
    turtle.color(cor)
    turtle.pendown()
    turtle.begin_fill()
    # desenha
    
    turtle.forward(lado_1)
    turtle.left(90)
    turtle.forward(lado_2)
    turtle.goto(x,y)
    turtle.end_fill()
    turtle.hideturtle()  

Na segunda parte da pergunta era pedido que usassem a definição anterior como auxiliar para o desenho formado por um número variável de triângulos rectângulos alinhados circularmente e igualmente espaçados. A única dificuldade era controlar a orientação, o que obrigava a saber o espaçamento. É isso que é feito no programa:

def boneco(n, x,y,orienta,cor,menor,maior):
    angulo = 360/n
    for i in range(n):
        tri_rect(x,y,orienta,cor,menor,maior)
        orienta = orienta + angulo

Teste 1 - TP1

Pergunta 1
Em Python tudo são objectos. Os objectos têm atributos que dependem do tipo do objecto. No entanto existem três que todos têm: identidade, valor e tipo. Os objectos estão armazenados num espaço próprio da memória, designado por Espaço dos Objectos. A localização do objecto é a sua identidade, e, nesse local estão a descrição do valor do objecto e do seu tipo. O Espaço de Nomes é o local da memória onde estão guardados os nomes associados aos objectos. A ligação é feita através da identidade. Assim ao fazer a = 5, é criada a associação entre o nome ‘a’ e o objecto 5, cada um a “viver” no respectivo espaço.

Pergunta 2
Uma questão trivial que pedia para usar Python como se de uma vulgar calculadora se tratasse.

import math

def area(n,l):
    return (n * l**2)/(4 * math.tan(math.pi/4))

Pergunta 3
Desenhar um rectângulo é semelhante a desenhar um quadrado, só que agora temos duas medidas para os lados. Tornar o desenho livre da dimensão dos lados, da orientação, da cor, obriga a usar esses elementos como parâmetros e a uma preparação para o desenho antes de concretizar. É isso que faz o código seguinte:

import turtle

def rect(x,y,orienta,cor,menor,maior):
    # inicialização
    turtle.penup()
    turtle.goto(x,y)
    turtle.setheading(orienta)
    turtle.color(cor)
    turtle.pendown()
    turtle.begin_fill()
    # desenha
    for i in range(2):
        turtle.forward(menor)
        turtle.right(90)
        turtle.forward(maior)
        turtle.right(90)
    turtle.end_fill()
    turtle.hideturtle()

Na segunda parte da pergunta era pedido que usassem a definição anterior como auxiliar para o desenho formado por um número variável de rectângulos alinhados circularmente e igualmente espaçados. A única dificuldade era controlar a orientação, o que obrigava a saber o espaçamento. É isso que é feito no programa:

def boneco(n, x,y,orienta,cor,menor,maior):
    angulo = 360/n
    for i in range(n):
        rect(x,y,orienta,cor,menor,maior)
        orienta = orienta + angulo

Livro

Depois de vários anos a ensinar programação em Python resolvi publicar um livro. O texto cobre toda a matéria de IPRP, isto é a parte procedimental da linguagem, mas acrescenta uma parte sobre programação orientada aos objectos e outros aspectos que aprofundam o conhecimento da linguagem.

Quem gostar de aprender a programar numa linguagem que hoje é ensinada nas melhores escolas e usada pelas grandes empresas, tem neste livro uma oportunidade de o fazer de modo completo e em português.

Os benefícios da generalização e da abstracção

Nestas primeiras aulas dissemos que em Python tudo são objectos. Cada objecto tem um conjunto determinado de atributos, como a identidade, o valor e o tipo, e um conjunto de operações em que podem participar. Os atributos num dado instante definem o estado do objecto, enquanto que as operações determinam o seu comportamento.
Podemos usar estes elementos para usar Python como se fosse um vulgar calculadora que me ajuda a saber o peso ideal de uma pessoa do género masculino.

>>> 72.7 * 1.81 - 58 
        73.58700000000002
>>>

Podemos fazer o mesmo para calcular o peso-ideal de uma pessoa do género feminino. E até podemos escrever um único programa que nos permite calcular o peso ideal de qualquer pessoa.

# Definição
def peso_ideal(altura,genero):
    if genero == 'M':
        return round(72.7 * altura - 58,2)
    else:
        return round(62.1 * altura - 44.7,2)
      
# Uso
print(peso_ideal(1.81,'M'))
print(peso_ideal(1.74,'F'))

Este exemplo simples mostra a vantagem de soluções genéricas. Para as conseguir fazemos uso de uma abstracção procedimental, uma definição (def). Neste exemplo os dados são fornecidos ao programa no momento da chamada do programa através dos argumentos da definição, também designados de parâmetros formais, e o resultado é comunicado a quem o solicitou através do comando de regresso (return). Não tem que ser forçosamente assim.

# Definição

def peso_ideal_2():
    altura = float(input('A sua altura sff: '))
    genero = input('O seu género sff [M/F]: ')
    if genero == 'M':
        print(round(72.7 * altura - 58,2))
    else:
        print(round(62.1 * altura - 44.7,2))
    
    
# Uso
peso_ideal_2()

peso_ideal_2()
 

Como se pode ver a grande diferença entre as duas soluções reside no modo como se processa a entrada dos dados a a comunicação do resultado. Agora usamos input para introduzir os dados e print para comunicar o resultado. Neste exemplo, estão presentes o que designamos de instruções, que de um modo geral podem ser agrupadas em dois grandes grupos: destrutivas e de controlo. No primeiro grupo, estão as instruções de atribuição (=), entrada (input) e saída (print). No segundo grupo, as instruções de sequência (;), condicionais (if) e ciclos ou repetições (for). São os blocos construtores dos programas.
Outro exemplo que quer tratámos envolvia desenho de polígonos regulares. Mostrei como se podia passar de um programa muito simples para desenhar um quadrado:

# Definição
def quadrado():
    turtle.forward(50)
    turtle.right(90)
    turtle.forward(50)
    turtle.right(90)
    turtle.forward(50)
    turtle.right(90)
    turtle.forward(50)
    turtle.right(90)
       
# Uso
quadrado()

para outro programa mais completo.

import turtle

# Nova Definição
def vai_para(x,y):
    turtle.penup()
    turtle.goto(x,y)
    turtle.pendown()
    
def quadrado(x,y,orientacao,cor,lado):
    vai_para(x,y)
    turtle.setheading(orientacao)
    turtle.color(cor)
    turtle.begin_fill()
    for i in range(4):
        turtle.forward(lado)
        turtle.right(90)
    turtle.end_fill()
    turtle.hideturtle()
    
# Uso

quadrado(50, -50, 45,'red',50)
turtle.exitonclick()

Completámos a ideia de abstracção ao mostrar como um único programa podia ser usado para desenhar qualquer polígono regular.

import turtle

# Nova Definição
def vai_para(x,y):
    turtle.penup()
    turtle.goto(x,y)
    turtle.pendown()
    
def poligono_reg(num_lados,x,y,orientacao,cor,lado):
    vai_para(x,y)
    turtle.setheading(orientacao)
    turtle.color(cor)
    turtle.begin_fill()
    angulo = 360//num_lados
    for i in range(num_lados):
        turtle.forward(lado)
        turtle.right(angulo)
    turtle.end_fill()
    turtle.hideturtle()
    
# Uso
poligono_reg(7,50, -50, 45,'red',50)
turtle.exitonclick()

A moral desta história é simples: generalizar + abstrair compensa!

Começar de novo

Começar de novo Cá estamos em mais um início de ano lectivo. Para os estreantes quero apenas dizer que neste blogue podem encontrar vários elementos que vos ajudarão na disciplina de IPRP e, assim o espero, a tornarem-se melhores programadores. Para todos os outros bom regresso.

Exame Recurso - P4

Temos uma base de dados, organizada com um dicionário, formada pelo identificador de cada docente (chave) e pelos seus dados profissionais e pessoais (valor). Estes dados estão também guardados num dicionário em que as chaves são os identificadores dos dados pessoais e académicos e os valores, os valores correspondentes. Era-nos pedido a verificação da consistência da base de dados. definida pela identidade das chaves dos dicionários associados a cada docente. Foram vários os erros feitos pelos alunos. Desde usarem à partida como argumento para além da base de dados a lista das chaves, até assumirem que as chaves de um dicionário estão ordenadas, passando por ignorar que os métodos para obter as chaves,os valores ou os items são iteradores.

Uma solução simples para o problema é o que apresentamos a seguir:

def bd_consistente(bd):
    lista_dados_docentes = list(bd.values())
    lista_chaves = []
    for elem in lista_dados_docentes:
        chaves = list(elem.keys())
        chaves.sort()
        lista_chaves.append(chaves)
    for i in range(len(lista_chaves)-1):
        if lista_chaves[i] != lista_chaves[i+1]:
            return False
    return True

if __name__ == '__main__':
    base_dados = {'ecosta':{'nome':'Ernesto','apelido':'Costa'},'lpato':{'nome':'Luís','apelido':'Pato', 'título':'Auxiliar'}, 'aneves':{'nome':'Artur','apelido':'Neves'}}
    print(bd_consistente(base_dados))

Come se pode ver, começamos por guardar em lista_dados_docentes a lista dos dicionários associados a cada docente. De seguida, construímos uma nova lista (lista_chaves) onde guardamos as chaves ordenadas de cada docente. Finalmente, no segundo ciclo, comparamos as chaves ordenadas, terminando mal exista uma caso de diferença.

Teste Final - Pergunta 4

Era pedido um programa em que se somam dois vectores esparsos representados através de dicionários. Um vector esparso é aquele em que a esmagadora maioria dos seus elementos é zero. Usando um dicionário apenas representamos explicitamente os casos diferentes de zero, poupando muito espaço e salvando tempo nas operações. Por exemplo, o vector x = (0,0,0,2,0,0,0,5,0,0) pode ser representado, com economia, pelo dicionário d ={3:2, 7:5, ‘len’:10}. Notar a referência ao comprimento, um parâmetro importante da representação.

Das respostas dadas no teste, quase todos(as) optaram por transformar os dois vectores representados por dicionários em listas, seguido da soma das duas listas, par finalmente depois construir o dicionário resultado. Se pensarmos um pouco, isto é tudo menos boa programação, porque precisamente destrói o que se ganha em usar uma representação baseada em dicionários: espaço e tempo! Mesmo assim, as soluções apresentadas têm muitas deficiências (por exemplo, recurso errado a isdigit() ou a type(x) == int, em vez de isinstance(x,int)). Eis uma solução possível para essa abordagem.

def soma_vec_esparso_b(vec_1, vec_2):
    comp = vec_1['len']
    # Converte dicionários em listas
    list_1 = [vec_1.get(i,0) for  i in range(comp) ]
    list_2 = [vec_2.get(i,0) for  i in range(comp)]
    # soma listas
    list = [list_1[i] + list_2[i] for i in range(comp)]
    # constrói dicionário
    dic = {i: list[i] for i in range(comp) if list[i] > 0}
    dic['len'] = comp
    return dic

Fazemos uso de listas e dicionários por compreensão, que nos permite um código curto.Claro que podem ser substituídas por ciclos normais.

Então qual seria a solução baseada em dicionários? Como vão ver, simples e curta.

def soma_vec_esparso(vec_1, vec_2):
    vec_3 = {}
    vec_3.update(vec_2)
    for ch1,val1 in vec_1.items():
        if ch1 != 'len': # isinstance(ch1,int)
            vec_3[ch1] = val1 + vec_3.get(ch1,0)
    return vec_3

A ideia é começar por copiar um dos dicionários para a solução usando o método update ( isso inclui a chave ‘len’), e depois verificar os elementos relevantes (isto é, diferentes de ‘len’) do outro vector efectuando a soma. Em comentário, mostramos que podemos fazer o teste para saber se é ‘len’ ou um número de um modo mais geral.