J'essaie de résoudre le Projet Hackerrank Euler Problème # 14 A> (séquence la plus longue de collatz) utilisant Python 3. Voici mon implémentation. Terminated due to timeout
4 Réponses :
Voici mon implémentation (pour la question spécifiquement sur le site Web du projet Euler):
num = 1
limit = int(input())
seq_list = []
while num < limit:
sequence_num = 0
n = num
if n == 1:
sequence_num = 1
else:
while n != 1:
if n % 2 == 0:
n = n / 2
sequence_num += 1
else:
n = 3 * n + 1
sequence_num += 1
sequence_num += 1
seq_list.append(sequence_num)
num += 1
k = seq_list.index(max(seq_list))
print(k + 1)
Merci d'avoir répondu mais je cherche une explication quant à la raison pour laquelle ma mise en œuvre ne fonctionne pas.
En ce qui concerne aussi la solution au problème du projet Euler actuel, la mise en œuvre ci-dessus le fait déjà.
Oui, vous pouvez faire des choses à votre code pour l'optimiser. Mais je pense que, plus important encore, il y a une observation mathématique que vous devez considérer, ce qui est au cœur du problème: étant donné, on peut toujours diviser (3 * n + 1) par 2. Et cela permet d'économiser un peu de temps ...
Voici une amélioration (il faut 1,6 seconde): il n'est pas nécessaire de calculer la séquence de chaque nombre. Vous pouvez créer un dictionnaire et stocker le nombre d'éléments d'une séquence. Si un chiffre qui est apparu est déjà présenté, la séquence est calculée comme DIC [Original_number] = DIC [N] + Count - 1. Cela fait gagner beaucoup de temps.
import time
start = time.time()
def main(n,dic):
'''Counts the elements of the sequence starting at n and finishing at 1'''
count = 1
original_number = n
while True:
if n < original_number:
dic[original_number] = dic[n] + count - 1 #-1 because when n < original_number, n is counted twice otherwise
break
if n == 1:
dic[original_number] = count
break
if (n % 2 == 0):
n = n/2
else:
n = 3*n + 1
count += 1
return dic
limit = 10**6
dic = {n:0 for n in range(1,limit+1)}
if __name__ == '__main__':
n = 1
while n < limit:
dic=main(n,dic)
n += 1
print('Longest chain: ', max(dic.values()))
print('Number that gives the longest chain: ', max(dic, key=dic.get))
end = time.time()
print('Time taken:', end-start)
Le truc pour résoudre cette question est de calculer les réponses de la plus grande entrée et de sauvegarder le résultat en tant que recherche pour toutes les entrées plus petites plutôt que de calculer la limite supérieure extrême.
Voici mon implémentation qui passe tous les cas de test. (Python3)
Dans de nombreux problèmes de Hackerrank, vous obtenez cette erreur si vous utilisez Python. Le même code dans d'autres langues, il va passer tous les tests.
@RPanai - Hmm ... on dirait que ça ...