Um problema, várias soluções

Sempre que estamos diante de um problema novo a melhor maneira de o resolver é tentar identificar um modelo de solução por analogia com problemas antigos já resolvidos. Para além disso, quando os problemas têm uma certa complexidade, pois necessitamos fazer muitas coisas e sujeitos a diferentes restrições, nada melhor do que dividir o problema em sub-problemas mais simples e/ou tentar resolver primeiro uma versão mais simples que depois completamos. Isto são princípios que temos vindo a explorar ao longo das aulas. Também é um facto que conhecendo melhor a linguagem de programação podemos encontrar variantes para a nossa solução inicial, eventualmente mais eficientes. Vamos ver este último aspecto com exemplos simples das aulas.

Contar quantos elementos de uma lista são menores do que um elemento de referência.

A solução trivial passa por percorrer (recorrendo a um ciclo) a lista e ir contando sempre que aparecer um elemento menor (uso de um acumulador. Mas mesmo esta situação pode ser feita de diferentes maneiras: percorrer a lista por índice ou percorrer por conteúdo:

view sourceprint?

01.def conta_menores1(num,lista_num):

02.    acum = 0

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

04.        if lista_num[i] < num:

05.            acum += 1

06.    return acum

07. 

08. 

09.def conta_menores2(num,lista_num):

10.    acum = 0

11.    for i in lista_num:

12.        if i < num:

13.            acum += 1

14.    return acum

A segunda versão é a preferível do ponto de vista da eficiência, sendo que, na nossa opinião, é mais clara. Quem conhecer o conceito de listas por compreensão pode sugerir outra solução:

view sourceprint?

1.def conta_menores3(num, lista_num):

2.    return sum([ 1 for i in lista_num if i < num])

Será que podemos arranjar ainda outra solução. Na aula um aluno sugeriu uma alternativa muito interessante:

view sourceprint?

1.def conta_menores4(num, lista_num):

2.    lista_num.sort()

3.    return lista_num.index(num)

Nesta solução ordenamos a lista e depois calculamos a posição do número da lista que vai ser igual ao número de elementos menores. Mas esta solução tem um problema: só funciona se o número de referência estiver na lista. Consegue perceber porquê?? Tratemos agora de uma variante deste problema.

Listagem dos menores

Podemos ter soluções semelhantes às anteriores. O que muda é a natureza do acumulador (agora terá que ser um contentor, tuplo ou lista.

view sourceprint?

01.def lista_menores1(num,lista_num):

02.    acum = []

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

04.        if lista_num[i] < num:

05.            acum += [lista_num[i]]

06.    return acum

07. 

08. 

09.def lista_menores2(num,lista_num):

10.    acum = []

11.    for i in lista_num:

12.        if i < num:

13.            acum += [i]

14.    return acum

Aqui podemos variar a forma de juntar o elemento à lista, recorrendo ao método append em substituição da operação de concatenação:

view sourceprint?

01.def lista_menores3(num,lista_num):

02.    acum = []

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

04.        if lista_num[i] < num:

05.            acum.append(lista_num[i])

06.    return acum

07. 

08.def lista_menores4(num,lista_num):

09.    acum = []

10.    for i in lista_num:

11.        if i < num:

12.            acum.append(i)

13.    return acum

E uma vez mais a solução com listas por compreensão (a nossa preferida):

view sourceprint?

1.def lista_menores5(num, lista_num):

2.    return [i for i in lista_num if i < num]

Será que a sugestão do nosso aluno também se aplica aqui (no pressuposto de que o elemento está na lista)? Claro:

view sourceprint?

1.def lista_menores4(num,lista_num):

2.    lista_num.sort()

3.    return lista_num[:lista_num.index(num)]

Soma cumulativa

Agora a questão é a de dada uma lista construir uma nova lista em que na posição i vamos ter a soma dos elementos da lista original entre as posições inicial e i (inclusivé). A solução mais simples baseia-se no recurso ao padrão ciclo-acumulador que contem no interior do ciclo outro padrão ciclo-acumulador. Este último é usado para o cálculo da soma cumulativa.

view sourceprint?

01.def soma_cumulativa(lista):

02.    acum = []

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

04.        # soma de 0 a i

05.        soma = 0

06.        for j in range(i+1):

07.            soma += lista[j]

08.        # junta soma ao acumulador

09.        acum.append(soma)

10.    return acum

Conhecendo a existência da função sum podemos simplificar a nossa primeira solução:

view sourceprint?

1.def soma_cumulativa2(lista):

2.    acum = []

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

4.        # soma de 0 a i

5.        soma = sum(lista[:i+1])

6.        # junta soma ao acumulador

7.        acum.append(soma)

8.    return acum

E, também aqui, o recurso a listas por compreensão da origem a um programa mais curto:

view sourceprint?

1.def soma_cumulativa3(lista):

2.    return [sum(lista[:i+1]) for i in range(len(lista))]

Será que podemos fazer melhor? Podemos. Uma pequena reflexão sobre o problema mostra que existe uma relação simples entre duas somas cumulativas consecutivas: basta somar à soma anterior (de 0 a i) o valor do elemento na posição (i+1):

view sourceprint?

1.def soma_cumulativa4(lista):

2.    acum = [lista[0]]

3.    for i in lista[1:]:

4.        acum.append(acum[-1]+i)

5.    return acum

E pronto. Esperamos que tenham ficado com uma ideia de que em programação mesmo os problemas mais simples podem ter várias alternativas.