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:

def conta_menores1(num,lista_num):
    acum = 0
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum += 1
    return acum


def conta_menores2(num,lista_num):
    acum = 0
    for i in lista_num:
        if i < num:
            acum += 1
    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:

def conta_menores3(num, lista_num):
    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:

def conta_menores4(num, lista_num):
    lista_num.sort()
    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.

def lista_menores1(num,lista_num):
    acum = []
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum += [lista_num[i]]
    return acum


def lista_menores2(num,lista_num):
    acum = []
    for i in lista_num:
        if i < num:
            acum += [i]
    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:

def lista_menores3(num,lista_num):
    acum = []
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum.append(lista_num[i])
    return acum

def lista_menores4(num,lista_num):
    acum = []
    for i in lista_num:
        if i < num:
            acum.append(i)
    return acum

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

def lista_menores5(num, lista_num):
    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:

def lista_menores4(num,lista_num):
    lista_num.sort()
    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.

def soma_cumulativa(lista):
    acum = []
    for i in range(len(lista)):
        # soma de 0 a i
        soma = 0
        for j in range(i+1):
            soma += lista[j]
        # junta soma ao acumulador
        acum.append(soma)
    return acum 

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

def soma_cumulativa2(lista):
    acum = []
    for i in range(len(lista)):
        # soma de 0 a i
        soma = sum(lista[:i+1])
        # junta soma ao acumulador
        acum.append(soma)
    return acum 

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

def soma_cumulativa3(lista):
    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):

def soma_cumulativa4(lista):
    acum = [lista[0]]
    for i in lista[1:]:
        acum.append(acum[-1]+i)
    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.