如何计算一个整数范围内的每个数字?-Howtocounteachdigitinarangeofintegers?

5  

To reel of the digits from a number, we'd only ever need to do a costly string conversion if we couldnt do a mod, digits can most quickly be pushed of a number like this:

要从一个数字中记录数字，我们只需要做一个代价昂贵的字符串转换，如果我们不能做一个mod，数字可以最快的被这样的数字推动:

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

that loop should be very fast and can just be placed inside a loop of the start to end numbers for the simplest way to tally the digits.

这个循环应该是非常快的，并且可以被放置在一个循环中，以最简单的方式来计算数字。

To go faster, for larger range of numbers, im looking for an optimised method of tallying all digits from 0 to number*10^significance (from a start to end bazzogles me)

更快,更大范围的数字,我寻找一个优化的方法计算所有数字从0到数量* 10 ^意义(从开始到结束bazzogles我)

here is a table showing digit tallies of some single significant digits.. these are inclusive of 0, but not the top value itself, -that was an oversight but its maybe a bit easier to see patterns (having the top values digits absent here) These tallies dont include trailing zeros,

这里有一张表显示了一些个位数的数字。这些都包含0，但不是最大值本身，这是一个疏忽，但它可能更容易看到模式(这里不包括上面的值)这些数据不包括尾随零，

  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: clearing up my origonal thoughts:

编辑:整理我的原始想法:

from the brute force table showing tallies from 0 (included) to poweroTen(notinc) it is visible that a majordigit of tenpower:

从蛮力表中可以看出，从0(包括)到poweroTen(notinc)，可以看到一个主要的tenpower数字:

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)

if these tally adjustments were applied for each significant digit, the tally should be modified as though counted from 0 to end-1

如果对每一个有效数字都应用了这些计数调整，则应该将计数从0到end 1进行修改。

the adjustments can be inverted to remove preceeding range (start number)

调整可以倒转以移走之前的范围(开始数)

Thanks Aaronaught for your complete and tested answer.

感谢Aaronaught的完整和测试的答案。

10  

There's a clear mathematical solution to a problem like this. Let's assume the value is zero-padded to the maximum number of digits (it's not, but we'll compensate for that later), and reason through it:

对于这样的问题，有一个清晰的数学解决方案。让我们假设这个值是零填充到最大位数(它不是，但是我们稍后会补偿)，以及通过它的原因:

• From 0-9, each digit occurs once
• 从0到9，每个数字出现一次。
• From 0-99, each digit occurs 20 times (10x in position 1 and 10x in position 2)
• 从0-99，每一个数字出现20次(10x在位置1和10x在位置2)
• From 0-999, each digit occurs 300 times (100x in P1, 100x in P2, 100x in P3)
• 从0-999，每一个数字出现300次(100x在P1, 100x在P2, 100x在P3)

The obvious pattern for any given digit, if the range is from 0 to a power of 10, is N * 10^N-1, where N is the power of 10.

任何给定数字的明显模式，如果取值范围是从0到10的幂，就是N * 10N-1，其中N是10的幂。

What if the range is not a power of 10? Start with the lowest power of 10, then work up. The easiest case to deal with is a maximum like 399. We know that for each multiple of 100, each digit occurs at least 20 times, but we have to compensate for the number of times it appears in the most-significant-digit position, which is going to be exactly 100 for digits 0-3, and exactly zero for all other digits. Specifically, the extra amount to add is 10^N for the relevant digits.

如果范围不是10的幂呢?从10的最低能量开始，然后向上运动。最简单的例子是399。我们知道，对于每100个倍数，每一个数字至少出现20次，但我们必须补偿它出现在最重要的位置上的次数，这个位置恰好是0-3的100，而所有其他的数字正好是0。具体来说，添加的额外数量是10N的相关数字。

Putting this into a formula, for upper bounds that are 1 less than some multiple of a power of 10 (i.e. 399, 6999, etc.) it becomes: M * N * 10^N-1 + iif(d <= M, 10^N, 0)

将其放入公式中，上界小于10的倍数(即399,6999，等等)它变成:M * N * 10N-1 + iif(d <= M, 10N, 0)

Now you just have to deal with the remainder (which we'll call R). Take 445 as an example. This is whatever the result is for 399, plus the range 400-445. In this range, the MSD occurs R more times, and all digits (including the MSD) also occur at the same frequencies they would from range [0 - R].

现在你只需要处理剩下的部分(我们称之为R)，以445为例。这是399的结果，加上400-445的范围。在这个范围内，MSD发生R次，所有的数字(包括MSD)也发生在相同频率范围内[0 - R]。

Now we just have to compensate for the leading zeros. This pattern is easy - it's just:

现在我们只需要补偿前导零。这个模式很简单——只是:

10^N + 10^N-1 + 10^N-2 + ... + **10⁰

10N + 10N-1 + 10N-2 +…+ * * 100

Update: This version correctly takes into account "padding zeros", i.e. the zeros in middle positions when dealing with the remainder ([400, 401, 402, ...]). Figuring out the padding zeros is a bit ugly, but the revised code (C-style pseudocode) handles it:

更新:这个版本正确地考虑了“填充零”，即在处理剩余部分时中间位置的零([400,401,402，…])。计算填充0是有点难看，但是修改后的代码(C-style伪代码)处理它:

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

As you can see, it's gotten a bit uglier but it still runs in O(log n) time, so if you need to handle numbers in the billions, this will still give you instant results. :-) And if you run it on the range [0 - 1000000], you get the exact same distribution as the one posted by High-Performance Mark, so I'm almost positive that it's correct.

正如你所看到的，它变得更难看了，但是它仍然运行在O(log n)的时间里，所以如果你需要处理数十亿的数字，这仍然会给你即时的结果。如果你在[0 - 1000000]范围内运行它，你得到的分布和高性能标记的分布完全相同，所以我几乎肯定它是正确的。

FYI, the reason for the inner variable is that the leading-zero function is already recursive, so it can only be counted in the first execution of countdigits.

FYI，内部变量的原因是导零函数已经是递归的，所以只能在第一次执行count位数时进行计数。

Update 2: In case the code is hard to read, here's a reference for what each line of the countdigits return statement means (I tried inline comments but they made the code even harder to read):

更新2:如果代码很难读，这里是对count位数返回语句的每一行的引用(我尝试了内联注释，但是它们使代码更难读):

1. Frequency of any digit up to highest power of 10 (0-99, etc.)
2. 最高功率为10(0-99，等等)的频率。
3. Frequency of MSD above any multiple of highest power of 10 (100-399)
4. MSD频率高于10(100-399)的最高倍数
5. Frequency of any digits in remainder (400-445, R = 45)
6. 其余数字的频率(400-445,R = 45)
7. Additional frequency of MSD in remainder
8. 剩余的MSD频率。
9. Count zeros in middle position for remainder range (404, 405...)
10. 在剩余范围(404,405…)的中间位置数0。
11. Subtract leading zeros only once (on outermost loop)
12. 只将前导零减去一次(在最外层循环)

8  

I'm assuming you want a solution where the numbers are in a range, and you have the starting and ending number. Imagine starting with the start number and counting up until you reach the end number - it would work, but it would be slow. I think the trick to a fast algorithm is to realize that in order to go up one digit in the 10^x place and keep everything else the same, you need to use all of the digits before it 10^x times plus all digits 0-9 10^(x-1) times. (Except that your counting may have involved a carry past the x-th digit - I correct for this below.)

我假设你想要一个解，其中的数字在一个范围内，你有开始和结束的数字。想象一下从开始数开始，然后数到最后的数字——它会起作用，但它会很慢。我认为快速算法的技巧是意识到为了上一位在10 ^ x的地方,保持一切一样,您需要使用所有的数字之前10 ^ x * +数字0 - 9 10 ^(x - 1)。(除了你的计数可能涉及到超过第x位的数字-我在下面是正确的。)

Here's an example. Say you're counting from 523 to 1004.

这是一个例子。比如从523到1004。

• First, you count from 523 to 524. This uses the digits 5, 2, and 4 once each.
• 首先，从523到524。它使用数字5、2和4。
• Second, count from 524 to 604. The rightmost digit does 6 cycles through all of the digits, so you need 6 copies of each digit. The second digit goes through digits 2 through 0, 10 times each. The third digit is 6 5 times and 5 100-24 times.
• 第二，从524到604。最右边的数字做了6个周期的所有数字，所以你需要6个数字的拷贝。第二个数字通过数字2到0，每一个10次。第三位是6 5乘以5 100-24。
• Third, count from 604 to 1004. The rightmost digit does 40 cycles, so add 40 copies of each digit. The second from right digit doers 4 cycles, so add 4 copies of each digit. The leftmost digit does 100 each of 7, 8, and 9, plus 5 of 0 and 100 - 5 of 6. The last digit is 1 5 times.
• 第三，从604到1004。最右边的数字是40个周期，所以每个数字加40个。第二个来自右数字的实施者4个周期，所以每个数字加4个副本。最左边的数字是每7个，8个，9个，加上5个0和100 - 5个6。最后一个数字是1 5乘以。

To speed up the last bit, look at the part about the rightmost two places. It uses each digit 10 + 1 times. In general, 1 + 10 + ... + 10^n = (10^(n+1) - 1)/9, which we can use to speed up counting even more.

为了加快最后一点，看看最右边两个地方的部分。它使用每个数字10 + 1次。一般来说，1 + 10 +…+ 10 n = (10 (n+1) - 1)/9，我们可以用它来加快计数。

My algorithm is to count up from the start number to the end number (using base-10 counting), but use the fact above to do it quickly. You iterate through the digits of the starting number from least to most significant, and at each place you count up so that that digit is the same as the one in the ending number. At each point, n is the number of up-counts you need to do before you get to a carry, and m the number you need to do afterwards.

我的算法是从开始数到最终数(使用base-10计数)，但是使用上面的事实来快速完成它。你遍历起始数的数字，从最小到最重要的，在每一个地方都加起来，使这个数字与结尾数字中的数字相同。在每一个点上，n是在你到达一个进位之前需要做的向上计数的数量，而m是你以后需要做的数字。

Now let's assume pseudocode counts as a language. Here, then, is what I would do:

现在让我们假设伪代码是一种语言。在这里，我要做的是:

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, and since the value of i increases by one each time, keep track of your old 10^i and just multiply it by 10 to get the new one, instead of exponentiating each time.

哦，因为我每次都加1，所以要跟踪你的老10，我把它乘以10得到新的，而不是每次取幂。

6  

Here's a very bad answer, I'm ashamed to post it. I asked Mathematica to tally the digits used in all numbers from 1 to 1,000,000, no leading 0s. Here's what I got:

这是一个很糟糕的回答，我很不好意思张贴出来。我要求Mathematica将所有数字中使用的数字从1到100万不等，而不是0。这是我得到的答案:

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

Next time you're ordering sticky digits for selling in your hardware store, order in these proportions, you won't be far wrong.

下次当你在你的五金店订购粘性数字时，按这些比例排序，你就不会错了。

5  

I asked this question on Math Overflow, and got spanked for asking such a simple question. One of the users took pity on me and said if I posted it to The Art of Problem Solving, he would answer it; so I did.

我问了这个关于数学溢出的问题，并因为问了这么简单的问题而被打了屁股。有一个用户很同情我，说如果我把它贴在解决问题的艺术上，他会回答的;所以我所做的。

Here is the answer he posted:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

以下是他发布的答案:http://www.artofproblem solving.com/forum/viewtopic.php?

Embarrassingly, my math-fu is inadequate to understand what he posted (the guy is 19 years old...that is so depressing). I really need to take some math classes.

令人尴尬的是，我的数学老师不太懂他的帖子(那家伙19岁了……)这是如此令人沮丧)。我真的需要上一些数学课。

On the bright side, the equation is recursive, so it should be a simple matter to turn it into a recursive function with a few lines of code, by someone who understands the math.

在好的方面，这个等式是递归的，所以应该是一个简单的问题，用几行代码把它变成递归函数，由理解数学的人来做。

3  

Your approach is fine. I'm not sure why you would ever need anything faster than what you've described.

你的方法很好。我不知道为什么你需要比你描述的更快的东西。

Or, this would give you an instantaneous solution: Before you actually need it, calculate what you would need from 1 to some maximum number. You can store the numbers needed at each step. If you have a range like your second example, it would be what's needed for 1 to 300, minus what's needed for 1 to 50.

或者，这将给你一个瞬时解:在你实际需要它之前，计算你需要从1到某个最大值。您可以存储每个步骤所需的数字。如果你有一个像你的第二个例子的范围，它将是需要的1到300，减去需要的1到50。

Now you have a lookup table that can be called at will. Doing up to 10,000 would only take a few MB and, what, a few minutes to compute, once?

现在您有一个可以随意调用的查找表。达到10,000只需要几MB，几分钟就可以计算一次?

3  

I know this question has an accepted answer but I was tasked with writing this code for a job interview and I think I came up with an alternative solution that is fast, requires no loops and can use or discard leading zeroes as required.

我知道这个问题有一个被接受的答案，但我的任务是写这段代码来进行工作面试，我想我找到了一个快速的替代方案，不需要循环，可以根据需要使用或丢弃前导零。

It is in fact quite simple but not easy to explain.

这其实很简单，但很难解释。

If you list out the first n numbers

如果你列出了第一个n个数字。

     1
     2
     3

     .
     .
     .


     9
    10
    11

It is usual to start counting the digits required from the start room number to the end room number in a left to right fashion, so for the above we have one 1, one 2, one 3 ... one 9, two 1's one zero, four 1's etc. Most solutions I have seen used this approach with some optimisation to speed it up.

通常开始计算从起始房间号到结束房间号所需的数字，从左到右的方式，所以上面我们有一个1，一个2，一个3…一个9，两个1，一个0，四个1等等，我看到的大多数解决方案都用这个方法来优化它。

What I did was to count vertically in columns, as in hundreds, tens, and units. You know the highest room number so we can calculate how many of each digit there are in the hundreds column via a single division, then recurse and calculate how many in the tens column etc. Then we can subtract the leading zeros if we like.

我所做的是垂直地计算列数，如在百位、十位和单位中。你知道最高的房间号，这样我们就可以计算出每一个数字有多少是通过一个除法来计算的，然后递归算出十位上的数，然后我们可以减去前导零。

Easier to visualize if you use Excel to write out the numbers but use a separate column for each digit of the number

如果你用Excel来写数字，但要用一个单独的列来表示数字的每一个数字，就更容易理解了。

     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

So if the highest room number is 671 the hundreds column will have 100 zeroes vertically, followed by 100 ones and so on up to 71 sixes, ignore 100 of the zeroes if required as we know these are all leading.

所以，如果最高的房间号是671，那么几百列就会垂直地有100个0，然后是100个0，那么就有71个6，如果需要的话，忽略100个0，因为我们知道这些都是领先的。

Then recurse down to the tens and perform the same operation, we know there will be 10 zeroes followed by 10 ones etc, repeated six times, then the final time down to 2 sevens. Again can ignore the first 10 zeroes as we know they are leading. Finally of course do the units, ignoring the first zero as required.

然后递归到十位上，执行相同的操作，我们知道会有10个0，然后是10个，重复6次，然后最后一次降到2个7。同样可以忽略前10个0，因为我们知道它们是领先的。最后当然是单位，忽略第一个0。

So there are no loops everything is calculated with division. I use recursion for travelling "up" the columns until the max one is reached (in this case hundreds) and then back down totalling as it goes.

所以没有循环，所有的都是用除法计算的。我使用递归来“向上”行“向上”的列，直到到达最大的列(在这个例子中是数百)，然后按它的方式返回。

I wrote this in C# and can post code if anyone interested, haven't done any benchmark timings but it is essentially instant for values up to 10^18 rooms.

我写这个在c#和邮政编码如果有人感兴趣,没做任何基准时间但它本质上是即时值10 ^ 18个房间。

Could not find this approach mentioned here or elsewhere so thought it might be useful for someone.

在这里或其他地方找不到这种方法，所以认为它可能对某些人有用。

1  

This doesn't answer your exact question, but it's interesting to note the distribution of first digits according to Benford's Law. For example, if you choose a set of numbers at random, 30% of them will start with "1", which is somewhat counter-intuitive.

这并不能回答你的问题，但有趣的是，根据本福德定律，第一个数字的分布是很有趣的。例如，如果你随机选择一组数字，其中的30%将以“1”开头，这有点违反直觉。

I don't know of any distributions describing subsequent digits, but you might be able to determine this empirically and come up with a simple formula for computing an approximate number of digits required for any range of numbers.

我不知道有什么分布描述了后来的数字，但是你可能可以根据经验来确定这一点，并给出一个简单的公式来计算任意数量的数字所需的近似数字。

1  

If "better" means "clearer," then I doubt it. If it means "faster," then yes, but I wouldn't use a faster algorithm in place of a clearer one without a compelling need.

如果“更好”的意思是“更清楚”，那我就怀疑了。如果它的意思是“更快”，那么是的，但是我不会使用一个更快的算法来代替一个更清晰的算法，而不需要一个令人信服的需求。

#!/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, a language known to be "dog slow," runs the above code in 0.135 seconds. That includes loading the interpreter. Don't give up an obvious algorithm unless you need more speed.

Ruby 1.8，一种被称为“dog slow”的语言，在0.135秒内运行上述代码。这包括加载解释器。除非你需要更多的速度，否则不要放弃一个明显的算法。

1  

If you need raw speed over many iterations, try a lookup table:

如果在许多迭代中需要原始速度，可以尝试查找表:

1. Build an array with 2 dimensions: 10 x max-house-number
2. 构建一个包含两个维度的数组:10 x max-house-number。

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

2. Fill each row with the count of digits required to get to that number from zero.
   Hint: Use the previous row as a start:
3. 在每一行中填入从0到这个数字所需的位数。提示:使用前一行作为开始:

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

       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.

0  

You can separate each digit (look here for a example), create a histogram with entries from 0..9 (which will count how many digits appeared in a number) and multiply by the number of 'numbers' asked.

您可以将每个数字分开(看这里的例子)，创建一个带有从0到的条目的直方图。9(它会计算一个数字中出现了多少个数字)，然后乘以“数字”的个数。

But if isn't what you are looking for, can you give a better example?

但如果不是你想要的，你能举一个更好的例子吗?

Edited:

编辑:

Now I think I got the problem. I think you can reckon this (pseudo C):

现在我想我有问题了。我认为你可以估计这个(伪C):

int histogram[10];
memset(histogram, 0, sizeof(histogram));

for(i = startNumber; i <= endNumber; ++i)
{
    array = separateDigits(i);
    for(j = 0; k 

histogram[0] == total of zeros
histogram[1] == total of ones