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 <stdio.h>
#include <string.h>
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 <stdio.h>
#include <string.h>
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;i<digit(n);i++){a[0]+=pow(10,i);} 
           }                            //与递归前做比较，补上被忽略的0
           top=n/pow(10,digit(n)-1);    //求最高位是多少
           for(i=0;i<top;i++){a[i]+=pow(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-99
           for(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;i<digit(k);i++){a[0]-=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;
}