关于统计数字问题的算法
一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如第6页用6表示而不是06或006。数字统计问题要求对给定书的总页码,计算出书的全部页码中分别用到多少次数字0,1,2,3,.....9。
这个题目有个最容易想到的n*log10(n)的算法。这是自己写的复杂度为O(n*log10(n))的代码:
voidstatNumber(intn){ inti,t; intcount[10]={0}; for(i=1;i<=n;i++){ t=i; while(t){ count[t%10]++; t/=10; } } for(i=0;i<10;i++){ printf("%d/n",count[i]); } }
仔细考虑m个n位十进制数的特点,在一个n位十进制数的由低到高的第i个数位上,总是连续出现10^i个0,然后是10^i个1……一直到10^i个9,9之后又是连续的10^i个0,这样循环出现。找到这个规律,就可以在常数时间内算出第i个数位上每个数字出现的次数。而在第i个数位上,最前面的10^i个0是前导0,应该把它们减掉。
这样,可以只分析给定的输入整数n的每个数位,从面可以得到一个log10(n)的算法,代码如下:
voidstatNumber(intn){ intm,i,j,k,t,x,len=log10(n); chard[16]; intpow10[12]={1},count[10]={0}; for(i=1;i<12;i++){ pow10[i]=pow10[i-1]*10; } sprintf(d,"%d",n); m=n+1; for(i=0;i<=len;i++){ x=d[i]-'0'; t=(m-1)/pow10[len-i]; count[x]+=m-t*pow10[len-i]; t/=10; j=0; while(j<=x-1){ count[j]+=(t+1)*pow10[len-i]; j++; } while(j<10){ count[j]+=t*pow10[len-i]; j++; } count[0]-=pow10[len-i];/*第i个数位上前10^i个0是无意义的*/ } for(j=0;j<10;j++){ printf("%d/n",count[j]); } }
通过对随机生成的测试数据的比较,可以验证第二段代码是正确的。
对两段代码做效率测试,第一次随机产生20万个整数,结果在我的电脑上,第二段代码执行1.744秒。第一段代码等我吃完钣回来看还是没反应,就强行关了它。
第二次产生了1000个整数,再次测试,结果第一段代码在我的电脑上执行的时间是
10.1440秒,而第二段代码的执行时间是0.0800秒。
其原因是第一段代码时间复杂度为O(n*log10(n)),对m个输入整数进行计算,则需要的时间为1*log10(1)+2*log10(2)+...+m*log10(m),当n>10时,有
n*log10(n)>n,所以上式的下界为11+12+....+m,其渐近界为m*m。对于20万个测试数据,其运行时间的下界就是4*10^10。
同样可得第二段代码对于n个输入数据的运行时间界是n*log10(n)的。
上面的代码中有个pow10数组用来记录10^i,但10^10左右就已经超过了2^32,但是题目给定的输入整数的范围在10^9以内,所以没有影响。
原著中给出的分析如下:
考察由0,1,2...9组成的所有n位数。从n个0到n个9共有10^n个n位数。在这10^n个n位数中,0,1,2.....9第个数字使用次数相同,设为f(n)。f(n)满足如下递推式:
n>1:
f(n)=10f(n-1)+10^(n-1)
n=1:
f(n)=1
由此可知,f(n)=n*10^(n-1)。
据此,可从高位向低位进行统计,再减去多余的0的个数即可。
著者的思想说的更清楚些应该是这样:
对于一个m位整数,我们可以把0到n之间的n+1个整数从小到大这样来排列:
000......0
.............
199......9
200......0
299......9
.........
这样一直排到自然数n。对于从0到199......9这个区间来说,抛去最高位的数字不看,其低m-1位恰好
就是m-1个0到m-1个9共10^(m-1)个数。利用原著中的递推公式,在这个区间里,每个数字出现的次数
(不包括最高位数字)为(m-1)*10^(m-2)。假设n的最高位数字是x,那么在n之间上述所说的区间共有
x个。那么每个数字出现的次数x倍就可以统计完这些区间。再看最高位数字的情况,显然0到x-1这些
数字在最高位上再现的次数为10^(m-1),因为一个区间长度为10^(m-1)。而x在最高位上出现次数就是
n%10^(m-1)+1了。接下来对n%10^(m-1),即n去掉最高位后的那个数字再继续重复上面的方法。直到
个位,就可以完成题目要求了。
比如,对于一个数字34567,我们可以这样来计算从1到34567之间所有数字中每个数字出现的次数:
从0到9999,这个区间的每个数字的出现次数可以使用原著中给出的递推公式,即每个数字出现4000次。
从10000到19999,中间除去万位的1不算,又是一个从0000到9999的排列,这样的话,从0到34567之间
的这样的区间共有3个。所以从00000到29999之间除万位外每个数字出现次数为3*4000次。然后再统计
万位数字,每个区间长度为10000,所以0,1,2在万位上各出现10000次。而3则出现4567+1=4568次。
之后,抛掉万位数字,对于4567,再使用上面的方法计算,一直计算到个位即可。
下面是自己的实现代码:
voidstatNumber_iterative(intn){ intlen,i,k,h,m; intcount[10]={0}; intpow10[12]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; chard[16]; len=log10(n);/*len表示当前数字的位权*/ m=len; sprintf(d,"%d",n); k=0;/*k记录当前最高位数字在d数组中的下标*/ h=d[k]-'0';/*h表示当前最高位的数字*/ n%=pow10[len];/*去掉n的最高位*/ while(len>0){ if(h==0){ count[0]+=n+1; h=d[++k]-'0'; --len; n%=pow10[len]; continue; } for(i=0;i<10;i++){ count[i]+=h*len*pow10[len-1]; } for(i=0;i<h;i++){ count[i]+=pow10[len]; } count[h]+=n+1; --len; h=d[++k]-'0'; n%=pow10[len]; } for(i=0;i<=h;i++){ count[i]+=1; } /*减去前导0的个数*/ for(i=0;i<=m;i++){ count[0]-=pow10[i]; } for(i=0;i<10;i++){ printf("%d/n",count[i]); } }
以上就是本文的全部内容,希望对大家的学习有所帮助。