Définissez une séquence de nombres qui est générée à plusieurs reprises par la formule suivante pour un entier positif.
n → n / 2 (n est pair)
n → 3n + 1 (n est impair)
À partir de 13, cette séquence est la suivante.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 Il y a 10 termes de 13 à 1. On pense que cette séquence se termine à 1 quel que soit le nombre avec lequel vous commencez, mais cela n'a pas encore été prouvé (problème de Colats).
Maintenant, lequel des nombres inférieurs à 1 million devrait être lancé pour générer la plus longue séquence de nombres?
Remarque: peut être supérieur à 1 million au milieu d'une rangée http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
En termes de séquence de nombres de, la longueur de la séquence de nombres générée par 13 est la longueur de la séquence de nombres générée par 40 plus un. En d'autres termes, la longueur de la séquence de nombres générée en 13 est calculée de manière récursive. De plus, la quantité de calcul peut être réduite en stockant le résultat au milieu.
def next(n):
if n % 2:
return n*3 + 1
else:
return n / 2
def add(dict,n1):
n2 = next(n1)
if not n2 in dict:
dict = add(dict,n2)
dict[n1] = dict[n2]+1
return dict
def main():
dict = {1:1}
(max_i,max) = (1,1)
for i in range(2,10**6):
if not i in dict:
dict = add(dict,i)
if dict[i] > max:
(max_i,max) = (i,dict[i])
print (max_i,max)
Le résultat était de 2,87 secondes, ce qui était aussi lent qu'un démon. Lorsque j'ai cherché sur le net, j'ai trouvé un code qui améliorait la vitesse en ne se souvenant pas des nombres (1 million) plus grands qu'un certain nombre.
Recommended Posts