Comment compter chaque chiffre dans une plage d'entiers ?

Question

Imaginez que vous vendez ces chiffres métalliques utilisés pour numéroter les maisons, les portes de casiers, les chambres d'hôtel, etc. Vous devez déterminer combien de chaque chiffre vous devez expédier lorsque votre client a besoin de numéroter des portes ou des maisons :

• 1 à 100
• 51 à 300
• 1 à 2 000 avec des zéros à gauche

La solution évidente est de faire une boucle du premier au dernier chiffre, de convertir le compteur en une chaîne avec ou sans zéros à gauche, d'extraire chaque chiffre et de l'utiliser comme index pour incrémenter un tableau de 10 entiers.

Je me demande s'il n'existe pas une meilleure façon de résoudre ce problème, sans avoir à parcourir en boucle toute la plage des nombres entiers.

Les solutions dans n'importe quel langage ou pseudocode sont les bienvenues.

---

Edit :

Examen des réponses
John à CashCommons y Wayne Conrad que mon approche actuelle est suffisamment bonne et rapide. Permettez-moi d'utiliser une analogie stupide : Si l'on vous demandait de compter les cases d'un échiquier en moins d'une minute, vous pourriez terminer la tâche en comptant les cases une par une, mais une personne qui n'est pas en mesure de le faire ne pourrait pas le faire. meilleur La solution consiste à compter les côtés et à faire une multiplication, car on vous demandera peut-être plus tard de compter les tuiles d'un bâtiment.
Alex Reisner indique une loi mathématique très intéressante qui, malheureusement, ne semble pas être pertinente pour ce problème.
Andres suggère le même algorithme que j'utilise, mais en extrayant les chiffres avec des opérations %10 au lieu des sous-chaînes.
John à CashCommons y phord proposent de précalculer les chiffres nécessaires et de les stocker dans une table de consultation ou, pour plus de rapidité, dans un tableau. Cela pourrait être une bonne solution si nous avions une valeur entière maximale absolue, inamovible, gravée dans la pierre. Je n'en ai jamais vu.
Marque de haute performance et filtre a calculé les chiffres nécessaires pour différentes plages. Le résultat pour un millon semble indiquer qu'il y a une proportion, mais les résultats pour d'autres nombres montrent des proportions différentes.
filtre trouvé quelques formules qui peuvent être utilisées pour compter les chiffres d'un nombre qui est une puissance de dix. Robert Harvey a eu une expérience très intéressante en postant la question à MathOverflow. L'un des mathématiciens a écrit une solution en utilisant la notation mathématique.
Aaronaught développé et testé une solution en utilisant les mathématiques. Après l'avoir postée, il a examiné les formules provenant de Math Overflow et y a trouvé une faille (point pour Stackoverflow :).
noahlavine a développé un algorithme et l'a présenté en pseudocode.

Une nouvelle solution
Après avoir lu toutes les réponses, et fait quelques expériences, j'ai trouvé que pour une gamme d'entiers de 1 à 10 n -1 :

• Pour les chiffres de 1 à 9, n*10 (n-1) des pièces sont nécessaires
• Pour le chiffre 0, si on n'utilise pas de zéros de tête, n*10 n-1 - ((10 n -1) / 9) sont nécessaires
• Pour le chiffre 0, si on utilise des zéros de tête, n*10 n-1 - n sont nécessaires

La première formule a été trouvée par filtre (et probablement par d'autres), et j'ai trouvé les deux autres par essai et erreur (mais ils peuvent être inclus dans d'autres réponses).

Par exemple, si n = 6, la plage est de 1 à 999 999 :

• Pour les chiffres de 1 à 9, il faut 6*10. 5 \= 600 000 de chaque
• Pour le chiffre 0, sans les zéros de tête, nous avons besoin de 6*10. 5 - (10 6 -1)/9 = 600,000 - 111,111 = 488,889
• Pour le chiffre 0, avec les zéros de tête, nous avons besoin de 6*10. 5 - 6 = 599,994

Ces chiffres peuvent être vérifiés en utilisant Marque de haute performance les résultats.

En utilisant ces formules, j'ai amélioré l'algorithme original. Il boucle toujours du premier au dernier nombre de la plage d'entiers, mais, s'il trouve un nombre qui est une puissance de dix, il utilise les formules pour ajouter aux chiffres le nombre de la quantité pour une plage complète de 1 à 9 ou de 1 à 99 ou de 1 à 999, etc. Voici l'algorithme en pseudocode :

integer First,Last //First and last number in the range
integer Number     //Current number in the loop
integer Power      //Power is the n in 10^n in the formulas
integer Nines      //Nines is the resut of 10^n - 1, 10^5 - 1 = 99999
integer Prefix     //First digits in a number. For 14,200, prefix is 142
array 0..9  Digits //Will hold the count for all the digits

FOR Number = First TO Last
  CALL TallyDigitsForOneNumber WITH Number,1  //Tally the count of each digit 
                                              //in the number, increment by 1
  //Start of optimization. Comments are for Number = 1,000 and Last = 8,000.
  Power = Zeros at the end of number //For 1,000, Power = 3
  IF Power > 0                       //The number ends in 0 00 000 etc 
    Nines = 10^Power-1                 //Nines = 10^3 - 1 = 1000 - 1 = 999
    IF Number+Nines <= Last            //If 1,000+999 < 8,000, add a full set
      Digits\[0-9\] += Power\*10^(Power-1)  //Add 3\*10^(3-1) = 300 to digits 0 to 9
      Digits\[0\]   -= -Power              //Adjust digit 0 (leading zeros formula)
      Prefix = First digits of Number    //For 1000, prefix is 1
      CALL TallyDigitsForOneNumber WITH Prefix,Nines //Tally the count of each 
                                                     //digit in prefix,
                                                     //increment by 999
      Number += Nines                    //Increment the loop counter 999 cycles
    ENDIF
  ENDIF 
  //End of optimization
ENDFOR  

SUBROUTINE TallyDigitsForOneNumber PARAMS Number,Count
  REPEAT
    Digits \[ Number % 10 \] += Count
    Number = Number / 10
  UNTIL Number = 0

Par exemple, pour la plage 786 à 3 021, le compteur sera incrémenté :

• Par 1 de 786 à 790 (5 cycles)
• Par 9 de 790 à 799 (1 cycle)
• Par 1 de 799 à 800
• Par 99 de 800 à 899
• Par 1 de 899 à 900
• Par 99 de 900 à 999
• Par 1 de 999 à 1000
• Par 999 de 1000 à 1999
• Par 1 de 1999 à 2000
• Par 999 de 2000 à 2999
• Par 1 de 2999 à 3000
• Par 1 de 3000 à 3010 (10 cycles)
• Par 9 de 3010 à 3019 (1 cycle)
• Par 1 de 3019 à 3021 (2 cycles)

Total : 28 cycles Sans optimisation : 2 235 cycles

Notez que cet algorithme résout le problème sans zéros de tête. Pour l'utiliser avec des zéros en tête, j'ai utilisé un hack :

Si l'on a besoin d'une plage de 700 à 1 000 avec des zéros de tête, il faut utiliser l'algorithme pour 10 700 à 11 000, puis soustraire 1 000 - 700 = 300 du compte du chiffre 1.

Benchmark et code source

J'ai testé l'approche originale, la même approche en utilisant %10 et la nouvelle solution pour quelques grandes plages, avec ces résultats :

Original             104.78 seconds
With %10              83.66
With Powers of Ten     0.07

Une capture d'écran de l'application de référence :

_{(source : <a href="http://clarion.sca.mx/images/stories/digitsbench.png" rel="nofollow noreferrer">clarion.sca.mx </a>)}

Si vous souhaitez voir le code source complet ou exécuter le benchmark, utilisez ces liens :

• Code source complet (en Clarion ) : http://sca.mx/ftp/countdigits.txt
• Projet compilable et exe win32 : http://sca.mx/ftp/countdigits.zip

Réponse acceptée

noahlavine La solution est peut-être correcte, mais je n'ai pas pu suivre le pseudo-code, je pense qu'il manque certains détails ou qu'ils ne sont pas complètement expliqués.

Aaronaught La solution semble être correcte, mais le code est tout simplement trop complexe à mon goût.

J'ai accepté filtre J'ai choisi de répondre à cette question, car c'est son raisonnement qui m'a incité à développer cette nouvelle solution.

Answer 1

Il y a une solution mathématique claire à un problème comme celui-ci. Supposons que la valeur est remplie de zéros jusqu'au nombre maximum de chiffres (ce n'est pas le cas, mais nous y remédierons plus tard), et raisonnons en conséquence :

• De 0 à 9, chaque chiffre apparaît une fois
• De 0 à 99, chaque chiffre apparaît 20 fois (10x en position 1 et 10x en position 2).
• De 0 à 999, chaque chiffre apparaît 300 fois (100x en P1, 100x en P2, 100x en P3).

Le modèle évident pour un chiffre donné, si l'intervalle va de 0 à une puissance de 10, est le suivant N * 10 N-1 où N est une puissance de 10.

Que faire si l'intervalle n'est pas une puissance de 10 ? Commencez par la plus petite puissance de 10, puis remontez. Le cas le plus facile à traiter est un maximum comme 399. Nous savons que pour chaque multiple de 100, chaque chiffre se produit au moins 20 fois, mais nous devons compenser le nombre de fois où il apparaît dans la position du chiffre le plus significatif, qui sera exactement de 100 pour les chiffres 0-3, et exactement de zéro pour tous les autres chiffres. Plus précisément, la quantité supplémentaire à ajouter est de 10 N pour les chiffres correspondants.

En mettant cela dans une formule, pour les limites supérieures qui sont inférieures de 1 à un multiple d'une puissance de 10 (c'est-à-dire 399, 6999, etc.), cela devient : M * N * 10 N-1 + iif(d <= M, 10 N , 0)

Il ne vous reste plus qu'à vous occuper du reste (que nous appellerons R ). Prenons l'exemple de 445. Il s'agit du résultat obtenu pour 399, plus l'intervalle 400-445. Dans cet intervalle, la DMS se produit R plus de fois, et tous les chiffres (y compris le MSD) apparaissent également aux mêmes fréquences qu'ils le feraient dans l'intervalle [0 - R ].

Il ne nous reste plus qu'à compenser les zéros de tête. Ce modèle est facile - c'est juste :

10 N + 10 N-1 + 10 N-2 + ... + **10 0

Mise à jour : Cette version prend correctement en compte les "zéros de remplissage", c'est-à-dire les zéros en position intermédiaire lors du traitement du reste ([4 0 0, 4 0 1, 4 0 2, ...]). Le calcul des zéros de remplissage est un peu laid, mais le code révisé (pseudocode de style C) s'en charge :

function countdigits(int d, int low, int high) {
    return countdigits(d, low, high, false);
}

function countdigits(int d, int low, int high, bool inner) {
    if (high == 0)
        return (d == 0) ? 1 : 0;

    if (low > 0)
        return countdigits(d, 0, high) - countdigits(d, 0, low);

    int n = floor(log10(high));
    int m = floor((high + 1) / pow(10, n));
    int r = high - m * pow(10, n);
    return
        (max(m, 1) * n * pow(10, n-1)) +                             // (1)
        ((d < m) ? pow(10, n) : 0) +                                 // (2)
        (((r >= 0) && (n > 0)) ? countdigits(d, 0, r, true) : 0) +   // (3)
        (((r >= 0) && (d == m)) ? (r + 1) : 0) +                     // (4)
        (((r >= 0) && (d == 0)) ? countpaddingzeros(n, r) : 0) -     // (5)
        (((d == 0) && !inner) ? countleadingzeros(n) : 0);           // (6)
}

function countleadingzeros(int n) {
      int tmp= 0;
      do{
         tmp= pow(10, n)+tmp;
         --n;
         }while(n>0);
         return tmp;
         }

function countpaddingzeros(int n, int r) {
    return (r + 1) * max(0, n - max(0, floor(log10(r))) - 1);
}

Comme vous pouvez le voir, il est devenu un peu plus moche mais il s'exécute toujours en temps O(log n), donc si vous devez manipuler des nombres de plusieurs milliards, il vous donnera toujours des résultats instantanés :-) Et si vous l'exécutez sur l'intervalle [0 - 1000000], vous obtenez exactement la même distribution que celle postée par High-Performance Mark, donc je suis presque sûr que c'est correct.

Pour info, la raison pour laquelle le inner est que la fonction leading-zero est déjà récursive, donc elle ne peut être comptée que dans la première exécution de countdigits .

Mise à jour 2 : Au cas où le code serait difficile à lire, voici une référence pour savoir ce que chaque ligne de l'indicateur countdigits L'instruction return signifie (j'ai essayé les commentaires en ligne mais ils ont rendu le code encore plus difficile à lire) :

1. Fréquence de tout chiffre jusqu'à la plus grande puissance de 10 (0-99, etc.)
2. Fréquence des TMS au-dessus de tout multiple de la plus grande puissance de 10 (100-399)
3. Fréquence des chiffres dans le reste (400-445, R = 45)
4. Fréquence supplémentaire des TMS dans le reste
5. Compter les zéros en position médiane pour la plage du reste (404, 405...)
6. Soustraire les zéros de tête une seule fois (sur la boucle la plus extérieure)

Answer 2

Je suppose que vous voulez une solution où les nombres sont dans une plage, et vous avez le numéro de début et de fin. Imaginez que vous commenciez par le nombre de départ et que vous comptiez jusqu'à ce que vous atteigniez le nombre de fin - cela pourrait fonctionner, mais ce serait lent. Je pense que l'astuce pour un algorithme rapide est de réaliser que pour augmenter d'un chiffre à la 10^xième place et garder tout le reste inchangé, vous devez utiliser tous les chiffres qui le précèdent 10^x fois plus tous les chiffres 0-9 10^(x-1) fois. (Sauf que votre comptage peut avoir impliqué un report au-delà du xième chiffre - je corrige cela ci-dessous).

Voici un exemple. Disons que vous comptez de 523 à 1004.

• D'abord, vous comptez de 523 à 524. Cela utilise les chiffres 5, 2 et 4 une fois chacun.
• Deuxièmement, comptez de 524 à 604. Le chiffre le plus à droite fait 6 cycles à travers tous les chiffres, vous avez donc besoin de 6 copies de chaque chiffre. Le deuxième chiffre passe par les chiffres 2 à 0, 10 fois chacun. Le troisième chiffre fait 6 fois 5 et 5 fois 100-24.
• Troisièmement, comptez de 604 à 1004. Le chiffre le plus à droite fait 40 cycles, donc ajoutez 40 copies de chaque chiffre. Le deuxième chiffre en partant de la droite fait 4 cycles, donc ajoutez 4 copies de chaque chiffre. Le chiffre le plus à gauche fait 100 de chaque 7, 8 et 9, plus 5 de 0 et 100 - 5 de 6. Le dernier chiffre fait 1 5 fois.

Pour accélérer le dernier point, regardez la partie concernant les deux endroits les plus à droite. Elle utilise chaque chiffre 10 + 1 fois. En général, 1 + 10 + ... + 10^n = (10^(n+1) - 1)/9, ce que nous pouvons utiliser pour accélérer encore plus le comptage.

Mon algorithme consiste à compter depuis le nombre de départ jusqu'au nombre d'arrivée (en utilisant la base 10), mais utilisez le fait ci-dessus pour le faire rapidement. Vous parcourez les chiffres du nombre de départ du moins significatif au plus significatif, et à chaque endroit, vous comptez jusqu'à ce que ce chiffre soit le même que celui du nombre final. À chaque point, n est le nombre de comptages ascendants que vous devez faire avant d'arriver à un report, et m le nombre que vous devez faire après.

Supposons maintenant que le pseudocode compte comme un langage. Voici donc ce que je ferais :

convert start and end numbers to digit arrays start\[\] and end\[\]
create an array counts\[\] with 10 elements which stores the number of copies of
     each digit that you need

iterate through start number from right to left. at the i-th digit,
    let d be the number of digits you must count up to get from this digit
        to the i-th digit in the ending number. (i.e. subtract the equivalent
        digits mod 10)
    add d \* (10^i - 1)/9 to each entry in count.
    let m be the numerical value of all the digits to the right of this digit,
        n be 10^i - m.
    for each digit e from the left of the starting number up to and including the
        i-th digit, add n to the count for that digit.
    for j in 1 to d
        increment the i-th digit by one, including doing any carries
        for each digit e from the left of the starting number up to and including
            the i-th digit, add 10^i to the count for that digit
    for each digit e from the left of the starting number up to and including the
        i-th digit, add m to the count for that digit.
    set the i-th digit of the starting number to be the i-th digit of the ending
        number.

Oh, et puisque la valeur de i augmente de un à chaque fois, gardez la trace de votre ancien 10^i et multipliez-le simplement par 10 pour obtenir le nouveau, au lieu d'exponentialiser à chaque fois.

Answer 3

Pour extraire les chiffres d'un nombre, nous n'aurions besoin que d'une coûteuse conversion de chaîne de caractères si nous ne pouvions pas faire un mod, les chiffres peuvent être poussés plus rapidement d'un nombre comme ceci :

feed=number;
do
{ digit=feed%10;
  feed/=10; 
  //use digit... eg. digitTally[digit]++;
  }
while(feed>0)

Cette boucle devrait être très rapide et peut simplement être placée à l'intérieur d'une boucle des nombres de début et de fin pour la manière la plus simple de compter les chiffres.

Pour aller plus vite, pour une plus grande gamme de nombres, je cherche une méthode optimisée pour comptabiliser tous les chiffres de 0 à nombre*10^significativité. (d'un début à une fin qui m'éblouit)

voici un tableau montrant les chiffres de certains chiffres simples significatifs ces chiffres incluent le 0, mais pas la valeur supérieure elle-même, -c'était un oubli mais c'est peut-être un peu plus facile de voir les modèles (en ayant les chiffres de la valeur supérieure absents ici). Ces décomptes n'incluent pas les zéros de queue,

  1 10 100 1000 10000 2 20 30 40 60 90 200 600 2000  6000

0 1 1  10  190  2890  1  2  3  4  6  9  30 110  490  1690
1 0 1  20  300  4000  1 12 13 14 16 19 140 220 1600  2800
2 0 1  20  300  4000  0  2 13 14 16 19  40 220  600  2800
3 0 1  20  300  4000  0  2  3 14 16 19  40 220  600  2800
4 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
5 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
6 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
7 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
8 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
9 0 1  20  300  4000  0  2  3  4  6  9  40 120  600  1800

edit : clarification de mon original pensées :

de la table de force brute montrant les résultats de 0 (inclus) à poweroTen(notinc) il est visible que un chiffre majuscule de puissance dix :

increments tally[0 to 9] by md*tp*10^(tp-1)
increments tally[1 to md-1] by 10^tp
decrements tally[0] by (10^tp - 10) 
(to remove leading 0s if tp>leadingzeros)
can increment tally[moresignificantdigits] by self(md*10^tp) 
(to complete an effect)

si ces ajustements du pointage étaient appliqués pour chaque chiffre significatif, le décompte devrait être modifié comme s'il était fait de 0 à 1.

les réglages peuvent être inversés pour supprimer la plage précédente (numéro de départ)

Merci Aaronaught pour votre réponse complète et éprouvée.

Answer 4

Voici une très mauvaise réponse, j'ai honte de la poster. J'ai demandé à Mathematica de compter les chiffres utilisés dans tous les nombres de 1 à 1 000 000, sans les 0 en tête. Voici ce que j'ai obtenu :

0   488895
1   600001
2   600000
3   600000
4   600000
5   600000
6   600000
7   600000
8   600000
9   600000

La prochaine fois que vous commanderez des chiffres collants pour les vendre dans votre quincaillerie, commandez dans ces proportions, vous ne vous tromperez pas.

Answer 5

I a posé cette question sur Math Overflow et a reçu une fessée pour avoir posé une question aussi simple. Un des utilisateurs a eu pitié de moi et m'a dit que si je le postais à L'art de résoudre les problèmes Il y répondrait, et c'est ce que j'ai fait.

Voici la réponse qu'il a postée :
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

Je suis embarrassé par le fait que mes connaissances en mathématiques sont insuffisantes pour comprendre ce qu'il a posté (ce type a 19 ans... c'est tellement déprimant). I realmente doivent prendre des cours de maths.

Le bon côté des choses, c'est que l'équation est récursive, donc il devrait être facile de la transformer en une fonction récursive avec quelques lignes de code, par quelqu'un qui comprend les mathématiques.