[PYTHON] Projekt Euler 44

Problem

Die Fünfeckzahl wird durch "Pn = n (3n-1) / 2" erzeugt. Die ersten 10 Terme sind

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

Ist.

"P4 + P7 = 22 + 70 = 92 = P8". Aber der Unterschied "70 - 22 = 48" ist kein Fünfeck.

Über fünfeckige Paare Pj und Pk,Überlegen Sie, was der Unterschied und die Summe fünfeckig sind.Einen Unterschied machenD = |Pk - Pj|Schreiben.Finden Sie den Mindestwert der Differenz D.. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044

Antworten

Bestimmen Sie nach dem Erstellen einer Folge von Pentagonen bis zum 2n-Term, ob die Summe und Differenz der Pentagone des n-Terms und der Pentagone des 1. bis n-Terms beide Pentagone sind. tat. Da es einige Zeit dauerte, auf das Append-Attribut usw. zu verweisen, wurden das Append-Attribut und das Add-Attribut im Voraus in die Variablen eingefügt. Darüber hinaus wollten wir die Geschwindigkeit verbessern, indem wir uns auf das Set-Objekt beziehen, um festzustellen, ob die Elemente in einem vorgegebenen Set enthalten sind.

Als Ergebnis fanden wir zuerst eine Zahl, deren Summe und Differenz fünfeckig waren, aber wir konnten nicht bestätigen, dass es die kleinste war.

def pe44():
  start, stop = 1, 10**8
  pen = ((n * ( 3*n - 1))//2 for n in xrange(start, stop))
  p_list, p_set = [], set([])
  ans = 10**10
  i = 0
  append = p_list.append
  add = p_set.add
  while 1:
    append(pen.next())
    append(pen.next())
    add(p_list[2*i])
    add(p_list[2*i+1])
    
    d = search(p_list[i],p_list[:i+1],p_set)
    if d:
      min_d = min(d)
      if min_d < ans:
        found_answer(min_d)
        ans = min_d
    if ans < p_list[i+1] - p_list[i]:
      break
    i+=1
  return ans

def found_answer(n):
  print n

#@debug
def search(p1,p_list,p_set):
  d = []
  for p2 in p_list:
    if (p1+p2 in p_set) and (p1-p2 in p_set):
    #if (p1+p2 in p_list) and (p1-p2 in p_list):
      d.append(p1-p2)
  return d

pe44()