Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Längste Collatz-Folge

Finde die Startzahl bis zu einer Grenze, deren Collatz-Folge am längsten ist.

Das lernst du

  • Eine Collatz-Folge erzeugen
  • Ergebnisse zwischenspeichern, um doppelte Arbeit zu vermeiden
  • Gleichstände zugunsten des kleinsten Werts auflösen

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.