Das Problem besteht darin, eine Formel zur Bestimmung der Anzahl der Stellen abzuleiten, die eine gegebene Dezimalzahl in einer gegebenen Basis haben könnte.
Beispiel: Die Dezimalzahl 100006 kann durch 17,11,9,8,7,6,8 Ziffern in den Basen 2,3,4,5,6,7,8 dargestellt werden.
Nun, die Formel, die ich bisher abgeleitet habe, ist wie folgt: (log10 (num) / log10 (base)) + 1.
in C / C ++ Ich habe diese Formel verwendet, um die oben angegebenen Ergebnisse zu berechnen.
long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;
Aber leider gibt die Formel nicht die richtige Antwort in einigen Fällen, wie diese:
%Vor%Also ist der Fehler um 1 Ziffer. Ich will nur, dass jemand mir hilft, die Formel zu korrigieren, damit sie für alle möglichen Fälle funktioniert.
Bearbeiten: Gemäß der Eingabespezifikation muss ich mich mit Fällen wie 10000000000 befassen, d. h. 10 ^ 10, ich denke nicht, dass log10 () in C / C ++ solche Fälle behandeln kann? Daher wird jede andere Prozedur / Formel für dieses Problem sehr geschätzt.
In Ihren Compilereinstellungen gibt es schnelle Gleitoperationen. Sie benötigen präzise Floations-Operationen. Die Sache ist, dass log10 (8) / log10 (2) immer 3 in Mathe ist. Aber vielleicht ist Ihr Ergebnis 2.99999, zum Beispiel. Es ist schlecht. Sie müssen ein kleines Additiv hinzufügen, aber nicht 0,5. Es sollte etwa 0,00001 oder so ähnlich sein.
Fast wahre Formel:
%Vor%Wirklich wahre Lösung
Sie sollten das Ergebnis Ihrer Formel überprüfen. Compexity ist O(log log n) oder O(log result) !
Dieser Test ist besser als Brute-Force-Test mit base Multiplikationen.
Einer der folgenden Schritte funktioniert:
%Vor% Die erste Version wird unter mathpath.org erklärt. In der zweiten Version ist + 1 erforderlich, um die richtige Antwort für jede Zahl n zu erhalten, die die kleinste Zahl mit d Ziffern in der Basis b . Das sind jene Zahlen, die 10 ... 0 in Basis b geschrieben sind. Beachten Sie, dass Eingabe 0 als Sonderfall behandelt werden muss.
Dezimalbeispiele:
%Vor%Binär:
%Vor% Bearbeiten : Das OP gibt an, dass die log -Lösung möglicherweise nicht für große Eingaben funktioniert. Ich weiß nichts darüber, aber wenn dem so ist, sollte der folgende Code nicht zusammenbrechen, weil er nur Integer-Arithmetik verwendet (dieses Mal in C):
Dieser Code wird wahrscheinlich weniger effizient sein. Und ja , es wurde für maximale Unklarheiten geschrieben. Es verwendet einfach die Beobachtung, dass jede Zahl mindestens eine Ziffer hat, und dass jede Division nach b , die nicht 0 ergibt, die Existenz einer zusätzlichen Ziffer impliziert. Eine besser lesbare Version ist die folgende:
Da Ihre Formel korrekt ist (ich habe es gerade ausprobiert), würde ich meinen, dass es sich um einen Rundungsfehler in Ihrer Division handelt, was dazu führt, dass die Zahl nur geringfügig kleiner als der Integer-Wert ist. Wenn Sie also eine ganze Zahl abschneiden, verlieren Sie 1. Versuchen Sie, eine zusätzliche 0,5 zu Ihrem endgültigen Wert hinzuzufügen (so dass das Abschneiden tatsächlich eine runde Operation ist).
Wie andere bereits erwähnt haben, haben Sie einen Rundungsfehler, aber die vorgeschlagenen Lösungen verschieben einfach die Gefahrenzone oder machen sie kleiner, sie eliminieren sie nicht. Wenn Ihre Zahlen Ganzzahlen sind, können Sie - mit Ganzzahlarithmetik - überprüfen, dass eine Potenz der Basis kleiner oder gleich Ihrer Zahl ist und die nächste darüber ist (die erste Potenz ist die Anzahl an Ziffern). Aber wenn Sie Gleitkommaarithmetik irgendwo in der Kette verwenden, sind Sie anfällig für Fehler (es sei denn, Ihre Basis ist eine Zweierpotenz und vielleicht sogar dann).
BEARBEITEN:
Hier ist grobe, aber effektive Lösung in Ganzzahlarithmetik. Wenn Ihre Integer-Klassen Zahlen enthalten können, die so groß sind wie die Anzahl der Basen *, gibt dies die richtige Antwort.
Verwenden Sie Ihre Formel,
%Vor%Das Problem liegt in der Genauigkeit der Logarithmusberechnung. Verwenden Sie
%Vor%sollte dieses Problem lösen. Das ist nicht ganz dasselbe wie
%Vor%weil dies die Antwort 3 für n = 8 b = 2 ergibt, noch ist es dasselbe wie
%Vor%, weil dies die Antwort 4 für n = 7 b = 2 ergibt (wenn mit voller Genauigkeit berechnet).
Ich bekomme tatsächlich einige seltsame Ergebnisse, indem ich das erste Formular mit g ++ implementiere und kompiliere:
%Vor%schlägt fehl (IE gibt die Antwort 3), während
%Vor%ist erfolgreich (gibt die Antwort 4). Wenn ich es noch einmal betrachte, denke ich an eine dritte Form
%Vor%wäre stabiler, weil es den "kritischen" Fall vermeidet, wenn n (oder n + 1 für die zweite Form) eine ganzzahlige Potenz von b ist (für ganzzahlige Werte von n).
Es kann nützlich sein, eine Rundungsfunktion (z. B. + 0,5) irgendwo in Ihren Code einzufügen: Es ist sehr wahrscheinlich, dass die Division (zB) 2.99989787 produziert, zu der 1.0 hinzugefügt wird, was 3.99989787 ergibt und wenn diese in einen int konvertiert wird gibt es 3.
Gleitkomma-Rundungsprobleme.
%Vor%Aber Sie können nicht 0,5 wie vorgeschlagen hinzufügen, weil es für die folgenden nicht funktioniert
%Vor%Vielleicht würde die Verwendung der log (value, base) -Funktion diese Rundungsfehler vermeiden.