如何计算整数范围内的每个数字？ [英] How to count each digit in a range of integers?
问题描述
- 1到100
- 51到300
- 1到2,000左
显而易见的解决方案是执行从第一个到最后一个数字的循环，将计数器转换为带或不带零的字符串在左边，提取每个数字，并使用它作为一个索引来增加一个10整数的数组。
我想知道是否有更好的方法来解决这个问题，
欢迎使用任何语言或伪代码的解决方案。
编辑：
回答查看
John at CashCommons 和 Wayne Conrad 评论说，我目前的方法是好的，足够快。让我使用一个愚蠢的类比：如果你在不到1分钟内完成棋盘上棋盘的计数，你可以通过逐个计算方块来完成任务，但是一个更好解决方案是计算边并做乘法，因为你以后可能会被要求计算建筑物中的砖。
Alex Reisner 指向一个非常有趣的数学法则，不幸的是，这似乎与这个问题不相关。
Andres 建议使用相同的算法，但使用％10操作（而不是子字符串）提取数字。 >
John在CashCommons 和 phord 建议预计算所需的数字，并将它们存储在查找表中，或者对于原始速度，这可能是一个很好的解决方案，如果我们有一个绝对的，不可移动的，设置在石头，最大整数值。我从来没有见过其中之一。
高性能标记和过滤器计算了各种范围所需的数字。一毫米的结果似乎表明有一个比例，但其他数字的结果显示不同的比例。
过滤器发现一些可用于计数数字的公式这是十的幂。
Robert Harvey 在MathOverflow上发表了一个非常有趣的问题。其中一个数学家使用数学符号写了一个解决方案。
Aaronaught 开发并测试了使用数学的解决方案。发布后，他检查了源自数学溢出的公式，并发现了一个缺陷（指向Stackoverflow :)。
noahlavine 开发了一个算法并以伪码形式呈现。
新解决方案
阅读所有答案并进行一些实验后，我发现对于一系列从1到10的整数 n -1：
- 对于数字1到9， （n-1）。
- 对于数字0，如果不使用前导零，n * 10 n-1 n -1）/ 9）
- 对于数字0，如果使用前导零，n * 10 n-1 （可能还有其他人）找到了第一个公式，我发现了第一个公式是由
例如，如果n = 6，范围为1到999,999：
- 对于数字1到9，我们需要6 * 10 5 = 600,000每个
- 对于数字0，没有前导零，我们需要6 * 10 5 - （10 6 -1）/ 9 = 600,000 - 111,111 = 488,889
- 对于数字0，前导零，我们需要6 * 10 5 - 6 = 599,994
这些数字可以使用高性能标记结果来检查。
使用这些公式，我改进了原始算法。它仍然循环从整数范围内的第一个到最后一个数字，但是，如果它找到一个十的幂的数字，它使用公式添加到数字计数数量为1到9的全范围或1到99或1到999等。下面是伪代码中的算法：
integer首先，最后//范围内的第一个和最后一个数字
integer Number //循环中的当前数字
integer power功率是公式中的10 ^ n中的n
整数Nines // Nines是10 ^ n - 1，10 ^ 5 - 1 = 99999
integer前缀//数字中的第一个数字。对于14,200，前缀是142
数组0..9数字//将持有所有数字的计数
FOR数字=第一TO最后
CALL TallyDigitsForOneNumber WITH Number，1 // Tally每个数字的计数
//在数字中增加1
//开始优化。注释是Number = 1,000和Last = 8,000。
Power = Zeros在数字的末尾//对于1,000，Power = 3
如果Power> 0 //数字以0结尾00 000 etc
Nines = 10 ^ Power-1 / / Nines = 10 ^ 3 - 1 = 1000 - 1 = 999
如果Number + Nines< = Last // If 1,000 + 999< 8,000，添加一整套
数字[0-9] + =功率* 10 ^（电源-1）//添加3 * 10 ^（3-1）= 300到数字0到9
数字[0] - = -Power //调整数字0（前导零公式）
前缀=数字的第一个数字//对于1000，前缀是1
CALL TallyDigitsForOneNumber WITH Prefix，Nines // Tally计数每个
//前缀中的数字，
//增加999
Number + = Nines //递增循环计数器999个循环
ENDIF
ENDIF
//优化结束
ENDFOR
SUBROUTINE TallyDigitsForOneNumber PARAMS编号，计数
REPEAT
数字[数字％10] + =计数
编号=数字/ 10
UNTIL数字= 0
例如，对于范围786到3,021，计数器将递增： p>
- 由786到790（5个周期）的1个
- 从790到799 ） 到900
- 从99到999
- 从1到999到
- 1000到1999年
- 从1999年到2000年1年
- 从2000年到2999年由999年
- 从2999到3000
- 从3000到3010的1（10个周期）
- 从3010到3019
- 从3019到3021（2个周期）中的1个
总共：28个周期
：2,235个周期
请注意，此算法解决了没有前导零的问题。要使用它与前导零，我使用一个hack：
如果需要范围700到1,000带前导零，请使用算法为10,700到11,000，然后从数字1的计数中减去1000 - 700 = 300。
基准和源代码
我测试了原来的方法，同样的方法使用％10和一些大范围的新解决方案，结果如下：
原始104.78秒
％10 83.66
具有十的权力0.07
基准测试应用程序的屏幕截图：
如果您想查看完整的源代码或运行基准测试，请使用以下链接：
- 完成源代码（在 Clarion 中）： http://sca.mx/ftp/countdigits.txt
- 可编译project和win32 exe： http://sca.mx/ftp/countdigits.zip li>
接受的答案
noahlavine 解决方案可能是正确的，但我只是不能跟随伪代码，我想有一些细节缺失或没有完全解释。
解决方案似乎是正确的，但是代码对我来说太复杂了。
我接受了
过滤器的回答，因为他的思路指导我开发这个新的解决方案。解决方案要从一个数字卷数字，我们只需要做一个昂贵的字符串转换，如果我们不能做一个mod，数字可以最快按下这样的数字：
feed = number;
do
{digit = feed％10;
feed / = 10;
//使用数字... eg。 digitTally [digit] ++;
}
while（feed> 0）
为了加快速度，对于更大的数字范围，im look一个优化的方法来统计从0到数字的所有数字* 10 ^的意义
（从开始到结束bazzogles我）
这里是一个表显示数字一些单个有效数字的计数。
这些都包括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
编辑：清除我的原始
思考：
从强力表中显示
ties从0（包含）到
poweroTen（notinc） $ ba majordigit of tenpower：
通过md * tp增加tally [0到9] 10 ^（tp-1）
将计数[1到md-1]递增10 ^ tp
将计数[0]递减（10 ^ tp - 10）
如果tp> leadingzeros）
可以通过self（md * 10 ^ tp）
（以完成效果）增加计数[moresignificantdigits]
如果对每个有效数字应用这些提示调整，则
应该将提示修改为从0到end-1。
$ b感谢Aaronaught为您提供完整且经过测试的答案。
$ b bImagine you sell those metallic digits used to number houses, locker doors, hotel rooms, etc. You need to find how many of each digit to ship when your customer needs to number doors/houses:
- 1 to 100
- 51 to 300
- 1 to 2,000 with zeros to the left
The obvious solution is to do a loop from the first to the last number, convert the counter to a string with or without zeros to the left, extract each digit and use it as an index to increment an array of 10 integers.
I wonder if there is a better way to solve this, without having to loop through the entire integers range.
Solutions in any language or pseudocode are welcome.
Edit:
Answers review
John at CashCommons and Wayne Conrad comment that my current approach is good and fast enough. Let me use a silly analogy: If you were given the task of counting the squares in a chess board in less than 1 minute, you could finish the task by counting the squares one by one, but a better solution is to count the sides and do a multiplication, because you later may be asked to count the tiles in a building.
Alex Reisner points to a very interesting mathematical law that, unfortunately, doesn’t seem to be relevant to this problem.
Andres suggests the same algorithm I’m using, but extracting digits with %10 operations instead of substrings.
John at CashCommons and phord propose pre-calculating the digits required and storing them in a lookup table or, for raw speed, an array. This could be a good solution if we had an absolute, unmovable, set in stone, maximum integer value. I’ve never seen one of those.
High-Performance Mark and strainer computed the needed digits for various ranges. The result for one millon seems to indicate there is a proportion, but the results for other number show different proportions.
strainer found some formulas that may be used to count digit for number which are a power of ten. Robert Harvey had a very interesting experience posting the question at MathOverflow. One of the math guys wrote a solution using mathematical notation.
Aaronaught developed and tested a solution using mathematics. After posting it he reviewed the formulas originated from Math Overflow and found a flaw in it (point to Stackoverflow :).
noahlavine developed an algorithm and presented it in pseudocode.A new solution
After reading all the answers, and doing some experiments, I found that for a range of integer from 1 to 10n-1:- For digits 1 to 9, n*10(n-1) pieces are needed
- For digit 0, if not using leading zeros, n*10n-1 - ((10n-1) / 9) are needed
- For digit 0, if using leading zeros, n*10n-1 - n are needed
The first formula was found by strainer (and probably by others), and I found the other two by trial and error (but they may be included in other answers).
For example, if n = 6, range is 1 to 999,999:
- For digits 1 to 9 we need 6*105 = 600,000 of each one
- For digit 0, without leading zeros, we need 6*105 – (106-1)/9 = 600,000 - 111,111 = 488,889
- For digit 0, with leading zeros, we need 6*105 – 6 = 599,994
These numbers can be checked using High-Performance Mark results.
Using these formulas, I improved the original algorithm. It still loops from the first to the last number in the range of integers, but, if it finds a number which is a power of ten, it uses the formulas to add to the digits count the quantity for a full range of 1 to 9 or 1 to 99 or 1 to 999 etc. Here's the algorithm 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 = 0For example, for range 786 to 3,021, the counter will be incremented:
- By 1 from 786 to 790 (5 cycles)
- By 9 from 790 to 799 (1 cycle)
- By 1 from 799 to 800
- By 99 from 800 to 899
- By 1 from 899 to 900
- By 99 from 900 to 999
- By 1 from 999 to 1000
- By 999 from 1000 to 1999
- By 1 from 1999 to 2000
- By 999 from 2000 to 2999
- By 1 from 2999 to 3000
- By 1 from 3000 to 3010 (10 cycles)
- By 9 from 3010 to 3019 (1 cycle)
- By 1 from 3019 to 3021 (2 cycles)
Total: 28 cycles Without optimization: 2,235 cycles
Note that this algorithm solves the problem without leading zeros. To use it with leading zeros, I used a hack:
If range 700 to 1,000 with leading zeros is needed, use the algorithm for 10,700 to 11,000 and then substract 1,000 - 700 = 300 from the count of digit 1.
Benchmark and Source code
I tested the original approach, the same approach using %10 and the new solution for some large ranges, with these results:
Original 104.78 seconds With %10 83.66 With Powers of Ten 0.07
A screenshot of the benchmark application:
If you would like to see the full source code or run the benchmark, use these links:
- Complete Source code (in Clarion): http://sca.mx/ftp/countdigits.txt
- Compilable project and win32 exe: http://sca.mx/ftp/countdigits.zip
Accepted answer
noahlavine solution may be correct, but l just couldn’t follow the pseudo code, I think there are some details missing or not completely explained.
Aaronaught solution seems to be correct, but the code is just too complex for my taste.
I accepted strainer’s answer, because his line of thought guided me to develop this new solution.
解决方案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:
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)
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,
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 1800edit: 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:
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
the adjustments can be inverted to remove preceeding range (start number)
Thanks Aaronaught for your complete and tested answer.
这篇关于如何计算整数范围内的每个数字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
