统计数字

实验一统计数字问题1、问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。2、题目分析：考虑由0,1,2,…,9组成的所有n位数。从n个0到n个9共有个n位数，在这些n位数中，0,1,2,…，9每个数字使用次数相同，设为。满足如下递归式：由此可知，。据此，可从低位向高位进行统计，再减去多余的0的个数即可。3、算法设计：定义数组a[10]存放0到9这10个数出现的次数，个位为第0位，第j位的数字为r。采用while循环从低位向高位统计：a.统计从个位算起前j位0~9个数；b.如果j+1位为0，去掉第j+1位补0个数；c.统计第j+1位出现1~(r-1)个数；d.统计第j+1位出现r个数。4、源程序：#includeiostream.hintmain(){longintsn[10];inti,n,c,k,s,pown;for(i=0;i10;i++)sn[i]=0;cinn;for(k=s=0,pown=1;n0;k++,n/=10,pown*=10){c=n%10;for(i=0;i10;i++)sn[i]+=c*k*(pown/10);for(i=0;ic;i++)sn[i]+=pown;sn[c]+=1+s;sn[0]-=pown;s+=c*pown;}for(i=0;i10;i++)coutsn[i]'\n';}5、算法分析：函数count()的复杂度为O(1)，主函数调用count()，故该算法的时间复杂度为O(1)。