想象一下，您出售用于对房屋、储物柜门、酒店房间等进行编号的金属数字。当您的客户需要对门/房屋进行编号时，您需要找出每个数字中要运送的数量：
- 1 到 100
- 51 至 300
- 1 到 2,000，左边有零
显而易见的解决方案是从第一个数字到最后一个数字进行循环，将计数器转换为左侧有或没有零的字符串，提取每个数字并将其用作索引以增加 10 个整数的数组。
我想知道是否有更好的方法来解决这个问题，而不必遍历整个整数范围。
欢迎使用任何语言或伪代码的解决方案。
编辑：
答案
是 CashCommons 的 John和Wayne Conrad评论说我目前的方法足够好且足够快。让我用一个愚蠢的类比：如果你被要求在不到 1 分钟的时间内计算棋盘中的方格，你可以通过一个一个地计算方格来完成任务，但更好的解决方案是数边数和做乘法，因为稍后可能会要求您计算建筑物中的瓷砖。
Alex Reisner指出了一个非常有趣的数学定律，不幸的是，它似乎与这个问题无关。
Andres建议使用我正在使用的相同算法，但使用 %10 操作而不是子字符串来提取数字。
约翰在 CashCommons和phord建议预先计算所需的数字并将它们存储在查找表中，或者为了原始速度，存储在一个数组中。如果我们有一个绝对的、不可移动的、一成不变的最大整数值，这可能是一个很好的解决方案。我从未见过其中之一。
高性能标记 和过滤器计算了各种范围所需的数字。一百万的结果似乎表明有一个比例，但其他数字的结果显示出不同的比例。
过滤器发现了一些可用于计算数字的数字的公式，这些数字是十的幂。
Robert Harvey在 MathOverflow 上发布问题时有过一次非常有趣的经历。一个数学家用数学符号写了一个解决方案。
阿罗诺特使用数学开发和测试了一个解决方案。发布后，他查看了源自 Math Overflow 的公式，发现其中存在缺陷（指向 Stackoverflow :)。
noahlavine开发了一种算法并以伪代码形式呈现。
一个新的解决方案
在阅读了所有答案并做了一些实验后，我发现对于从 1 到 10 n -1 的整数范围：
- 对于数字 1 到 9，需要 n*10 (n-1)个
- 对于数字 0，如果不使用前导零，则需要 n*10 n-1 - ((10 n -1) / 9)
- 对于数字 0，如果使用前导零，则需要 n*10 n-1 - n
第一个公式是由过滤器（可能是其他人）找到的，我通过反复试验找到了另外两个（但它们可能包含在其他答案中）。
例如，如果 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
可以使用High-Performance Mark结果检查这些数字。
使用这些公式，我改进了原始算法。它仍然从整数范围内的第一个数字循环到最后一个数字，但是，如果它找到一个 10 的幂的数字，它会使用公式将数字添加到数字上，计算 1 到 9 的整个范围内的数量或 1 到 99 或 1 到 999 等。这是伪代码中的算法：
integer First,Last //范围内的第一个和最后一个数字
integer Number //当前循环中的数字
integer Power //Power 是公式中 10^n 中的 n
integer Nines //Nines 是 10^n - 1, 10^5 - 1 = 99999 的结果
integer Prefix //数字中的第一个数字。对于 14,200，前缀是 142
array 0..9 Digits //将保存所有数字的计数
FOR 编号 = 从第一个到最后一个
CALL TallyDigitsForOneNumber WITH Number,1 //统计每个数字的计数
//在数字中，加1
//开始优化。注释适用于 Number = 1,000 和 Last = 8,000。
幂 = 数字末尾的零 //对于 1,000，幂 = 3
IF Power > 0 //数字以0 00 000等结尾
九号 = 10^Power-1 //九号 = 10^3 - 1 = 1000 - 1 = 999
IF Number+Nines <= Last //如果 1,000+999 < 8,000，添加一个完整的集合
Digits[0-9] += Power*10^(Power-1) //将 3*10^(3-1) = 300 添加到数字 0 到 9
Digits[0] -= -Power //调整数字0（前导零公式）
Prefix = Number 的前几位 //对于 1000，前缀为 1
CALL TallyDigitsForOneNumber WITH Prefix,Nines //统计每个的计数
//前缀中的数字，
//递增 999
Number += Nines //增加循环计数器 999 个周期
万一
万一
//优化结束
ENDFOR
SUBROUTINE TallyDigitsForOneNumber PARAMS Number,Count
重复
数字 [ 数字 % 10 ] += 计数
数字 = 数字 / 10
直到编号 = 0
例如，对于 786 到 3,021 的范围，计数器将递增：
- 由 1 从 786 到 790（5 个周期）
- 由 9 从 790 到 799（1 个周期）
- 由 1 从 799 到 800
- 由 99 从 800 到 899
- 由 1 从 899 到 900
- 由 99 从 900 到 999
- 由 1 从 999 到 1000
- 999 从 1000 到 1999
- 1999 年至 2000 年
- 999 从 2000 年到 2999
- 由 1 从 2999 到 3000
- 由 1 从 3000 到 3010（10 个周期）
- 由 9 从 3010 到 3019（1 个周期）
- 由 1 从 3019 到 3021（2 个周期）
总计：28 个周期 未优化：2,235 个周期
请注意，此算法在没有前导零的情况下解决了该问题。要将它与前导零一起使用，我使用了一个技巧：
如果需要带前导零的 700 到 1,000 范围，请使用 10,700 到 11,000 的算法，然后从数字 1 的计数中减去 1,000 - 700 = 300。
基准和源代码
我测试了原始方法，使用 %10 的相同方法和一些大范围的新解决方案，结果如下：
原始 104.78 秒 含 %10 83.66 十次方 0.07
基准应用程序的屏幕截图：（来源：clarion.sca.mx）
如果您想查看完整的源代码或运行基准测试，请使用以下链接：
- 完整的源代码（在Clarion中）：http ://sca.mx/ftp/countdigits.txt
- 可编译项目和win32 exe：http ://sca.mx/ftp/countdigits.zip
接受的答案
noahlavine解决方案可能是正确的，但我只是无法遵循伪代码，我认为有一些细节缺失或没有完全解释。
Aaronaught解决方案似乎是正确的，但代码对我来说太复杂了。
我接受了过滤器的回答，因为他的思路指导我开发了这个新的解决方案。