¿Cuántos dígitos en esta base?
https://stackoverflow.com/questions/1847131
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
El problema es derivar una fórmula para determinar el número de dígitos de un número decimal dado podría tener en una base dada.
Por ejemplo:. El número decimal 100 006 puede ser representado por 17,11,9,8,7,6,8 dígitos en bases 2,3,4,5,6,7,8 respectivamente
Bien la fórmula I derivado hasta ahora es así: (log10 (num) / log10 (base)) + 1
.en C / C ++ utilicé esta fórmula para calcular los resultados dados anteriormente.
long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;
Pero, lamentablemente, la fórmula no está dando respuesta correcta es algunos casos, como los siguientes:
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
Así que el error es de 1 digit.I sólo quiero a alguien que me ayude a corregir la fórmula para que el trabajo para cada posibles casos.
Editar De acuerdo con la especificación de entrada tengo que hacer frente a casos como 10 mil millones, es decir 10 ^ 10, no creo log10 () en C / C ++ puede manejar este tipo de casos? Así que cualquier otro procedimiento / fórmula para este problema será muy apreciada.
Solución
Hay operaciones rápidas que flotan en la configuración del compilador. Es necesario floation operaciones precisas. El caso es que log10 (8) / log10 (2) es siempre 3 en matemáticas. Pero puede ser el resultado es 2,99999, por expample. Es malo. Debe añadir aditivos pequeña, pero no 0,5. Debe tratarse de 0,00001 o algo por el estilo.
fórmula casi cierto:
int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);
solución realmente cierto
Debe comprobar el resultado de la fórmula. Compexity es O(log log n) o 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;
}
Esta comprobación es mejor que la prueba de fuerza bruta con multiplicaciones base.
Otros consejos
Cualquiera de las siguientes funcionará:
>>> 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
...
La primera versión se explica en mathpath.org . En la segunda versión el + 1 es necesario para producir la respuesta correcta para cualquier número n que es el número más pequeño con d dígitos en la base b . Es decir, los números que están escritas 10 ... 0 en la base de b . Observe que 0 de entrada debe ser tratado como un caso especial.
ejemplos decimales:
>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3
Binario:
>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11
Editar : El PO afirma que la solución log puede no funcionar para grandes entradas. Yo no sé nada de eso, pero si es así, el siguiente código no debería romperse, ya que utiliza la aritmética de enteros solamente (esta vez en C):
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 0;
while (d++, n /= b);
return d;
}
Este código será probablemente menos eficiente. Y Sí , que fue escrito por los puntos máximos Obscurity. Es simplemente usa la observación de que cada número tiene al menos un dígito, y que cada Divison por b que no dió 0 implica la existencia de un dígito adicional. Una versión más fácil es la siguiente:
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 1;
while (n /= b) {
d++;
}
return d;
}
Debido a que su fórmula es correcta (acabo probé), yo creo que es un error de redondeo en su división, causando que el número sea sólo un poco menor que el valor entero que debería ser. Así que cuando se trunca a un entero, se pierde 1. Trate de añadir un adicional de 0,5 a su valor final (de modo que truncar es en realidad una operación de vuelta).
Lo que queremos es el techo (= menor entero no mayor que) log b (n + 1), en lugar de lo que estás calcular en este momento, suelos (1 + log b (n)).
Usted puede tratar de:
int digits = (int) ceil( log((double)(n+1)) / log((double)base) );
Como otros han señalado, que haya error de redondeo, pero las soluciones propuestas simplemente mover la zona de peligro o hacerlo más pequeño, no lo elimina. Si los números son números enteros luego verificar - utilizando la aritmética de enteros - que un poder de la base es menor o igual a su número, y el siguiente es por encima de ella (la primera potencia es la número de dígitos). Pero si se utiliza la aritmética de punto flotante en cualquier lugar de la cadena, entonces será vulnerable al error (a menos que su base es una potencia de dos, y tal vez incluso entonces).
editar
Aquí es solución bruta pero eficaz en la aritmética de enteros. Si sus clases enteros pueden contener números tan grandes como número base *, esto le dará la respuesta correcta.
size = 0, k = 1;
while(k<=num)
{
k *= base;
size += 1;
}
Uso de su fórmula,
log(8)/log(2) + 1 = 4
el problema está en la precisión del cálculo de logaritmo. Con
ceil(log(n+1)/log(b))
debe resolver ese problema. Esto no es exactamente lo mismo que
ceil(log(n)/log(b))
porque esto da la respuesta 3 para n = 8 b = 2, ni es el mismo que
log(n+1)/log(b) + 1
porque esto da la respuesta 4 para n = 7 b = 2 (cuando se calcula a precisión completa).
En realidad tengo algo curioso que resulta implementar y compilar la primera forma con g ++:
double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);
falla (IE da la respuesta 3), mientras que,
double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);
tiene éxito (da la respuesta 4). Mirando un poco más creo que una tercera forma
ceil(log(n+0.5)/log(b))
sería más estable, ya que evita el caso "crítico" cuando N (o N + 1 para la segunda forma) es una potencia entera de b (para valores enteros de n).
Puede ser beneficioso para envolver una función de redondeo (por ejemplo + 0.5) en su código en algún lugar: es bastante probable que la división está produciendo (por ejemplo) 2,99989787, a la que se añade 1,0, dando 3,99989787 y cuando que es convertido a un int , da 3.
Parece que la fórmula es correcta para mí:
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
Así que es definitivamente sólo un error de redondeo.
Flotante problemas de redondeo de punto.
log10(216) / log10(6) = 2.9999999999999996
Pero no se puede añadir 0,5 como se sugiere, porque no funcionaría para el siguiente
log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5
log10(1296) = log10(6) = 4.0 // 1, 0, 0, 0, 0
Tal vez usando el log (valor, base) función sería evitar estos errores de redondeo.
Creo que la única manera de eliminar el error de redondeo sin producir otros errores es utilizar o aplicar logaritmos de números enteros.
Aquí es una solución en 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);
}
