Problem
Für jede positive Zahl n legt die Collatz-Regel das nächste Glied fest: n / 2, wenn n gerade ist, und 3n + 1, wenn n ungerade ist. Die Folge endet, sobald sie 1 erreicht. Die Folge für 6 lautet 6, 3, 10, 5, 16, 8, 4, 2, 1, das sind neun Glieder. Finde unter allen Startzahlen von 1 bis limit diejenige mit den meisten Gliedern.
Implementiere longest_collatz_chain(limit).
Verschiedene Folgen enden oft gleich. Wenn du dir für jede Zahl die gefundene Länge merkst, sparst du viel Arbeit. Unterwegs können die Glieder größer als die Grenze werden, verwende daher 64-Bit-Ganzzahlen.
Eingabe
limit: Die größte Startzahl, die ausprobiert wird.
Ausgabe
Gib die Startzahl zurück, deren Folge die meisten Glieder hat (Startzahl und abschließende 1 mitgezählt). Bei Gleichstand gib die kleinste dieser Startzahlen zurück.
Einschränkungen
1 ≤ limit ≤ 100.000
Beispiele
Eingabe:
limit = 6
Erwartete Ausgabe:
expected = 6
Eingabe:
long long limit = 6;
Erwartete Ausgabe:
long long expected = 6;
Eingabe:
long limit = 6;
Erwartete Ausgabe:
long expected = 6;
Erläuterung
Die Folgen für 1 bis 6 haben 1, 2, 8, 3, 6 und 9 Glieder, also lautet die Antwort 6.
Eingabe:
limit = 10
Erwartete Ausgabe:
expected = 9
Eingabe:
long long limit = 10;
Erwartete Ausgabe:
long long expected = 9;
Eingabe:
long limit = 10;
Erwartete Ausgabe:
long expected = 9;
Erläuterung
9 ergibt 20 Glieder (9, 28, 14, 7, ...), mehr als jede andere Startzahl bis 10, also lautet die Antwort 9.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Zähle zuerst die Glieder einer einzelnen Folge, einschließlich der Startzahl und der 1.
Hinweis 2
Erreicht eine Folge eine Zahl, deren Länge du schon kennst, addiere diese Länge, statt weiterzurechnen.
Hinweis 3
Ersetze die beste Startzahl nur, wenn eine Länge echt größer ist.
Erwartete Komplexität
Zeit O(limit × average new steps), zusätzlicher Speicher O(limit)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.