Wie zählt man die einzelnen Ziffern in einem Bereich von ganzen Zahlen?

Question

Stellen Sie sich vor, Sie verkaufen diese Metallziffern, die zur Nummerierung von Häusern, Schließfächern, Hotelzimmern usw. verwendet werden. Sie müssen herausfinden, wie viele Ziffern Sie versenden müssen, wenn Ihr Kunde Türen/Häuser nummerieren muss:

• 1 bis 100
• 51 bis 300
• 1 bis 2.000 mit Nullen auf der linken Seite

Die offensichtliche Lösung besteht darin, eine Schleife von der ersten bis zur letzten Zahl zu machen, den Zähler in eine Zeichenkette mit oder ohne Nullen links zu konvertieren, jede Ziffer zu extrahieren und sie als Index zu verwenden, um ein Array von 10 Ganzzahlen zu erhöhen.

Ich frage mich, ob es eine bessere Möglichkeit gibt, dieses Problem zu lösen, ohne den gesamten Ganzzahlbereich in einer Schleife durchlaufen zu müssen.

Lösungen in jeder Sprache oder Pseudocode sind willkommen.

---

Editar:

Überprüfung der Antworten
John bei CashCommons y Wayne Conrad dass mein derzeitiger Ansatz gut und schnell genug ist. Lassen Sie mich eine dumme Analogie verwenden: Wenn Sie die Aufgabe bekämen, die Felder eines Schachbretts in weniger als 1 Minute zu zählen, könnten Sie die Aufgabe lösen, indem Sie die Felder einzeln zählen, aber ein mejor Die Lösung besteht darin, die Seiten zu zählen und zu multiplizieren, weil man später vielleicht aufgefordert wird, die Ziegel in einem Gebäude zu zählen.
Alex Reisner weist auf ein sehr interessantes mathematisches Gesetz hin, das leider für dieses Problem nicht relevant zu sein scheint.
Andres schlägt denselben Algorithmus vor, den ich verwende, aber er extrahiert Ziffern mit %10-Operationen anstelle von Teilstrings.
John bei CashCommons y phord Sie schlagen vor, die erforderlichen Ziffern im Voraus zu berechnen und sie in einer Nachschlagetabelle oder, für höhere Geschwindigkeit, in einem Array zu speichern. Dies könnte eine gute Lösung sein, wenn wir einen absoluten, unverrückbaren, in Stein gemeißelten Höchstwert für ganze Zahlen hätten. So etwas habe ich noch nie gesehen.
Leistungsstarke Marke y Schmutzfänger berechnete die benötigten Ziffern für verschiedene Bereiche. Das Ergebnis für eine Million scheint darauf hinzudeuten, dass es ein Verhältnis gibt, aber die Ergebnisse für andere Zahlen zeigen andere Verhältnisse.
Schmutzfänger einige Formeln gefunden, die zum Zählen von Ziffern für Zahlen, die eine Zehnerpotenz sind, verwendet werden können. Robert Harvey hatte eine sehr interessante Erfahrung, als ich die Frage bei MathOverflow stellte. Einer der Mathematiker schrieb eine Lösung in mathematischer Notation.
Aaronaught eine mathematische Lösung entwickelt und getestet. Nach der Veröffentlichung überprüfte er die Formeln aus Math Overflow und fand einen Fehler darin (Hinweis auf Stackoverflow :).
noahlavine einen Algorithmus entwickelt und ihn in Pseudocode dargestellt.

Eine neue Lösung
Nach dem Lesen aller Antworten und einigen Experimenten habe ich herausgefunden, dass für eine Reihe von ganzen Zahlen von 1 bis 10 n -1:

• Für die Ziffern 1 bis 9, n*10 (n-1) Stücke werden benötigt
• Für Ziffer 0, wenn keine führenden Nullen verwendet werden, n*10 n-1 - ((10 n -1) / 9) werden benötigt
• Für die Ziffer 0, bei Verwendung führender Nullen, n*10 n-1 - n benötigt werden

Die erste Formel wurde gefunden durch Schmutzfänger (und wahrscheinlich auch von anderen), und die beiden anderen habe ich durch Ausprobieren gefunden (sie könnten aber auch in anderen Antworten enthalten sein).

Ist beispielsweise n = 6, beträgt der Bereich 1 bis 999.999:

• Für die Ziffern 1 bis 9 benötigen wir 6*10 5 \= 600.000 von jedem
• Für die Ziffer 0, ohne führende Nullen, benötigen wir 6*10 5 - (10 6 -1)/9 = 600,000 - 111,111 = 488,889
• Für die Ziffer 0, mit führenden Nullen, benötigen wir 6*10 5 - 6 = 599,994

Diese Zahlen können überprüft werden mit Leistungsstarke Marke Ergebnisse.

Mit diesen Formeln habe ich den ursprünglichen Algorithmus verbessert. Er geht immer noch von der ersten bis zur letzten Zahl im Bereich der ganzen Zahlen, aber wenn er eine Zahl findet, die eine Zehnerpotenz ist, verwendet er die Formeln, um die Ziffern zu addieren und die Menge für einen vollen Bereich von 1 bis 9 oder 1 bis 99 oder 1 bis 999 usw. zu zählen. Hier ist der Algorithmus in 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

Zum Beispiel wird der Zähler für den Bereich 786 bis 3.021 inkrementiert:

• Um 1 von 786 auf 790 (5 Zyklen)
• Um 9 von 790 auf 799 (1 Zyklus)
• Um 1 von 799 auf 800
• Um 99 von 800 auf 899
• Um 1 von 899 auf 900
• Mit 99 von 900 bis 999
• Um 1 von 999 bis 1000
• Bis 999 von 1000 bis 1999
• Um 1 von 1999 auf 2000
• Bis 999 von 2000 bis 2999
• Um 1 von 2999 auf 3000
• Um 1 von 3000 bis 3010 (10 Zyklen)
• Um 9 von 3010 bis 3019 (1 Zyklus)
• Um 1 von 3019 bis 3021 (2 Zyklen)

Insgesamt: 28 Zyklen Ohne Optimierung: 2.235 Zyklen

Beachten Sie, dass dieser Algorithmus das Problem ohne führende Nullen löst. Um ihn mit führenden Nullen zu verwenden, habe ich einen Hack verwendet:

Wenn ein Bereich von 700 bis 1.000 mit führenden Nullen benötigt wird, verwenden Sie den Algorithmus für 10.700 bis 11.000 und subtrahieren dann 1.000 - 700 = 300 von der Zahl der Ziffer 1.

Benchmark und Quellcode

Ich habe den ursprünglichen Ansatz, den gleichen Ansatz mit %10 und die neue Lösung für einige große Bereiche getestet, mit diesen Ergebnissen:

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

Ein Bildschirmfoto der Benchmark-Anwendung:

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

Wenn Sie den vollständigen Quellcode sehen oder den Benchmark ausführen möchten, verwenden Sie diese Links:

• Vollständiger Quellcode (in Clarion ): http://sca.mx/ftp/countdigits.txt
• Kompilierbares Projekt und Win32-Exe: http://sca.mx/ftp/countdigits.zip

Akzeptierte Antwort

noahlavine Lösung mag richtig sein, aber ich konnte dem Pseudocode einfach nicht folgen, ich denke, es fehlen einige Details oder sind nicht vollständig erklärt.

Aaronaught Lösung scheint richtig zu sein, aber der Code ist für meinen Geschmack einfach zu komplex.

Ich habe angenommen Schmutzfänger Antwort, denn sein Gedankengang hat mich dazu gebracht, diese neue Lösung zu entwickeln.

Answer 1

Es gibt eine klare mathematische Lösung für ein Problem wie dieses. Gehen wir davon aus, dass der Wert auf die maximale Anzahl von Ziffern mit Nullen aufgefüllt wird (was nicht der Fall ist, aber wir werden das später kompensieren), und denken Sie darüber nach:

• Von 0-9, jede Ziffer kommt einmal vor
• Von 0-99 kommt jede Ziffer 20 Mal vor (10x in Position 1 und 10x in Position 2)
• Von 0-999, jede Ziffer kommt 300 Mal vor (100x in P1, 100x in P2, 100x in P3)

Das offensichtliche Muster für jede beliebige Ziffer, wenn der Bereich von 0 bis zu einer Potenz von 10 reicht, ist N * 10 N-1 , wobei N ist die Potenz von 10.

Was ist, wenn der Bereich nicht eine Potenz von 10 ist? Beginnen Sie mit der niedrigsten Potenz von 10 und arbeiten Sie sich dann hoch. Am einfachsten ist es, mit einem Maximum wie 399 zu arbeiten. Wir wissen, dass für jedes Vielfache von 100 jede Ziffer vorkommt mindestens 20-mal, aber wir müssen die Anzahl der Vorkommen an der höchstwertigen Stelle kompensieren, die für die Ziffern 0-3 genau 100 und für alle anderen Ziffern genau null beträgt. Konkret beträgt der zu addierende zusätzliche Betrag 10 N für die entsprechenden Ziffern.

Wenn man dies in eine Formel umsetzt, ergibt sich für Obergrenzen, die um 1 kleiner sind als ein Vielfaches einer Potenz von 10 (z. B. 399, 6999 usw.), folgende Formel: M * N * 10 N-1 + iif(d <= M, 10 N , 0)

Jetzt müssen Sie sich nur noch um den Rest kümmern (den wir als R ). Nehmen wir als Beispiel 445. Dies entspricht dem Ergebnis für 399 plus dem Bereich 400-445. In diesem Bereich tritt der MSD auf R mehr, und alle Ziffern (einschließlich des MSD) treten auch mit der gleichen Häufigkeit auf wie im Bereich [0 - R ].

Jetzt müssen wir nur noch die führenden Nullen ausgleichen. Dieses Muster ist einfach - es ist einfach:

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

Aktualisierung: Bei dieser Version werden die "Auffüllnullen", d. h. die Nullen in den mittleren Positionen, bei der Behandlung des Rests korrekt berücksichtigt ([4 0 0, 4 0 1, 4 0 2, ...]). Das Herausfinden der Auffüllnullen ist ein bisschen hässlich, aber der überarbeitete Code (Pseudocode im C-Stil) kommt damit klar:

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);
}

Wie Sie sehen können, ist es etwas hässlicher geworden, aber es läuft immer noch in O(log n)-Zeit, wenn Sie also Zahlen in Milliardenhöhe verarbeiten müssen, werden Sie damit immer noch schnelle Ergebnisse erhalten :-) Und wenn man es auf den Bereich [0 - 1000000] anwendet, erhält man genau die gleiche Verteilung wie die von High-Performance Mark gepostete, so dass ich mir fast sicher bin, dass es korrekt ist.

Zu Ihrer Information: Der Grund für die inner Variable ist, dass die führende Nullfunktion bereits rekursiv ist, so dass sie nur bei der ersten Ausführung von countdigits .

Update 2: Für den Fall, dass der Code schwer zu lesen ist, finden Sie hier einen Hinweis darauf, was jede Zeile der countdigits return-Anweisung bedeutet (ich habe es mit Inline-Kommentaren versucht, aber die machten den Code noch schwerer zu lesen):

1. Häufigkeit einer beliebigen Ziffer bis zur höchsten Potenz von 10 (0-99, usw.)
2. Häufigkeit des MSD über einem Vielfachen der höchsten Potenz von 10 (100-399)
3. Häufigkeit von beliebigen Ziffern im Rest (400-445, R = 45)
4. Zusätzliche Häufigkeit von EBA im Rest
5. Zählung der Nullen in der mittleren Position für den Restbereich (404, 405...)
6. Führende Nullen nur einmal subtrahieren (in der äußersten Schleife)

Answer 2

Ich gehe davon aus, dass Sie eine Lösung suchen, bei der die Zahlen in einem Bereich liegen und Sie die Anfangs- und Endzahl kennen. Stellen Sie sich vor, Sie beginnen mit der Startzahl und zählen bis zur Endzahl - das würde funktionieren, aber es wäre langsam. Ich denke, der Trick für einen schnellen Algorithmus besteht darin, sich klar zu machen, dass man, um um eine Stelle in der 10^x-Stelle nach oben zu gehen und alles andere gleich zu lassen, alle Ziffern davor 10^x mal plus alle Ziffern 0-9 10^(x-1) mal verwenden muss. (Es sei denn, Sie haben beim Zählen einen Übertrag über die x-te Stelle hinaus gemacht - das korrigiere ich weiter unten).

Hier ist ein Beispiel. Angenommen, du zählst von 523 bis 1004.

• Zunächst zählen Sie von 523 bis 524. Dabei werden die Ziffern 5, 2 und 4 jeweils einmal verwendet.
• Zweitens: Zählen Sie von 524 bis 604. Die Ziffer ganz rechts durchläuft 6 Zyklen durch alle Ziffern, Sie brauchen also 6 Kopien von jeder Ziffer. Die zweite Ziffer durchläuft die Ziffern 2 bis 0, jeweils 10 Mal. Die dritte Ziffer ist 5 mal 6 und 5 mal 100-24.
• Drittens: Zählen Sie von 604 bis 1004. Die Ziffer ganz rechts macht 40 Zyklen, also addiere 40 Kopien jeder Ziffer. Die zweite Ziffer von rechts macht 4 Zyklen, also addiere 4 Kopien von jeder Ziffer. Die Ziffer ganz links macht jeweils 100 von 7, 8 und 9, plus 5 von 0 und 100 - 5 von 6. Die letzte Ziffer ist 5 mal 1.

Um das letzte Stück zu beschleunigen, sehen Sie sich den Teil über die beiden rechten Stellen an. Hier wird jede Ziffer 10 + 1 Mal verwendet. Im Allgemeinen gilt: 1 + 10 + ... + 10^n = (10^(n+1) - 1)/9, was wir nutzen können, um das Zählen noch weiter zu beschleunigen.

Mein Algorithmus besteht darin, von der Startzahl bis zur Endzahl hochzuzählen (unter Verwendung der Basis-10-Zählung), aber die obige Tatsache zu nutzen, um es schnell zu tun. Man durchläuft die Ziffern der Startzahl von der niedrigsten bis zur höchsten Wertigkeit und zählt an jeder Stelle so hoch, dass die betreffende Ziffer dieselbe ist wie die der Endzahl. An jedem Punkt ist n die Anzahl der Aufwärtszählungen, die Sie durchführen müssen, bevor Sie zu einem Übertrag gelangen, und m die Anzahl, die Sie danach durchführen müssen.

Nehmen wir nun an, dass Pseudocode als Sprache zählt. Dann würde ich Folgendes tun:

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, und da der Wert von i jedes Mal um eins zunimmt, behalte deine alten 10^i im Auge und multipliziere sie einfach mit 10, um den neuen Wert zu erhalten, anstatt jedes Mal zu exponentieren.

Answer 3

Um die Ziffern aus einer Zahl abzuspulen, müssten wir immer nur eine teure String-Konvertierung durchführen, wenn wir nicht einen Mod machen könnten, können Ziffern am schnellsten aus einer Zahl wie dieser geschoben werden:

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

Diese Schleife sollte sehr schnell sein und kann einfach in eine Schleife der Start- bis Endnummern eingefügt werden, um die Ziffern auf einfachste Weise zu zählen.

Um schneller zu werden, suche ich für einen größeren Zahlenbereich nach einer optimierten Methode, um alle Ziffern von 0 bis number*10^significance zu zählen (von einem Anfang bis zum Ende verwirrt mich)

Hier ist eine Tabelle mit den Ziffernhöhen einiger einzelner signifikanter Ziffern. diese sind inklusive 0, aber nicht der Spitzenwert selbst, - das war ein Versehen aber es ist vielleicht etwas einfacher, Muster zu erkennen (da die obersten Ziffern hier fehlen) In diesen Tabellen sind die Nullen am Ende nicht enthalten,

  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: Klärung meiner ursprünglichen Gedanken:

aus der Brute-Force-Tabelle mit die Werte von 0 (eingeschlossen) bis poweroTen(notinc) ist ersichtlich, dass eine große Zahl von Zehnerpotenzen:

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)

wenn diese Anpassungen für jede signifikante Ziffer vorgenommen würden, sollte die Zählung so geändert werden, als würde von 0 bis Ende-1 gezählt.

die Einstellungen können invertiert werden, um den vorhergehenden Bereich (Startnummer) zu entfernen

Vielen Dank, Aaronaught, für Ihre vollständige und geprüfte Antwort.

Answer 4

Hier ist eine sehr schlechte Antwort, für die ich mich schäme, sie zu veröffentlichen. Ich habe Mathematica gebeten, die Ziffern zu zählen, die in allen Zahlen von 1 bis 1.000.000 verwendet werden, ohne führende 0s. Hier ist das Ergebnis:

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

Wenn Sie das nächste Mal klebrige Ziffern für den Verkauf in Ihrem Baumarkt bestellen, sollten Sie diese Proportionen einhalten, dann liegen Sie nicht weit daneben.

Answer 5

I fragte diese Frage auf Math Overflow und bekam den Hintern versohlt, weil er eine so einfache Frage gestellt hatte. Einer der Nutzer hatte Mitleid mit mir und sagte, ich solle die Frage an Die Kunst des Problemlösens würde er sie beantworten, und das tat ich auch.

Hier ist die Antwort, die er gepostet hat:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

Peinlicherweise sind meine mathematischen Fähigkeiten unzureichend, um zu verstehen, was er gepostet hat (der Typ ist 19 Jahre alt... das ist so deprimierend). I wirklich Sie müssen ein paar Mathekurse belegen.

Das Gute daran ist, dass die Gleichung rekursiv ist, so dass es ein Leichtes sein sollte, sie mit ein paar Zeilen Code in eine rekursive Funktion umzuwandeln, und zwar von jemandem, der etwas von Mathematik versteht.