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

Ich weiß, dass diese Frage eine akzeptierte Antwort hat, aber ich wurde mit dem Schreiben dieses Codes für ein Vorstellungsgespräch beauftragt, und ich glaube, ich habe eine alternative Lösung gefunden, die schnell ist, keine Schleifen erfordert und führende Nullen je nach Bedarf verwenden oder verwerfen kann.

Es ist eigentlich ganz einfach, aber nicht leicht zu erklären.

Wenn Sie die ersten n Zahlen auflisten

     1
     2
     3

     .
     .
     .

     9
    10
    11

Üblicherweise beginnt man mit der Zählung der erforderlichen Ziffern von der Anfangsraumnummer bis zur Endraumnummer von links nach rechts, also eine 1, eine 2, eine 3 ... eine 9, zwei 1en, eine Null, vier 1en usw. Die meisten Lösungen, die ich gesehen habe, verwenden diesen Ansatz mit einigen Optimierungen, um das Ganze zu beschleunigen.

Ich habe senkrecht in Spalten gezählt, wie bei Hundertern, Zehnern und Einer. Sie kennen die höchste Raumnummer, so dass wir durch einfache Division berechnen können, wie viele Ziffern in der Hunderter-Spalte stehen, dann rekursieren und berechnen, wie viele in der Zehner-Spalte stehen usw. Dann können wir die führenden Nullen abziehen, wenn wir wollen.

Es ist einfacher zu visualisieren, wenn Sie die Zahlen in Excel ausschreiben und für jede Ziffer der Zahl eine eigene Spalte verwenden.

     A    B    C
     -    -    -
     0    0    1  (assuming room numbers do not start at zero)
     0    0    2
     0    0    3
     .
     .
     .
     3    6    4
     3    6    5
     .
     .
     .

     6    6    9
     6    7    0
     6    7    1

     ^
     sum in columns not rows

Wenn also die höchste Raumnummer 671 ist, enthält die Hunderterspalte 100 Nullen in vertikaler Richtung, gefolgt von 100 Einsen und so weiter bis zu 71 Sechsen, wobei 100 der Nullen bei Bedarf ignoriert werden können, da wir wissen, dass sie alle führend sind.

Dann rekursiert man bis zu den Zehnerstellen und führt die gleiche Operation durch. Wir wissen, dass es 10 Nullen gefolgt von 10 Einsen usw. geben wird, was sechsmal wiederholt wird, und dann das letzte Mal bis zu 2 Siebenern. Auch hier können wir die ersten 10 Nullen ignorieren, da wir wissen, dass sie führend sind. Zum Schluss natürlich die Einheiten, wobei die erste Null ignoriert wird, wie erforderlich.

Es gibt also keine Schleifen, alles wird durch Division berechnet. Ich verwende Rekursion für die Reise "up" die Spalten, bis die maximale erreicht ist (in diesem Fall Hunderte) und dann wieder nach unten Summen, wie es geht.

Ich schrieb dies in C# und kann Code posten, wenn jemand interessiert ist, habe keine Benchmark-Timings durchgeführt, aber es ist im Wesentlichen sofort für Werte bis zu 10^18 Zimmer.

Ich konnte nicht finden, dass dieser Ansatz hier oder anderswo erwähnt wurde und dachte, er könnte für jemanden nützlich sein.

Answer 2

Ihr Ansatz ist gut. Ich bin mir nicht sicher, warum Sie jemals etwas Schnelleres als das, was Sie beschrieben haben, benötigen würden.

Oder Sie erhalten eine sofortige Lösung: Berechnen Sie vor dem tatsächlichen Bedarf, was Sie von 1 bis zu einer bestimmten Höchstzahl benötigen würden. Sie können die benötigten Zahlen für jeden Schritt speichern. Wenn Sie einen Bereich wie in Ihrem zweiten Beispiel haben, wäre das, was für 1 bis 300 benötigt wird, minus dem, was für 1 bis 50 benötigt wird.

Jetzt haben Sie eine Nachschlagetabelle, die Sie nach Belieben aufrufen können. Die Berechnung von bis zu 10.000 Daten würde nur ein paar MB und ein paar Minuten in Anspruch nehmen, einmalig?

Answer 3

Dies beantwortet zwar nicht genau Ihre Frage, aber es ist interessant, die Verteilung der ersten Ziffern nach Benfordsches Gesetz . Wenn man zum Beispiel eine Reihe von Zahlen zufällig auswählt, beginnen 30 % davon mit einer "1", was etwas kontraintuitiv ist.

Mir sind keine Verteilungen bekannt, die die nachfolgenden Ziffern beschreiben, aber vielleicht können Sie dies empirisch ermitteln und eine einfache Formel zur Berechnung einer Ungefähr Anzahl der für einen beliebigen Zahlenbereich erforderlichen Ziffern.

Answer 4

Wenn "besser" "klarer" bedeutet, dann bezweifle ich es. Wenn es "schneller" bedeutet, dann ja, aber ich würde ohne zwingenden Grund keinen schnelleren Algorithmus anstelle eines klareren verwenden.

#!/usr/bin/ruby1.8

def digits_for_range(min, max, leading_zeros)
  bins = [0] * 10
  format = [
    '%',
    ('0' if leading_zeros),
    max.to_s.size,
    'd',
  ].compact.join
  (min..max).each do |i|
    s = format % i
    for digit in s.scan(/./)
      bins[digit.to_i] +=1  unless digit == ' '
    end
  end
  bins
end

p digits_for_range(1, 49, false) 
# => [4, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 49, true)
# => [13, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 10000, false)
# => [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]

Ruby 1.8, eine Sprache, die dafür bekannt ist, "hundemüde" zu sein, führt den obigen Code in 0,135 Sekunden aus. Das schließt das Laden des Interpreters ein. Geben Sie einen offensichtlichen Algorithmus nicht auf, es sei denn, Sie brauchen mehr Geschwindigkeit.

Answer 5

Wenn Sie eine hohe Geschwindigkeit bei vielen Iterationen benötigen, sollten Sie eine Nachschlagetabelle verwenden:

1. Erstellen Sie ein Array mit 2 Dimensionen: 10 x maximale Hausnummer

   int nDigits[10000][10] ;   // Don't try this on the stack, kids!

2. Füllen Sie jede Zeile mit der Anzahl der Ziffern, die erforderlich sind, um von Null auf diese Zahl zu kommen.
   Tipp: Verwenden Sie die vorherige Reihe als Ausgangspunkt:

   n=0..9999:
      if (n>0) nDigits[n] = nDigits[n-1]
      d=0..9:
          nDigits[n][d] += countOccurrencesOf(n,d)   // 

`

3. Number of digits "between" two numbers becomes simple subtraction.

`

       For range=51 to 300, take the counts for 300 and subtract the counts for 50.
       0's = nDigits[300][0] - nDigits[50][0]
       1's = nDigits[300][1] - nDigits[50][1]
       2's = nDigits[300][2] - nDigits[50][2]
       3's = nDigits[300][3] - nDigits[50][3]
       etc.