如何计算一个整数范围的每个数字？ [英] How to count each digit in a range of integers?

查看：264
本文介绍了如何计算一个整数范围的每个数字？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

想象一下，你出售用于一些房屋，更衣室的门，酒店客房等，这些金属的数字你需要找到多少每个数字的船舶，当你的客户需要数门/房屋：

  • 在1至100
  • 在51至300
  • 在1到2000零至左

显而易见的解决方案是执行从所述第一循环的最后一个号码时，计数器转换为字符串具有或不具有零的左边，提取每个数字，并用它作为一个指标来递增的10个整数的数组。

我不知道是否有更好的方法来解决这个问题，而不在整个整数不必环路范围。

在任何语言或伪code解决方案是值得欢迎的。

编辑：

答案审查
约翰在CashCommons 和韦恩·康拉德的意见我目前的做法是好的，速度不够快。让我用一个愚蠢的比喻：如果给你指望在不到1分钟的国际象棋棋盘的平方的任务，你可以通过计算方格逐一完成任务，而是一个的好的解决方法是计数的侧面和做乘法，因为你以后可能会被要求计算在建筑物的瓷砖。
亚历克斯·赖斯纳的点，不幸的是，似乎并没有被相关与这个问题非常有趣的数学规律。
安德烈斯的建议相同的算法，我使用，但提取子的数字与10％，而不是操作。
的约翰在CashCommons 的和的 phord 的提出$ P $对 - 计算所需的数字和它们存储在查找表中，或者，为原始速度，阵列。这可能是一个很好的解决方案，如果我们有一个绝对的，不可移动的，一成不变的，最大整数值。我从来没有见过其中的一个。
高性能标志和过滤器的计算了不同范围的需要的数字。结果为1米永似乎表明有一个比例，但结果为其它数目的显示不同的比例。
过滤器的发现了一些公式可以用来计算数字的数目是10的幂。 罗伯特·哈维的有一个非常有趣的经历发布在MathOverflow的问题。其中一个数学的家伙写了用数学符号的解决方案。
Aaronaught 的开发和测试运用数学解决方案。张贴之后，他回顾了公式源于数学溢出，发现一个缺陷在里面（点计算器:)。
noahlavine 的开发了一种算法和$ P $伪code psented它。

新解
看完所有的答案，并做了一些实验后，我发现了一个范围的整数，从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 = 600000每一个
    • 的
  • 对于数字0，没有前导零，我们需要6 * 10 5 - （10 6 -1）/ 9 = 600000 - 111111 = 488889
  • 对于数字0，与领先的零，我们需要6 * 10 5 - 6 = 599994

这些数字可以使用的高性能标志的结果进行检查。

使用这些公式，我改进了原有的算法。它仍从第一到的整数范围的最后一个数字环路，但是，如果它发现了一些它是10的幂，它使用的公式要添加到数字数量为全方位的1至9或1至99或1至999等。这里的算法伪code：

的整数，姓//第一和最后一个范围内的数
整数//在回路电流数量
整数次幂//功率为n的10的n次方的公式
整数花枝招展//花枝招展为10 ^ n个resut  -  1，10 ^ 5  -  1 = 99999
整数preFIX //首先在一个号码的数字。对于14200，preFIX是142
阵列0..9数字//将举行所有数字的计数

对于数字=第一个到最后
  CALL TallyDigitsForOneNumber以数字，1 //理货每个数字的计数
                                              //在数，增量1
  //开始优化。注释是对数= 1000和尾= 8000。
  功率=零的数字// 1000，电源端= 3
  中频电源> 0 //数0 00 000等结束
    九= 10 ^电1 //九= 10 ^ 3  -  1 = 1000  -  1 = 999
    如果number +花枝招展＆LT; =最后//如果1000 + 999＆LT; 8000，加上全套
      数字[0-9] + =功率* 10 ^（电源-1）//添加3 * 10 ^（3-1）= 300到数字0到9
      数字[0]  -  =  - 电源//调整数字0（前导零式）
      preFIX =第一位数// 1000，preFIX为1
      CALL TallyDigitsForOneNumber其中preFIX，花枝招展//理货每个计数
                                                     //位在preFIX，
                                                     //增量999
      号码+ =花枝招展//递增循环计数器999次
    ENDIF
  ENDIF
  //优化结束
ENDFOR

子程序TallyDigitsForOneNumber PARAMS数，计数
  重复
    位数[编号％10] + =计数
    数=数/ 10
  UNTIL数= 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年
  • 将1 1999至2000年
  • 将999为2000〜2999
  • 将1从2999至3000
  • 将1 3000〜3010（10次）
  • 将9从3010到3019（1周）
  • 将1从3019到3021（2次）

共计：28次 如果没有优化：2235次

请注意，该算法解决了这个问题，没有前导零。与领先的零使用它，我用了一个黑客：

  

如果范围700〜1000前导零是必要的，使用算法10700至11000，然后substract 1000 - 从数字1计数700 = 300

基准和Source code

我测试了原来的做法，用10％相同的方法和一些大范围的新的解决方案，这些结果：

原104.78秒
凭借％10 83.66
随着十大0.07权力

该基准测试应用程序的

一个截图：

如果你想看到完整的源代码code或运行的基准测试中，使用这些链接：

接受的答案

noahlavine 的解决方案可能是正确的，但我只是不能按照伪code，我觉得有一些细节丢失或不能完全解释。

Aaronaught 的解决方案似乎是正确的，但code是对我的口味太复杂。

我接受过滤器的的回答，因为他的思路指导我开发这个新的解决方案。

解决方案

要的从号码的数字盘，我们就永远只能要做昂贵的串转换，如果我们不可能做一个MOD，数字最能迅速地将推动了一批这样的：

 饲料=号;
做
{位=饲料10％;
  饲料/ = 10;
  //使用数字...例如。 digitTally [数字] ++;
  }
而（饲料大于0）

这是循环应该是非常快，可以直接放置在从头到尾的理货数字的最简单方法号的循环中。

要走得更快，对于较大范围的数字，即时寻找清点所有的数字从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

  

编辑：清理我的origonal   思考：

     

从蛮力表，显示   从0（含）到吻合   poweroTen（notinc）它是可见的   tenpower的majordigit：

 由MD递增相符[0-9] * TP * 10 ^（TP-1）
递增帐簿[1到MD-1]由10 ^ TP
递减相符[0]由（10 ^ TP  -  10）
（删除前导零，如果TP＆GT; leadingzeros）
可以增加理货[moresignificantdigits]自我（MD * 10 ^ TP）
（完成的效果）

如果被应用于每个显著位这些理货调整， 就像数从0到最终1理货应修改

调整可以倒删除preceeding范围（起始号码）

感谢Aaronaught为您彻底和测试的答案。

Imagine 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 = 0

For 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:

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  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:

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屋！

查看全文
相关文章
C/C++最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆