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.

view sourceprint?

1.def tira_repete_1(cadeia):

2.    acum = ''

3.    for car in cadeia:

4.        if car not in acum:

5.            acum = acum + car

6.    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:

view sourceprint?

01.def tira_repete_2(cadeia):

02.    acum = ''

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

04.        if cadeia[i] not in cadeia[i+1:]:

05.            acum = acum + cadeia[i]

06.    return acum

07. 

08.def tira_repete_3(cadeia):

09.    acum = ''

10.    for i in range(len(cadeia)):

11.        if cadeia.find(cadeia[i],i+1) == -1:

12.            acum = acum + cadeia[i]

13.    return acum

14. 

15.def tira_repete_4(cadeia):

16.    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:

view sourceprint?

1.def prod_esc(vec1,vec2):

2.    acum = 0

3.    for i in range(len(vec1)):

4.        acum = acum + (vec1[i] * vec2[i])

5.    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:

view sourceprint?

1.def prod_esc(vec1,vec2):

2.    dim = min(len(vec1), len(vec2))

3.    acum = 0

4.    for i in range(dim):

5.        acum = acum + (vec1[i] * vec2[i])

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

view sourceprint?

1.def fact(n):

2.    acum = 1

3.    for i in range(1,n+1):

4.        acum = acum * i

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