[PYTHON] Projekt Euler 14

Problem

Definieren Sie eine Zahlenfolge, die wiederholt durch die folgende Formel für eine positive Ganzzahl generiert wird.

n → n / 2 (n ist gerade)

n → 3n + 1 (n ist ungerade)

Ab 13 sieht diese Zahlenfolge folgendermaßen aus:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 Es gibt 10 Terme von 13 bis 1. Es wird angenommen, dass diese Sequenz bei 1 endet, egal mit welcher Zahl Sie beginnen, aber das wurde noch nicht bewiesen (Colats-Problem).

Welche der Zahlen unter 1 Million sollte nun gestartet werden, um die längste Folge von Zahlen zu generieren?

Hinweis: Kann über 1 Million in der Mitte einer Reihe sein http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014

Antwortrichtlinie

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

In Bezug auf die Zahlenfolge von ist die Länge der durch 13 erzeugten Zahlenfolge die Länge der durch 40 plus eins erzeugten Zahlenfolge. Mit anderen Worten wird die Länge der durch 13 erzeugten Zahlenfolge rekursiv berechnet. Darüber hinaus kann der Rechenaufwand reduziert werden, indem das Ergebnis in der Mitte gespeichert wird.

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)

Ergebnis

Das Ergebnis war 2,87 Sekunden, was so langsam war wie ein Dämon. Als ich im Internet suchte, fand ich einen Code, der die Geschwindigkeit verbesserte, indem ich mich nicht an Zahlen (1 Million) erinnerte, die größer als eine bestimmte Zahl waren.

Recommended Posts

Projekt Euler 37
Projekt Euler 7
Projekt Euler 47
Projekt Euler 31
Projekt Euler 4
Projekt Euler 17
Projekt Euler 26
Projekt Euler 8
Projekt Euler 23
Projekt Euler 19
Projekt Euler 50
Projekt Euler 42
Projekt Euler 33
Projekt Euler 32
Projekt Euler 43
Projekt Euler 35
Projekt Euler 24
Projekt Euler 46
Projekt Euler 48
Projekt Euler 45
Projekt Euler 6
Projekt Euler 44
Projekt Euler 39
Projekt Euler 40
Projekt Euler 49
Projekt Euler 27
Projekt Euler 41
Projekt Euler 18
Projekt Euler 13
Projekt Euler 30
Projekt Euler 14
Projekt Euler 34
Projekt Euler 25
[Project Euler] Problem1
Projekt Euler15 "Gitterpfad"
Projekt Euler 2 Beschleunigung 2.21 Mikrosekunden speichern.
Was ist Project Euler 3-Beschleunigung?
Funktionsprogrammierung in Python Project Euler 1
Projekt Euler 10 "Summe der Primzahlen"
[Hinweis] Project Euler in Python (Problem 1-22)
Funktionale Programmierung in Python Project Euler 3
Projekt Euler # 5 "Minimum Multiple" in Python
Project Euler 4 Versuch zu beschleunigen
Funktionsprogrammierung in Python Project Euler 2
Projekt Euler 11 "Maximales Produkt im Raster"
Projekt Euler # 15 "Gitterpfad" in Python
Projekt Euler # 4 "Maximale Kalligraphie" in Python
Projekt Euler 9 Aufbewahrung der Berechnungsergebnisse
Projekt Euler # 3 "Maximale Primfaktoren" in Python
Projekt Euler # 11 "Maximales Produkt im Raster" in Python
Projekt Euler # 7 "1000 1. Primzahl" in Python
Projekt Euler # 16 "Summe der Kräfte" in Python
Projekt Euler # 9 "Spezielle Pitagolas-Nummer" in Python
Projekt Euler # 14 "Längste Spalte mit Kollatennummern" in Python
Ich habe Project Euler 1 in einem Liner geschrieben.
Projekt Euler # 2 "Gerade Fibonacci-Zahl" in Python
Projekt Euler # 17 "Anzahl der Zeichen" in Python
Projekt Euler # 1 "Vielfaches von 3 und 5" in Python
Projekt Euler # 8 "Maximales Produkt in Anzahl Zeichenfolge" in Python
Projekt Euler # 10 "Summe der Primzahlen" in Python
Projekt Euler 4 Die Codierung mit einem neuen Ansatz schlägt fehl.