Dies ist eine Interviewfrage, auf die ich gestoßen bin: find K erste Ziffern der dezimalen Darstellung von 1/N. Es sieht so aus, als müssten wir einfach 10^K/N berechnen, um das Problem zu lösen. Macht das Sinn ? Es sieht so aus, als würde mir etwas fehlen, weil die Lösung zu einfach ist.So finden Sie K erste Ziffern der Dezimaldarstellung von 1/N
Gerade Grundschul lange Teilung implementieren:
int value = 1;
bool outputDecimalSeparator = false;
int digitsOutput = 1;
while(digitsOutput <= k) {
if (value == 0) {
Console.Write(0);
}
else {
if (value < n) {
Console.Write(0);
value *= 10;
}
else {
Console.Write(value/n);
value %= n;
}
}
if (outputDecimalSeparator == false) {
outputDecimalSeparator = true;
Console.Write('.');
}
digitsOutput++;
}
Console.WriteLine();
Der Zweig auf value == 0 ist zu erkennen, wenn 1/n eine Abschluss Darstellung von weniger als k Ziffern hat.
Hier ist n der Nenner in 1/n und k ist die Anzahl der Ziffern in der dezimalen Darstellung von 1/n zu drucken.
Beachten Sie, dass Sie durch die Änderung value *= 10 zu value *= b auch die b-ary-Darstellung von 1/n drucken können.
Wenn es erste k Ziffern ist, ist es nicht sehr einfach, den Zähler mit 10^k zu multiplizieren, und so wird es einfacher, durch N zu teilen? Und wenn wir die Antwort brauchen, die Dezimaldarstellung, dann enden wir damit, das Ergebnis erneut durch 10^K zu teilen, so dass die vorherige Multiplikation ungültig wird.
Dies ist die gleiche Frage, die OP stellt, dies ist keine Antwort. – user470379
@ user470379, OP hatte ein wenig Verwirrung in seiner Frage. Wenn er nur die ersten K Ziffern benötigt, dann ist das sehr einfach, da wir es aus Bequemlichkeit machen. –
Die Berechnung von 10^K/N kann bei großen K und kleinen N sehr teuer sein. Dies ist wahrscheinlich näher an einer guten Lösung: long division. So teilten wir Zahlen vor Taschenrechnern. :)
Offensichtlich sollten Sie diesen Algorithmus nur ausführen, bis es K Ziffern ergibt.
Was ist, wenn N 3 ist? – Pointy
das würde nicht funktionieren, weil 1/8 == .125. Wenn k == 2 dann 10^2/8 = 12,5, was nicht hilft. Die Antwort, die du willst, ist 25, oder? Vielleicht sehe ich das falsch? –
Die letzten 3? oder die ersten 3? ... Ich hoffe, Sie wissen, dass es einige Zahlen mit der Darstellung gibt, die unendliche Ziffern haben ... 1/3, 1/9 –