1244 数字统计（从1~n各个数字出现的次数）

1244 数字统计（从1~n各个数字出现的次数）

题目描述：

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，
每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，
2，…，9。

输入

给出表示书的总页码的整数n

输出

输出10行，在第k行输出页码中用到数字k-1 的次数，k=1，2，…，10。

样例输入

11

样例输出

1
4
1
1
1
1
1
1
1
1

算法：

当n比较小的时候我们可以暴力枚举，从1到n遍历一遍，对每个数统计各个数出现的次数。只需要对每个数做除法直至为0即可。

代码实现：

#include 
#include 
int main()
{int n,i,j;int a[10];while(~scanf("%d",&n)){memset(a,0,sizeof(a));   //清空数组for(i=1;i<=n;i++){j=i;while(j)            //直到数字为0{a[j%10]++;      //统计0~9 每位出现的次数j/=10;          //将数字向右移动一位继续统计}}for(i=0;i<10;i++){printf("%d\n",a[i]);}}return 0;
}

当n很大的时候我们会发现A这道题时会超时。所以我们要改进算法。

改进算法：

首先以666为例子，我们可以把666分为000-599和600-666。000-599我们可以通过一定的算法来继续。600-666只需要将数字6加67次，而后做递归只需要计算00-66即可。
在这里我做一点提示，例如10000001，当我们做了一次递归后只能计算0-1，此时我们会忽略很多0，而计算0的方法我们需要比较递归前后数的位数相差是否为1，若不为1，则一定有0被忽略掉，此时我们只需要加上0的个数即可。
在最后我们只需要去掉前导0即可。

代码实现

#include 
#include 
int pow(int i,int j)
{int k=1;while(j--){k*=i;}return k;
}
//幂
int digit(int n)
{int num=0;while(n>0){n/=10;num++;}return num;
}
//求该数字有多少位
int number(int digit_num)
{int i=digit_num;int j,k;if(i==0){k=0;}else{k=number(i-1)*10+pow(10,i-1);;}return k;
}
//有几位数字时应该有都少次出现
int main()
{int n,i,j,k,p;int sum;int top;int a[10];while(~scanf("%d",&n)){k=n;                             //储存n的值，为去除前导0做准备sum=0;memset(a,0,sizeof(a));p=digit(n);                      //在这里p就是为上面可能有0被忽略做准备if(n>=10){while(n){if(p!=digit(n)){a[0]+=(p-digit(n))*n;for(i=0;i0]+=pow(10,i);} }                            //与递归前做比较，补上被忽略的0top=n/pow(10,digit(n)-1);    //求最高位是多少for(i=0;ipow(10,digit(n)-1)   //top之前的数字都要先加，比方说000-666：000-599中0,1,2,3,4,5分别先出现了100遍sum=top*number(digit(n)-1);   //000-599 可以分成6份每份为00-99for(i=0;i<10;i++){a[i]+=sum;}p=digit(n)-1;n=n%(top*pow(10,digit(n)-1)); //对于666 600-666可变为00-66此时n变为a[top]+=n+1;                  //600-666中开头的6又出现了67次}for(i=0;i0]-=pow(10,i);}    //除去前导零a[0]+=p;}//else{for(i=1;i<=n;i++){a[i]++;}}for(i=0;i<10;i++){printf("%d\n",a[i]);                    //依次输出}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！