Importa-se de repetir?

Importa-se de repetir? Aprendemos nas aulas que quando temos um conjunto de instruções que se repete um certo número de vezes recorremos a uma instrução de controlo repetitiva. Mas concretamente, temos vindo a exercitar para estas situações o uso do ciclo for. Nas sua versão mais simples toma a forma de:

for _nome> in _iterável:
   _instruções

A semântica desta construção é fácil de perceber. Enquanto existirem elementos em iterável vai buscar um e associa-o ao nome. De seguida, executa as instruções num ambiente com a associação nome elemento definida. Vejamos exemplos concretos.

>>> for i in range(3):
...     print(i)
... 
0
1
2
>>> for i in range(len('abc')):
...     print('abc'[i])
... 
a
b
c
>>> for car in 'abc':
...     print(car)
... 
a
b
c
>>> 

No primeiro e segundo exemplos o nome i funciona na prática como um contador que toma os sucessivos valores de 0,1 e 2. No terceiro exemplo, vamos extraindo um a um os elementos da cadeia de caracteres, primeiro ‘a’, depois ‘b’ e por último ‘c’, que vão ficando associados ao nome car. Este exemplo mostra ainda as duas formas de percorrer os elementos de uma cadeia de caracteres. O facto de estarmos a lidar com sequências faz com que os elementos sejam extraídos pela ordem em que se encontram na sequência.

Nota que pode ser saltada. Existem outros objectos iteráveis de que falaremos ao longo do curso, como os listas, os dicionários ou os conjuntos que também podem ser usados na parte do cabeçalho dos ciclos. No caso dos dicionários e dos conjuntos, porque não existe nenhuma ordem apenas podemos garantir que cada vez que se percorre o ciclo há um elemento que é extraído do objecto. É isso que define um objecto como sendo iterável: a possibilidade de ir fornecendo um a um os seus elementos.

Como já dissemos os ciclos são usados na resolução de qualquer problema minimamente complexo. Nestes casos os ciclos são usados num contexto mais vasto que faz emergir um padrão de utilização: ir construindo a solução final do nosso problema a partir de uma solução inicial que vai progredindo para a solução desejada cada vez que o ciclo é executado. Vamos aos exemplos.

Suponhamos que não sabemos que existe uma operação pré-definida para determinar o elemento máximo de uma cadeia de caracteres pelo que vamos implementar o respectivo programa. É desde logo claro que vamos ter que percorrer toda a cadeia. Por outro lado, estando interessados no elemento maior interessa-nos fazer a procura pelo conteúdo da cadeia. Assim sendo vamos ter um esqueleto de solução com o seguinte aspecto:

def maximo(cadeia):
      # inicialização
      for car in cadeia:
 # Transformação
      return elem_max

Mas falta o essencial. Vamos pensar. Admitamos que num dado momento da consulta da nossa cadeia sabemos qual é o maior elemento de entre os analisados. O que fazer então? Bom, consultamos o primeiro elemento dos ainda não analisados (lembre-se há uma ordem nas cadeias de caracteres!) e procuramos saber se é maior do que o máximo actual. Em função da resposta actualizamos, ou não, o máximo. A figura ilustra a situação.

 Então podemos melhorar a nossa solução básica:

def maximo(cadeia):
    # inicialização
    for car in cadeia:
        # elem_max é o maior dos elementos já vistos
        if elem_max < car:
            elem_max = car
    return elem_max

Uma das características do ciclo é que existe um propriedade que é sempre verdadeira quando vamos iniciar as instruções dentro do ciclo. Chama-se um invariante ... de ciclo. No nosso exemplo o invariante é: elem_max é o maior dos elementos já vistos! A inicialização do ciclo é feita por forma a tornar logo na primeira vez verdadeiro o invariante e daí a solução:

def maximo(cadeia):
    # inicialização
    elem_max = cadeia[0]
    for car in cadeia:
        # elem_max é o maior dos elementos já vistos
        if elem_max < car:
            elem_max = car
    return elem_max

Analisemos agora a solução. Em primeiro lugar só funciona se a cadeia tiver elementos, caso contrário dá erro. Por outro lado, tem uma ineficiência pois o primeiro elemento é analisado dentro do ciclo quando é desnecessário. Estas duas observações levam à solução final seguinte.

def maximo(cadeia):
    """Determina o máximo de uma cadeia de caracteres não vazia."""
    # inicialização
    elem_max = cadeia[0]
    for car in cadeia[1:]:
        # elem_max é o maior dos elementos já vistos
        if elem_max < car:
            elem_max = car
    return elem_max

Para consolidar a ideia passemos a um problema diferente: dada uma cadeia de caracteres fabricar a cadeia inversa. Uma vez mais vamos ter que percorrer toda a cadeia e também aqui são os elementos que nos interessam. De novo vamos partir de uma solução parcial que aproximamos passo a passo do resultado. Vamos pensar de novo indutivamente, procurando um invariante de ciclo e uma transformação que nos aproxime progressivamente da solução pretendida. Façamos o desenho que traduz a nossa estratégia. Baseia-se na ideia simples de que já temos uma cadeia que contém os caracteres invertidos de uma parte inicial da cadeia de que partimos.


Obtida uma solução parcial vamos buscar o próximo elemento à cadeia original, o primeiro ainda não invertido, que é colocado na sua posição de destino. Como podemos inicializar a solução parcial antes de entrar no ciclo? Basta considerar a cadeia vazia. E qual o invariante do ciclo? Na etapa de ordem N a solução parcial contem os primeiros (N-1) caracteres por ordem inversa. E agora o código.

def inverte(cadeia):
    """Inverte uma cadeia de carateres."""
    # Inicialização
    solucao = ''
    for car in cadeia:
        # Na etapa N solucao tem os primeiros (N-1) caracteres da cadeia por ordem inversa."""
        solucao = car + solucao
    return solucao

Comentário. Esta solução funciona mesmo com cadeias vazias.

Terceiro exemplo: Determinar se um caractere ocorre numa cadeia. Devolve o índice do elemento na cadeia caso exista, -1 caso não ocorra. Vamos fazer agora ao contrário, apresentando desde já a solução.

def procura(car, cadeia):
    """Procura car em cadeia. Devolve  o índice do caracter na cadeia, -1 se não encontrou."""
    enc = -1
    for i in range(len(cadeia)):
        if car == cadeia[i]:
            enc = i
    return enc

Algumas notas. Como pretendemos o índice, percorremos a cadeia por posição e não por conteúdo. Funciona mesmo no caso de cadeias vazias. No caso de existir mais do que uma ocorrência devolve o índice da última. Vermos ao longo do curso como se poderia resolver a questão de sair do ciclo mal encontre uma ocorrência do caracter. Questão: qual será o invariante? Pense um pouco, vai ver que chega à conclusão: no início da etapa i, o nome enc está associado ao índice ao índice a última ocorrência do car na sub-cadeia formada pelos primeiros (i-i) caracteres.

Resumindo. Existe um modo de resolver problemas que envolve ciclos e pensamento indutivo. Os ciclos têm três partes: inicialização, controlo e transformação. O pensamento indutivo significa que assumimos uma solução parcial que cada vez que o ciclo é percorrido se aproxima da solução pretendida. Descobrir o invariante do ciclo significa (quase) resolver o problema. A inicialização é a definição de valores que tornam o invariante verdadeiro à entrada do ciclo. Agora divirta-se!