Projet Euler 34

problème

145 est un nombre intéressant.1! + 4! + 5! = 1 + 24 + 120 = 145.

Trouvez la somme des nombres pour que la somme des échelles de chaque chiffre corresponde à elle-même.

Remarque: 1! = 1 et 2! = 2 ne doivent pas être inclus dans la somme. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2034

Répondre

J'ai fait une fonction pour juger si un certain nombre est la somme des échelles.

def is_wa_of_kaijo(i,kaijos):
  s = 0
  for j in str(i):
    s+= kaijos[int(j)]
  if i == s:
    return True
  else:
    return False

En utilisant cette fonction, nous avons effectué une recherche à 100% dans la plage considérée comme la valeur maximale, mais c'était très lent. Puisque n> = 7 et 10 ** n -1> 9! * N, il suffit de rechercher la plage jusqu'à 9! * 7.

def main():
  MAX = math.factorial(9)*7
  kaijos = [math.factorial(x) for x in range(0,10)]
  ans = 0
  for i in range(3,MAX):
    if is_wa_of_kaijo(i,kaijos):
      ans += i
  print ans

En guise d'approche différente, j'ai d'abord créé un objet de type ensemble de somme avec un maximum de 7 facteurs, puis j'ai essayé d'effectuer une recherche à 100% sur l'objet de type d'ensemble de somme avec ce rang. Au moins, la partie décision doit être plus rapide car la population de recherche est plus petite. J'ai essayé de me souvenir des facteurs lors de la création de la liste de somme des échelles, mais j'ai abandonné la mise en œuvre car c'était devenu un processus très compliqué. La puissance de zéro est 1, mais au début, elle est mise à 0 car la valeur de la liste sans addition est conservée.

def main2():
  kaijos = [0] + [math.factorial(x) for x in range(1,10)]
  kaijos2 = set(x1+x2 for x1 in kaijos for x2 in kaijos)
  kaijos3 = set(x1+x2 for x1 in kaijos for x2 in kaijos2)
  kaijos4 = set(x1+x2 for x1 in kaijos2 for x2 in kaijos2)
  kaijos7 = set(x1+x2 for x1 in kaijos3 for x2 in kaijos4)
  kaijos[0] = 1
  ans = -3
  for i in kaijos7:
    if is_wa_of_kaijo(i,kaijos):
      ans += i
  print ans

J'ai également envisagé une version qui augmente légèrement la notation d'inclusion du générateur.

def main3():
  kaijos = [0] + [math.factorial(x) for x in range(1,10)]
  kaijos7 = set(x1+x2+x3+x4+x5+x6+x7 for x1 in kaijos for x2 in kaijos for x3 in kaijos for x4 in kaijos for x5 in kaijos for x6 in kaijos for x7 in kaijos)
  kaijos[0] = 1
  print len(kaijos7)
  ans = -3
  for i in kaijos7:
    if is_wa_of_kaijo(i,kaijos):
      ans += i
  #print ans

Temps d'exécution main2() 0.484 main3() 18.011

J'examinerai plus tard quelle est la cause de cette différence de temps d'exécution.

Recommended Posts

Projet Euler 37
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 38
Projet Euler 26
Projet Euler 8
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1
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 # 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 # 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
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 28 Proposition de réponse inefficace Créer des "numéros en spirale"
Projet Euler 4 Coding avec une nouvelle approche échoue.
Projet Euler n ° 12 "Triangles hautement ajustés" en Python