Projet Euler 14

problème

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

Politique de réponse

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.

code

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)

résultat

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

Projet Euler 37
Projet Euler 7
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 14
Projet Euler 34
Projet Euler 25
[Projet Euler] problème1
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Qu'est-ce que Project Euler 3 Acceleration?
Programmation fonctionnelle dans Python Project Euler 1
Projet Euler 10 "Somme des nombres premiers"
[Note] Projet Euler en Python (problème 1-22)
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 4 Tentative d'accélération
Programmation fonctionnelle dans Python Project Euler 2
Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 15 "Lattice Path" en Python
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler 9 Conservation des résultats des calculs
Projet Euler # 3 "Maximum Prime Factors" en Python
Projet Euler # 11 "Produit maximum dans la grille" en Python
Projet Euler # 7 "1000 1er nombre premier" en Python
Projet Euler # 16 "Somme des pouvoirs" en Python
Projet Euler # 9 "Numéro spécial Pitagolas" en Python
Projet Euler # 14 "Colonne de nombre de collats la plus longue" en Python
J'ai écrit Project Euler 1 en une seule ligne.
Projet Euler # 2 "Even Fibonacci Number" en Python
Projet Euler # 17 "Nombre de caractères" en Python
Projet Euler # 1 "Multiple de 3 et 5" en Python
Projet Euler # 8 "Produit maximum en chaîne numérique" en Python
Projet Euler # 10 "somme des nombres premiers" en Python
Projet Euler 4 Coding avec une nouvelle approche échoue.