Projet Euler 9 Conservation des résultats des calculs

Un nombre de Pitagolas (un nombre naturel qui satisfait le théorème de Pitagolas) est un ensemble de nombres qui satisfont l'équation suivante avec a <b <c.

a2 + b2 = c2 Par exemple, 32 + 42 = 9 + 16 = 25 = 52.

Il n'y a qu'un seul triplet de Pitagoras avec a + b + c = 1000. Calculez le produit abc de ceux-ci. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209

Tout d'abord, je l'ai écrit docilement.

def cof1():
  target=1000
  (a,b,c) = (1, 1, target - 2)
  ans = 0
  while a < c:
    while b < c:
      if a**2 + b**2 == c**2:
        ans = a*b*c
        break
      (b,c) = (b + 1, c - 1)
    if ans:
      break
    else:
      (a,b,c) = (a + 1, a + 1, target - a*2 -2)
  #print ans

J'ai pensé qu'il serait inefficace de revoir et de calculer les carrés de a, b et c à chaque fois. pe9.png

J'ai donc créé une liste de carrés de 1 à 999 à l'avance et j'ai essayé de m'y référer.

def cof2():
  target=1000
  sq = [x**2 for x in range(0,target)] #create 
  (a,b,c) = (1, 1, target - 2)
  ans = 0
  while a < c:
    while b < c:
      if sq[a] + sq[b] == sq[c]:
        ans = a*b*c
        break
      (b,c) = (b + 1, c - 1)
    if ans:
      break
    else:
      (a,b,c) = (a + 1, a + 1, target - a*2 -2)
  #print ans

En conséquence, nous avons pu réduire 3,9 millisecondes (exécutées 100 fois ci-dessous).

pe9_2.png

Recommended Posts

Projet Euler 9 Conservation des résultats des calculs
Projet Euler 37
Projet Euler 7
Projet Euler 47
Projet Euler 10 "Somme des nombres premiers"
Projet Euler 31
Projet Euler 4
Projet Euler 38
Projet Euler 17
Projet Euler 26
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 39
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
Projet Euler # 16 "Somme des pouvoirs" en Python
Projet Euler # 17 "Nombre de caractères" en Python
Projet Euler # 1 "Multiple de 3 et 5" en Python
[Projet Euler] problème1
Projet Euler # 10 "somme des nombres premiers" en Python
Projet Euler # 13 "Somme des grands nombres" en Python
Projet Euler # 6 "Différence de somme des carrés" en Python
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1
Réutiliser les résultats du clustering
Calcul de similitude par MinHash
À propos du calcul des coûts de MeCab
Qu'est-ce que Project Euler 3 Acceleration?