Wie viele Stellen in dieser Basis?
https://stackoverflow.com/questions/1847131
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Das Problem ist eine Formel zur Bestimmung Anzahl der Stellen eine gegebene Dezimalzahl abzuleiten in einer gegebenen Basis haben könnte.
Zum Beispiel:. Die Dezimalzahl 100006 kann durch 17,11,9,8,7,6,8 Ziffern in Basen 2,3,4,5,6,7,8 jeweils dargestellt werden
Nun, die Formel I so weit abgeleitet ist wie folgt: (log10 (num) / log10 (Basis)) + 1
.in C / C ++ ich diese Formel verwendet, um die oben angegebenen Ergebnisse zu berechnen.
long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;
Aber leider ist die Formel nicht richtige Antwort gibt es einige Fälle, wie diese:
Number 8 in base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 64 in base 2 : 1,0,0,0,0,0,0
Number of digits: 7
Formula returned: 6
Number 64 in base 4 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 125 in base 5 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 128 in base 2 : 1,0,0,0,0,0,0,0
Number of digits: 8
Formula returned: 7
Number 216 in base 6 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 243 in base 3 : 1,0,0,0,0,0
Number of digits: 6
Formula returned: 5
Number 343 in base 7 : 1,0,0,0
Number of digits: 4
Formula returned: 3
So ist der Fehler von 1 digit.I wollen einfach nur jemanden, der mir helfen, die Formel zu korrigieren, so dass es für alle möglichen Fälle arbeiten.
Edit: Gemäß der Eingangsspezifikation I mit Fällen wie 10000000000 zu tun haben, das heißt 10 ^ 10, ich glaube nicht, log10 () entweder in C / C ++ können solche Fälle behandeln? So andere Verfahren / Formel für dieses Problem wird sehr geschätzt werden.
Lösung
Es gibt schnelle Floating-Operationen in Ihren Compiler-Einstellungen. Sie müssen präzise floation Operationen. Die Sache ist die, dass log10 (8) / log10 (2) immer 3 in Mathe ist. Aber kann Ihr Ergebnis ist 2,99999, Um zB sein. Es ist schlecht. Sie müssen kleinen Zusatzstoff hinzuzufügen, aber nicht mehr als 0,5. Es sollte etwa 0,00001 oder etwas ähnliches sein.
Fast wahre Formel:
int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);
Wirklich echte Lösung
Sie sollten das Ergebnis Ihrer Formel überprüfen. Komplexität im ist O(log log n) oder O(log result)!
int fast_power(int base, int s)
{
int res = 1;
while (s) {
if (s%2) {
res*=base;
s--;
} else {
s/=2;
base*=base;
}
}
return res;
}
int digits_size(int n, int base)
{
int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
return fast_power(base, s) > n ? s : s+1;
}
Diese Prüfung ist besser als Brute-Force-Test mit base Multiplikationen.
Andere Tipps
Eine der folgenden arbeiten:
>>> from math import *
>>> def digits(n, b=10):
... return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
... return int(ceil(log(n + 1, b))) if n else 1
...
Die erste Version wird erläutert unter mathpath.org . In der zweiten Version ist die + 1 notwendig, um die richtige Antwort für eine beliebige Anzahl n , die die kleinste Zahl mit ist d Ziffern in der Basis b zu erhalten. Das heißt, die Zahlen, die geschrieben sind 10 ... 0 in base b . Beachten Sie, dass Eingang 0 muss als Sonderfall behandelt werden.
Dezimal Beispiele:
>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3
Binary:
>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11
Bearbeiten : Die OP stellt fest, dass die log Lösung nicht für große Eingänge arbeiten kann. Ich weiß nicht so recht, aber wenn ja, der folgende Code sollte nicht brechen, weil es nur Integer-Arithmetik verwendet (diesmal in C):
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 0;
while (d++, n /= b);
return d;
}
Dieser Code wird wahrscheinlich weniger effizient. Und ja wurde für maximale Unklarheit Punkte geschrieben. Es nutzt einfach die Beobachtung, dass jede Zahl mindestens eine Ziffer hat, und dass jeder Divison von b die 0 nicht nachgeben wird impliziert die Existenz einer zusätzlichen Ziffer. Eine lesbare Version ist die folgende:
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 1;
while (n /= b) {
d++;
}
return d;
}
Da die Formel korrekt ist (ich habe gerade versucht), würde ich denken, dass es ein Rundungsfehler in Ihrer Abteilung, so dass die Zahl nur geringfügig kleiner sein als der Integer-Wert sollte es sein. Also, wenn Sie auf eine ganze Zahl gestutzt, verlieren Sie 1.e Versuchen weitere 0,5 auf Ihren Endwert Zugabe (so dass Abschneide tatsächlich ein runder Betrieb ist).
Was Sie wollen, ist Decke (= kleinste ganze Zahl nicht größer als) log b (n + 1), und nicht als das, was Sie jetzt gerade berechnet wird, Stock (1 + log b (n)).
Sie könnten versuchen:
int digits = (int) ceil( log((double)(n+1)) / log((double)base) );
Wie andere haben darauf hingewiesen, Sie haben Rundungsfehler, aber die vorgeschlagenen Lösungen einfach in die Gefahrenzone bewegen oder sie kleiner machen, sie nicht beseitigen. Wenn Ihre Zahlen ganze Zahlen sind, dann können Sie überprüfen, - Integer-Arithmetik mit -, dass eine Potenz der Basis kleiner oder gleich Ihre Nummer, und die nächste ist darüber (die erste Kraft ist die Anzahl an Ziffern). Aber wenn Sie Gleitkomma-Arithmetik verwenden überall in der Kette, dann werden Sie anfällig für Fehler (es sei denn, Ihre Basis eine Zweierpotenz ist, und vielleicht sogar dann).
EDIT:
Hier ist roh, aber effektive Lösung in Integer-Arithmetik. Wenn Sie Ihre ganze Zahl Klassen Zahlen so groß wie base * Zahl halten können, wird dies die richtige Antwort geben.
size = 0, k = 1;
while(k<=num)
{
k *= base;
size += 1;
}
Mit Ihrer Formel,
log(8)/log(2) + 1 = 4
Das Problem ist in der Genauigkeit der Logarithmusberechnung. Mit
ceil(log(n+1)/log(b))
sollte dieses Problem lösen. Das ist nicht ganz dasselbe wie
ceil(log(n)/log(b))
, da dies gibt die Antwort 3 für n = 8 b = 2, noch ist es die gleiche wie
log(n+1)/log(b) + 1
, da dies gibt die Antwort 4 für n = 7 b = 2 (wenn die Voll Genauigkeit berechnet).
ich tatsächlich einige neugierig resultierende Implementierung und der Zusammenstellung der ersten Form mit g ++:
double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);
fehlschlägt (IE gibt die Antwort 3), während
double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);
erfolgreich ist (gibt die Antwort 4). Betrachtet man es etwas mehr Ich denke, eine dritte Form
ceil(log(n+0.5)/log(b))
wäre stabiler sein, weil es den „kritischen“ Fall vermeidet, wenn n (oder n + 1 für die zweite Form) ist eine ganzzahlige Potenz von b (für ganzzahlige Werte von n).
Es kann vorteilhaft sein, eine Rundungsfunktion (zB + 0,5) in den Code zu wickeln irgendwo: es ist sehr wahrscheinlich, dass die Teilung (zB) 2,99989787 produziert, auf die 1,0 zugegeben wird, was 3,99989787 und wenn das in einen int umgewandelt ist es gibt 3.
Sieht aus wie die Formel richtig für mich ist:
Number 8 in base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3
log10(8) = 0.903089
log10(2) = 0.301029
Division => 3
+1 => 4
Es ist also auf jeden Fall nur ein Rundungsfehler.
Gleitkomma-Rundungsprobleme.
log10(216) / log10(6) = 2.9999999999999996
Sie können aber 0,5 nicht hinzufügen, wie vorgeschlagen, weil es nicht für die folgenden funktionieren würde,
log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5
log10(1296) = log10(6) = 4.0 // 1, 0, 0, 0, 0
Vielleicht das Protokoll verwenden (Wert, Base) Funktion würde vermeiden, dass diese Rundungsfehler.
Ich glaube, dass der einzige Weg, den Rundungsfehler eliminiert werden, ohne dass andere Fehler produzieren ist integer Logarithmen zu verwenden oder zu implementieren.
Hier ist eine Lösung in der Bash:
% digits() { echo $1 $2 opq | dc | sed 's/ .//g;s/.//' | wc -c; }
% digits 10000000000 42
7
static int numInBase(int num, int theBase)
{
if(num == 0) return 0;
if (num == theBase) return 1;
return 1 + numInBase(num/theBase,theBase);
}
