Combien de chiffres dans cette base?
https://stackoverflow.com/questions/1847131
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Le problème est d'obtenir une formule pour déterminer le nombre de chiffres d'un nombre décimal donné peut avoir dans une base donnée.
Par exemple:. Le nombre décimal 100006 peut être représenté par 17,11,9,8,7,6,8 chiffres 2,3,4,5,6,7,8 dans les bases respectivement
Eh bien la formule I tirais jusqu'à présent est le suivant: (log10 (num) / log10 (base)) + 1
.en C / C ++ I utilisé cette formule pour calculer les résultats donnés ci-dessus.
long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;
Mais malheureusement, la formule ne donne pas de réponse correcte est certains cas, comme ceux-ci:
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
Ainsi, l'erreur est de 1 digit.I veux juste quelqu'un pour me aider à corriger la formule pour que cela fonctionne pour tous les cas possibles.
Modifier Selon la spécification d'entrée, je dois traiter les cas comme 10000000000, i.e. 10 ^ 10, je ne pense pas log10 () soit dans C / C ++ peut traiter de tels cas? Ainsi, toute autre procédure / formule pour ce problème sera très apprécié.
La solution
Il y a des opérations flottantes rapide dans vos paramètres du compilateur. Vous avez besoin d'opérations précises flottation. La chose est que log10 (8) / log10 (2) est toujours 3 en mathématiques. Mais peut-être votre résultat est 2,99999, pour expample. C'est mauvais. Vous devez ajouter petit additif, mais pas 0,5. Il devrait être d'environ 0,00001 ou quelque chose comme ça.
Presque vraie formule:
int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);
Vraiment vraie solution
Vous devriez vérifier le résultat de votre formule. Est O(log log n) ou complexités 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;
}
Cette vérification est mieux que le test avec force brute multiplications base.
Autres conseils
Soit des éléments suivants fonctionneront:
>>> 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 première version est expliqué à mathpath.org . Dans la deuxième version du + 1 est nécessaire pour obtenir la bonne réponse pour tout nombre n qui est le plus petit nombre avec d chiffres dans la base b . Autrement dit, ces chiffres qui sont écrits 10 ... 0 dans la base b . CONSTATENT que 0 d'entrée doit être traitée comme un cas particulier.
Exemples de décimales:
>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3
binaire:
>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11
Modifier : L'OP déclare que la solution log ne fonctionne pas pour les grandes entrées. Je ne sais pas, mais le cas échéant, le code suivant ne devrait pas tomber en panne, car il utilise l'arithmétique des nombres entiers (cette fois en C):
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 0;
while (d++, n /= b);
return d;
}
Ce code sera probablement moins efficace. Et oui , il a été écrit pour les points de obscurité maximale. Il utilise simplement l'observation que chaque numéro a au moins un chiffre, et que tous les divison par b qui ne donne pas 0 implique l'existence d'un chiffre supplémentaire. Une version plus lisible est la suivante:
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 1;
while (n /= b) {
d++;
}
return d;
}
Étant donné que votre formule est correcte (je viens d'essayer), je pense que c'est une erreur d'arrondi dans votre division, à l'origine du nombre d'être légèrement inférieur à la valeur entière, il devrait être. Ainsi, lorsque vous tronquer à un nombre entier, vous perdez 1. Essayez d'ajouter un 0,5 supplémentaire à votre valeur finale (de sorte que tronquer est en fait une opération ronde).
Qu'est-ce que vous voulez est plafond (= le plus petit entier non supérieur) log b (n + 1), plutôt que ce que vous calculez en ce moment, étage (1 + log b (n)).
Vous pouvez essayer:
int digits = (int) ceil( log((double)(n+1)) / log((double)base) );
Comme d'autres l'ont souligné, vous avez erreur d'arrondi, mais les solutions proposées il suffit de déplacer la zone de danger ou de le rendre plus petit, ils ne l'élimine pas. Si vos chiffres sont des nombres entiers, vous pouvez vérifier - en utilisant l'arithmétique entier - que l'une puissance de la base est inférieure ou égale à votre numéro, et l'autre est au-dessus (la première puissance est la nombre de chiffres). Mais si vous utilisez l'arithmétique en virgule flottante partout dans la chaîne alors vous serez vulnérable à l'erreur (à moins que votre base est une puissance de deux, et peut-être même à l'époque).
EDIT:
Voici solution brute mais efficace en arithmétique entière. Si vos classes entières peuvent contenir des nombres aussi grand que le numéro de base *, cela donnera la bonne réponse.
size = 0, k = 1;
while(k<=num)
{
k *= base;
size += 1;
}
Utilisation de votre formule,
log(8)/log(2) + 1 = 4
le problème est dans la précision du calcul de logarithme. En utilisant
ceil(log(n+1)/log(b))
devrait résoudre ce problème. Ce n'est pas tout à fait la même chose que
ceil(log(n)/log(b))
parce que cela donne la réponse 3 pour n = 8 b = 2, ni la même chose que
log(n+1)/log(b) + 1
parce que cela donne la réponse 4 pour n = 7 b = 2 (lorsqu'il est calculé avec une précision d').
Je reçois un certain résultat curieux effectivement la mise en œuvre et la compilation de la première forme avec g ++:
double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);
échoue (IE donne la réponse 3), alors que,
double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);
réussit (donne la réponse 4). En regardant cela un peu plus je pense qu'une troisième forme
ceil(log(n+0.5)/log(b))
serait plus stable, car il évite le cas « critique » lorsque N (ou n + 1 de la seconde forme) est une puissance entière de b (pour les valeurs entières de n).
Il peut être bénéfique pour envelopper une fonction d'arrondi (par exemple + 0,5) dans votre code quelque part: il est probable que la division est produit (par exemple) 2,99989787, auquel 1.0 est ajouté, donnant 3,99989787 et quand cela est converti en un entier , il donne 3.
On dirait que la formule est juste pour moi:
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
Il est certainement juste une erreur d'arrondi.
Floating problèmes d'arrondi point.
log10(216) / log10(6) = 2.9999999999999996
Mais vous ne pouvez pas ajouter 0,5 comme l'a suggéré, parce que cela ne fonctionne pas pour les
log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5
log10(1296) = log10(6) = 4.0 // 1, 0, 0, 0, 0
en utilisant peut-être la fonction log (valeur, base) éviterait ces erreurs d'arrondi.
Je pense que la seule façon d'obtenir l'erreur d'arrondi éliminé sans produire d'autres erreurs est d'utiliser ou de mettre en œuvre des logarithmes entiers.
Voici une solution 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);
}
