Para comentar a resposta do Rodrigo, eu dividirei minha contribuição em três partes, com (1) um comentário geral, (2) alguns específicos e (3) uma alternativa de resposta.
1. Comentários gerais:
A resposta oferecida é bastante intuitiva, bem estruturada e não encontrei uma forma mais direta de resolver o problema. Se entendi corretamente o objetivo da função proposta, o que queremos é uma função que retorne o primeiro número triangular com pelo menos n divisores. Ao trabalhar com ela, no entanto, notei que não se encontra o resultado esperado para todos os valores de n. Pelo que fui capaz de diagnosticar, a resposta é adequada na maioria dos casos (inclusive quando n = 500, que é o que o exercício pede) porém em outros não, note:
Vamos considerar o primeiro caso em que há divergência. Quando n = 3, o primeiro número triangular com ao menos 3 divisores é 6:
D(1): 1
D(3): 1, 3
D(6): 1, 2, 3, 6
A função retorna 3. Isso acontece pois o while loop é interrompido no 3. Nesse estágio, a função avalia se “len(divisores) < n // 2”, em que o lado esquerdo da desigualdade corresponde ao tamanho da lista que contém metade dos divisores do número triangular em questão. No caso do 3, temos "len(divisores) = 1". Assim, seu comprimento é 1. Ao avaliar a sentença “len(divisores) < n // 2”, portanto, temos 1 < 1, o que, por ser falso, interrompe o loop. A resposta retornada é então 3. Para resolver, podemos utilizar a divisão convencional (/) ao invés da parte inteira (floor division, //). Dessa forma, a desigualdade analisada pelo loop passará a ser 1 < 1.5, que por ser verdadeira, dará continuidade ao loop. No entanto, ao fazer isso, uma resposta que estava correta antes passa a ficar incorreta agora (n = 1), além da diferença quando n = 10 ainda permanecer, note:
A primeira inconsistência (n = 1) surge pois, na primeira vez em que o loop roda, "len(divisores)" é igual a 0 e n/2 é igual 0.5. Assim, o while loop não é interrompido e o número triangular é atualizado para o seguinte (isto é, 3). Uma maneira mais simples de corrigir isso consiste em se criar uma exceção:
if n == 0 or n == 1:
return 1
Já a segunda inconsistência (n = 10) acontece devido a uma exceção que poucas vezes aparece, mas que deve ser considerada no código: nem sempre a lista retornada pela primeira função conterá metade dos divisores do número. Isso acontecerá particularmente naqueles casos em que o argumento avaliado tiver uma raiz quadrada inteira, como o 36, o que fará com que o número de divisores seja ímpar.
D(36): 1, 2, 3, 4, 6, 9, 12, 18, 36
encontra_divisores(36) = [1, 2, 3, 4, 5, 6]
Nesses casos, o loop deve continuar pois "len(divisores)" não terá metade do tamanho da lista de divisores de 36, mas sim a metade + 1. Por exemplo, se n for igual a 10 e não incluirmos essa exceção, a resposta será 36 pois "len(divisores) = 5" e "n/2 = 5". Mas note que o número de divisores de 36 não é 10, mas sim 9 – não podemos parar o loop aqui. Caso contrário – se a raiz não for inteira, o que representa a maioria dos casos – o loop é interrompido. Essa exceção só volta a se repetir no 48º número triangular (1225, cuja raiz é 35). Ela não interfere os demais resultados, sendo por isso o código original retorna a resposta correta quando n = 500. Para tratar tal exceção, proponho a seguinte estrutura:
while len(divisores) <= n / 2:
if len(divisores) == n / 2 and divisores[-1] != np.sqrt(soma):
return soma
else:
soma = soma + i
i = i + 1
divisores = encontra_divisores_1(soma)
return soma
Nela, definimos uma regra de parada do loop ao avaliar exatamente os casos com raiz não-inteira, que são a maioria. No entanto, se o último número da lista de divisores (indicado por "divisores[-1]") for igual à raiz quadrada do número triangular, permitimos o loop continuar rodando. Assim, quando n = 10, teremos o triangular 120.
2. Comentários específicos
Como ressaltei, a solução oferecida é bastante intuitiva e, ao meu entendimento, está bem estruturada. Alguns comentários bastante pontuais:
1. Na função "encontra_divisores", ao criar a exceção para quando x for igual a 1, seria interessante que a função retornasse o objeto lista
return [1]
ao invés do inteiro 1, apenas para que se mantenha o padrão do restante da função, que é sempre o de retornar uma lista. Caso contrário, se levarmos um inteiro para a função seguinte – que utiliza o comando len – podemos obter erro, já que esse comando é para listas, tuples, dicionários... mas não para números inteiros.
2. No while loop da função "encontra_triangulares", não me pareceu ser necessário declarar o objeto "divisores = [ ]" dentro do *loop*. Declará-lo no começo da função parece ser suficiente.
3. Resposta alternativa
# Contribuições Lucas Lourenço:
import numpy as np
def encontra_divisores_1(x):
if (x == 0):
return None
elif(x==1):
return [1]
else:
os_divisores = []
contador = 1
sqrtx = np.floor(x**0.5)
while contador <= sqrtx:
if x % contador == 0:
os_divisores.append(contador)
contador += 1
return(os_divisores)
def encontra_triangulares_1(n):
soma = 1
i = 2
divisores = []
if n == 0 or n == 1:
return 1
else:
while len(divisores) <= n / 2:
if len(divisores) == n / 2 and divisores[-1] != np.sqrt(soma):
return soma
else:
soma = soma + i
i = i + 1
divisores = encontra_divisores_1(soma)
return soma
Para gerar as tabelas comparativas da parte 1:
for i in range (1,31):
string=""
if encontra_triangulares(i) != encontra_triangulares_1(i):
string="*"
print("{0: ^10d} | {1:^20d} | {2:^20d} | {3: ^10s}".format(i,encontra_triangulares(i),encontra_triangulares_1(i),string))
Quanto à eficiência, a resposta mantém a mesma estrutura do código original e, portanto, não há ganho de eficiência. Como não pensei em nenhuma solução que economize linhas ou simplifique as funções, deixo aqui o espaço aberto para que o Rodrigo, o professor e os demais colegas possam contribuir. Fiquem a vontade também para apontarem qualquer imprecisão ou deslize no meu comentário.