segunda-feira, 31 de outubro de 2011

Problema 5.6

Para resolver o problema de deslizar n posições para a esquerda ou para a direita vamos abordar a questão por etapas. Admitindo que sabemos deslizar isoladamente n elementos para a direita ou para a esquerda a solução gloabla é fácil de escrever.


def desliza_n_d_e(n, lista):
"""Desliza n posições para a direita ou esquerda,de modo circular, os elementos de uma lista."""
if n > 0:
return desliza_d_n(n,lista)
else:
return desliza_e_n(abs(n), lista)

Temos agora que resolver cada um dos dois sub-problemas quer introduzimos. Eles são muito semelhantes. Comecemos pelo deslizar para a direita. A silução consiste em dividir a lista em dois pedaços, em função do valor de n. Guardamos a parte final numa variável auxiliar e depois acrescentamos à sua frente a parte inicial da lista de que partimos. A figura ilustra a estratégia.




O programa tem apenas que ter o cuidado de testar se a lista é vazia ou não.

def desliza_d_n(n, lista):
"""Desliza n posições para a direita,de modo circular, os elementos de uma lista."""
if lista == []:
return lista
else:
aux = lista[-n:]
aux.extend(lista[:len(lista) - n])
return aux



Para o deslizar pata a esquerda usamos o mesmo mecanismo.

def desliza_e_n(n, lista):
"""Desliza n posições para a esquerda,de modo circular, os elementos de uma lista."""
if lista == []:
return lista
else:
aux = lista[n:]
aux.extend(lista[:n])
return aux


Como é lógico podíamos ter resolvido o problema só com uma função, cobrindo os dois casos. Fica para o leitor resolver.

Problema 5.2

Estes problemas são muito elementares e a sua função é apenas obrigar a conhecer as operações que podemos fazer sobre listas. Vamos apenas apresentar a solução para o problema de calcular e devolver a soma de todos os valores (números) contidos numa lista. Permite-nos ilustrar os diferentes modos de iterar com listas e, ainda, o que podemos fazer quando conhecemos melhor a linguagem.

Pecorrer por índice

def idades_4a(lista):
soma=0
for indice in range(len(lista)):
soma = soma + lista[indice]
return soma

Perocorrer pelo conteúdo

def idades_4b(lista):
soma = 0
for elem in lista:
soma = soma + elem
return soma

Recurso à função sum

def idades_4c(lista):
return sum(lista)

Problema 5.1

Implementar os métodos referidos pode ser feito de várias maneiras. Aqui apenas apresento a maneira mais básica. Como tempo aprenderão a fazer de outro modo recorrendo a outras construções da linguagem.

Contagem


def my_count(item, lista):
""" Número de ocorrências do item na lista."""
conta = 0
for elem in lista:
if elem == item:
conta = conta + 1
return conta

Inversão

def my_reverse(lista):
"""Inverte os elementos de uma lista. Cria uma cópia."""
return lista[::-1]

# - variante
def my_reverse_b(lista):
"""Inverte os elementos de uma lista. Cria uma cópia."""
aux = []
for elem in lista:
aux = [elem] + aux
return aux

Procura

def my_find(item,lista):
for i in range(len(lista)):
if lista[i] == item:
return i
return -1

# Variante
def my_find_b(item,lista):
for ind, elem in enumerate(lista):
if elem == item:
return ind
return -1

Insere

def my_insert(elem, pos,lista):
""" Insere o elem na posição. Assume posição correcta."""
return lista[:pos] + [elem] + lista[pos:]

domingo, 30 de outubro de 2011

Problema 4.7

O facto de este ser o último problema da folha não significa que seja o mais difícil. com efeito, e até em função do que já vimos no problema 4.6 a solução apenas depende do correcto uso do módulo random e de saber como ir retirando caracteres ao alfabeto de modo aleatório.

def cria_chave():
"""Devolve uma chave para encriptar mensagens. Constrói uma permutação."""
alfabeto = 'abcdefghijklmnopqrstuvwxyz '
chave = ''
while alfabeto:
# escolhe próximo caracter
indice = random.randint(0,len(alfabeto)-1)
car = alfabeto[indice]
# actualiza chave
chave = chave + car
# actualiza alfabeto
alfabeto = alfabeto.replace(car,'')
return chave

Problema 4.6

Este problema obriga a alguns cuidados. Mas também é um pretexto para percebermos como podemos construir um programa por aproximações sucessivas, não tentando resolver tudo de uma só vez.

De acordo com o algoritmo dado no enunciado uma solução possível para o nosso problema poderá ser:

def cria_chave(palavra_chave):
"""Gera uma chave a partir de uma palavra de passe."""
alfabeto = 'abcdefghijklmnopqrstuvwxyz '
# retira duplicações da palavra chave
palavra_chave = retira_dup(palavra_chave)
# divide em duas partes
ultimo_car = palavra_chave[-1]
indice = alfabeto.find(ultimo_car)
antes = alfabeto[:indice]
depois = alfabeto[indice+1:]
# retira caracteres da palavra chave
antes = retira_car(palavra_chave, antes)
depois = retira_car(palavra_chave, depois)
# junta tudo
chave = palavra_chave + depois + antes
return chave

Se olharmos para os comentários torna-se claro que o algoritmo foi correctamente implementado. Claro, que isto só é verdade se as duas funções auxiliares, retira_dup e retira_car, funcionarem bem. É disso que vamos agora tratar. Comecemos pelo problema de retirar os duplicados.

def retira_dup(cadeia):
"""Retira caracteres duplicados na cadeia."""
nova_cadeia = ''
for car in cadeia:
if car not in nova_cadeia:
nova_cadeia = nova_cadeia + car
return nova_cadeia

Esta solução, constrói uma nova cadeia, percorrendo os elementos da cadeia antiga uma a um, e só introduzindo os caracteres caso não provoquem uma duplicação.

Uma alternativa é o programa seguinte.

def retira_dup_2(cadeia):
"""Retira caracteres duplicados na cadeia."""
nova_cadeia = ''
for ind, car in enumerate(cadeia):
if car not in cadeia[ind+1:]:
nova_cadeia = nova_cadeia + car
return nova_cadeia

Aqui fazemos uso da função enumerate que nos permite percorrer a cadeia simultaneamente pela índices e pelo conteúdo. Veja-se como no teste dentro do if determinamos se um caractere é ou não repetido.

Agora a parte de retirar carateres de um texto.

def retira_car(caracteres, texto):
"""retira do texto os caracteres."""
novo_texto = ''
for car in texto:
if car not in caracteres:
novo_texto = novo_texto + car
return novo_texto

Ainda e sempre a mesma ideia: percorrer o texto (ciclo), e sempre que o caractere em análise não pertencer aos caracteres proibidos ele é adicionado (acumulador). A contagem é implícita.

A lição que podemos tirar deste exemplo é a de que vale a pena usar mecanismos de abstracção (neste caso as duas funções auxiliares) para melhor dominar a complexidade da busca da solução para o nosso problema.

Problema 4.2

O problema do cálculo do valor numérico associado a um nome formado por uma única palavra não levanta dificuldades de maior. O padrão habitual -- ciclo, contador e acumulador, chega para resolver a questão. Devido à natureza do problema vamos percorrer a cadeia de caracteres pelo seu conteúdo, pelo que a contagem é implícita. Atente-se no modo como conseguimos estabelecer a relação entre cada caractere e o seu valor numérico. Só precisamos saber o que faz a função ord e não qual o valor no código ASCII associado a cada caractere.
def valor_numerico(nome):
""" Calcula o valor numérico de um nome. 'a' = 1, ..., 'z' = 26."""
valor = 0
for car in nome:
valor = valor + (ord(car) - ord('a') + 1)
return valor

segunda-feira, 24 de outubro de 2011

Este problema é muito semelhante ao 3.7. Agora trata-se de desenhar quadrados concêntricos. Ao contrário do exemplo anterior, agora o que muda é a posição inicial já que a orientação se mantém a mesma. É preciso saber no início o incremento do lado a cada repetição.




def quad_concent(n,lado,d):
"""Desenha n quadrados concêntricos.

"""
x0 = xcor()
y0 = ycor()
for i in range(n):
quad(lado+i*2*d, x0-i*d, y0+i*d, 0)



A solução apresentada não é a única. O leitor é convidado a encontrar a sua abordagem e a compará-la com a apresentada.