[PYTHON] Projekt Euler 34

Problem

145 ist eine interessante Zahl. 1! + 4! + 5! = 1 + 24 + 120 = 145.

Suchen Sie die Summe der Zahlen, sodass die Summe der Skalen jeder Ziffer mit sich selbst übereinstimmt.

Hinweis: 1! = 1 und 2! = 2 dürfen nicht in der Summe enthalten sein. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2034

Antworten

Ich habe eine Funktion erstellt, um zu beurteilen, ob eine bestimmte Zahl die Summe der Skalen ist.

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

Mit dieser Funktion haben wir eine 100% ige Suche innerhalb des Bereichs durchgeführt, der als Maximalwert angesehen wurde, der jedoch sehr langsam war. Da n> = 7 und 10 ** n -1> 9! * N ist, reicht es aus, den Bereich bis zu 9! * 7 zu durchsuchen.

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

Als anderen Ansatz habe ich zuerst ein Objekt vom Typ Summensatz mit maximal 7 Faktoren erstellt und dann versucht, eine 100% ige Suche nach dem Objekt vom Typ Summensatz mit diesem Rang durchzuführen. Zumindest sollte der Entscheidungsteil schneller sein, da die Suchpopulation kleiner ist. Ich habe versucht, mich an die Faktoren zu erinnern, als ich die Summenliste der Skalen erstellt habe, aber ich habe die Implementierung aufgegeben, weil es ein sehr komplizierter Prozess wurde. Die Potenz von Null ist 1, aber zu Beginn wird sie auf 0 gesetzt, da der Wert der Liste ohne Addition beibehalten wird.

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

Ich habe auch eine Version in Betracht gezogen, die die Einschlussnotation des Generators leicht erhöht.

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

Ausführungszeit main2() 0.484 main3() 18.011

Ich werde später untersuchen, was die Ursache für diesen Unterschied in der Ausführungszeit ist.