Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Längste Dezimalperiode

Finde das d bis zu einer Grenze, für das der Bruch 1/d die längste Periode in der Dezimaldarstellung hat.

Das lernst du

  • Schriftliche Division mit Resten simulieren
  • Eine Wiederholung mit einer Nachschlagetabelle erkennen
  • Eine Zykluslänge aus den ersten Vorkommen bestimmen

Problem

Manche Stammbrüche brechen ab (1/4 = 0,25), die übrigen sind periodisch: 1/6 = 0,1666... hat eine Periode der Länge 1 und 1/7 = 0,142857142857... eine der Länge 6. Finde unter d = 2, 3, ..., limit das d, für das 1/d die längste Periode hat. Führe dazu die schriftliche Division im Code durch: Die Ziffern wiederholen sich, sobald ein Rest zum zweiten Mal auftritt.

Implementiere longest_recurring_cycle(limit).

Eingabe

limit: Der größte Nenner, der ausprobiert wird.

Ausgabe

Gib das d mit der längsten Periode zurück. Ein abbrechender Bruch hat die Periodenlänge 0. Bei Gleichstand gib das kleinste d zurück.

Einschränkungen

2 ≤ limit ≤ 2000

Beispiele

Beispiel 1
Eingabe:
limit = 8

Erwartete Ausgabe:
expected = 7
Eingabe:
long long limit = 8;

Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long limit = 8;

Erwartete Ausgabe:
long expected = 7;

Erläuterung

Die Periodenlängen für 2 bis 8 sind 0, 1, 0, 0, 1, 6, 0, also lautet die Antwort 7.

Beispiel 2
Eingabe:
limit = 5

Erwartete Ausgabe:
expected = 3
Eingabe:
long long limit = 5;

Erwartete Ausgabe:
long long expected = 3;
Eingabe:
long limit = 5;

Erwartete Ausgabe:
long expected = 3;

Erläuterung

1/3 hat eine einstellige Periode, 1/2, 1/4 und 1/5 brechen ab, also lautet die Antwort 3.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Jede neue Ziffer von 1/d ergibt sich aus dem Rest mal 10.

Hinweis 2

Merke dir, in welchem Schritt jeder Rest zum ersten Mal aufgetreten ist.

Hinweis 3

Wird der Rest 0, bricht die Dezimalzahl ab. Sonst ist die Periodenlänge der Abstand zwischen zwei Vorkommen desselben Rests.

Erwartete Komplexität

Zeit O(limit²), 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.