Teste # 2 - TP2

P2

O problema: Duas palavra dizem-se deslocadas de n posições se se puder obter os caracteres de uma deslocando cada caracter da outra n posições no alfabeto. Por exemplo, HAL e IBM são palavras deslocadas com uma distância de 1. Escreva um programa que determina se duas palavras são deslocadas ou não de n.

A solução. Definimos o alfabeto e depois procuramos as posições no alfabeto dos caracteres presentes nas duas palavras. É preciso que todas as diferenças tenham o mesmo valor, igual a n.

view sourceprint?

01.def deslocadas(pal_1, pal_2,n):

02.    """

03.    pal_1 é pal_2 quand se deslocam todos os caracteres de n posições?

04.    Exemplo: IBM,HAL e n = 1.

05.    """

06.    alfabeto ='abcdefghijklmnopqrstuvwxyz'

07.    for i in range(len(pal_1)):

08.        indice_1 = alfabeto.find(pal_1[i])

09.        indice_2 = alfabeto.find(pal_2[i])

10.        if (indice_1 - indice_2) != n:

11.            return False

12.    return True

Notar que a ordem porque efectuamos a comparação dos índices é relevante. Se n for positivo a primeira palavra deve estar à esquerda da segunda, se for negativo é o contrário. Se quisermos não nos preocupar com a ordem e usar sempre valores positivos de n só temos que acrescentar:

view sourceprint?

1.def desloc(p_1,p_2,n):

2.    return (deslocadas(p_1, p_2,n) or deslocadas(p_2, p_1,n)

P3

O problema: Suponha que tem duas imagens a preto e branco e pretende saber se uma delas, a mais pequena,ocorre na imagem maior. Escreva um programa que resolve esta questão.

A solução. O problema desdobra-se em dois sub-problemas: saber se a operação é possível e, no caso afirmativo, calcular a ocorrência do canto superior esquerdo. Para simplificar a questão criámos um pequeno programa auxiliar que determina se duas imagens são iguais ou não.

view sourceprint?

01.def ocorre(img_1, img_2):

02.    # possivel

03.    n_linhas_1 = len(img_1)

04.    n_colunas_1 = len(img_1[0])

05.    n_linhas_2 = len(img_2)

06.    n_colunas_2 = len(img_2[0])

07.    possivel = (n_linhas_1 <= n_linhas_2) and (n_colunas_1 <= n_colunas_2)

08.    # verifica

09.    for l in range(n_linhas_2 - n_linhas_1 + 1):

10.        for c in range(n_colunas_2 - n_colunas_1 + 1):

11.            # verifica se imagem 1 ocorre a partir da posição (l,c)

12.            if igual(img_1,img_2,l,c):

13.                return (l,c)

14.    return (-1,-1)

15. 

16.def igual(img_1,img_2,l,c):

17.    for i in range(len(img_1)):

18.        for j in range(len(img_1[0])):

19.            if img_1[i][j] != img_2[l+i][c+j]:

20.                return False

21.    return True

Teste # 2 - TP1

P2

O problema: Um palavra diz-se embebida noutra palavra se os seus caracteres ocorrerem nesta pela mesma ordem, embora não necessariamente de modo consecutivo. Por exemplo, ADIA está embebida em ACADEMIA. Escreva um programa que dadas duas palavras, determina se uma delas está embebida na outra.

A solução. Não há grande mistério. Analisamos os caracteres da palavra mais pequena e verificamos se está presente na palavra maior. Para garantir o problema da ordem cada vez que fazemos a pesquisa limitarmos o campo de procura de modo que a posição inicial seja a posição imediatamente à frente da posição onde se encontrou o último caractere. notar que mal um caractere não esteja presente o programa termina com False.

view sourceprint?

01.def embebida(pal_1, pal_2):

02.    """ verifica se pal_1 está embebida em pal_2."""

03.    pos = 0

04.    for car in pal_1:

05.        indice = pal_2.find(car,pos)

06.        if indice == -1:

07.            return False

08.        pos = indice + 1

09.    return True

P3

O problema: Suponha que tem duas imagens a preto e branco e pretende que uma delas, a mais pequena, substitua uma parte da imagem maior. Escreva um programa que dadas as duas imagens e o ponto de inserção efectue a modificação.

A solução. A solução apresentada tem duas partes: uma em que se verifica se a operação é possível, e a segunda em que se processa a alteração. como se pode ver a estratégia consistiu em percorrer a imagem mais pequena e colocar os seus valores no sítio certo da imagem maior.

view sourceprint?

01.def altera_img(img_1, img_2,pos_l, pos_c):

02.    """ altera a imagem 2 com a imagem 1 a partir das posição (pos_l,pos_c)"""

03.    # é possível?

04.    n_linhas_1 = len(img_1)

05.    n_colunas_1 = len(img_1[0])

06.    n_linhas_2 = len(img_2)

07.    n_colunas_2 = len(img_2[0])

08.    possivel = ((pos_l + n_linhas_1) <= n_linhas_2) and ((pos_c + n_colunas_1) <= n_colunas_2)

09.    if possivel:

10.        # modifica

11.        for l in range(n_linhas_1):

12.            for c in range(n_colunas_1):

13.                img_2[pos_l + l][pos_c + c] = img_1[l][c]

14.    return img_2

Variações em torno de vogais

Nas aulas discutimos o problema de escrever um programa que leia um texto e indique para cada vogal a lista das suas ocorrências no texto. Trata-se de um problema em que, naturalmente, se opta por um dicionário para representar o resultado. Assim, para:

view sourceprint?

1.txt = 'ernesto ui ui cuidado com os alunos’

o resultado deve ser:

view sourceprint?

1.{'e': [0, 3], 'o': [6, 20, 23, 26, 33], 'u': [8, 11, 15, 31], 'i': [9, 12, 16], 'a': [18, 29]}

A solução evidente segue o padrão ciclo-acumulador. Aqui o acumulador é o dicionário que vai sendo actualizado à medida que percorremos o texto caractere a caractere.

view sourceprint?

01.def vogais_x(texto):

02.    dicio = dict()

03.    for i in range(len(texto)):

04.        if texto[i] == 'a':

05.            dicio['a'] = dicio.get('a',[]) + [i]

06.        elif texto[i] == 'e':

07.            dicio['e'] = dicio.get('e',[]) + [i]

08.        elif texto[i] == 'i':

09.            dicio['i'] = dicio.get('i',[]) + [i]

10.        elif texto[i] == 'o':

11.            dicio['o'] = dicio.get('o',[]) + [i]

12.        elif texto[i] == 'u':

13.            dicio['u'] = dicio.get('u',[]) + [i] 

14.        else:

15.            continue

16.    return dicio

Todos concordaremos que é uma solução feia. Todos aqueles ifs podem ser facilmente removidos. Por outro lado, sabemos que vamos precisar não apenas das posições mas também dos caracteres, pelo que nos interessa percorrer o texto obtendo estes dois elementos. Daí uma nova versão:

view sourceprint?

1.def vogais_y(texto):

2.    vogais ='aeiou'

3.    dicio = dict()

4.    for i,car in enumerate(texto):

5.        if texto[i] in vogais:

6.            dicio[car] = dicio.get(car,[]) + [i]

7.    return dicio

Estas soluções constroem o dicionário de modo incremental. No entanto, nós sabemos quais são as chaves do dicionário, e sabemos ainda que nunca mudam. Daí , a possibilidade de criar inicialmente o dicionário com as posições todas iguais a listas vazias, recorrendo ao método fromkeys. Como consequência deixamos de necessitar do uso do método get.

view sourceprint?

1.def vogais(texto):

2.    vogais ='aeiou'

3.    dicio = dict.fromkeys(vogais, [])

4.    for i,car in enumerate(texto):

5.        if car in vogais:

6.            dicio[car] = dicio[car] + [i]

7.    return dicio 

O leitor atento dirá que ainda se pode ter uma solução mais elegante usando uma atribuição aumentada: +=.

view sourceprint?

1.def vogais_z(texto):

2.    vogais ='aeiou'

3.    dicio = dict.fromkeys(vogais, [])

4.    for i,car in enumerate(texto):

5.        if car in vogais:

6.            dicio[car] += [i] # <———

7.    return dicio

No entanto, se correr este código verificará que não funciona. Ou melhor, corre mas apresenta o resultado errado:

view sourceprint?

1.{'a': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'e': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'i': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'o': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'u': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33]}

A explicação para o resultado (todas as vogais ocorrem nas mesmas posições, igual à união das posições de cada uma…) é simples: a construção do dicionário usando fromkeys faz com que os valores iniciais sejam o mesmo objecto (partilha de memória) e a instrução += não constrói objectos novos. Uma solução consiste em alterar a construção do dicionário inicial, usando dicionários por compreensão:

view sourceprint?

1.def vogais_e(texto):

2.    vogais ='aeiou'

3.    dicio = {vog:[] for vog in 'aeiou'}

4.    for i,car in enumerate(texto):

5.        if car in vogais:

6.            dicio[car] += [i]

7.    return dicio

E pronto. Espero que tenha entendido. Ah, já agora, ainda outra solução….

view sourceprint?

1.def vogais_d(texto):

2.    vogais ='aeiou'

3.    dicio = {vog:[] for vog in 'aeiou'}

4.    for i,car in enumerate(texto):

5.        if car in vogais:

6.            dicio[car].append(i)

7.    return dicio