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.).