关于页码中0~9数字出现的次数解决方法

关于页码中0~9数字出现的次数
我想问一个编程方面的问题
就是求一本书的页码数中0~9这几个数字出现的次数,用递归的方法做,如何做,请各位大侠帮帮忙啊

------解决方案--------------------
记T(n,k)为区间[1,n)内的自然数数字组成中含数字k(0<k<10)的次数。
那么，可以得到如下的递归式：
T(n,k)=(n%10)*T(n/10+1,k) + (10-n%10)*T(n/10,k) + n/10 + (n%10>k) （1）
T(n,k)=0 n<=k
T(n,k)=1 k<n<10

特殊的，n=10^t、 k=1 则：
T(10^t,k)=10*T(10^(t-1))+10^(t-1)
于是，得到：T(10^t)=t*10^(t-1)。

注意，（1）式并不适合k=0的情况。

------解决方案--------------------
计算0出现个数，先补0，就可以同其他数字同样计算，然后去掉补 0 个数

C/C++ code

#include <stdio.h>
#include <stdlib.h>

void  statNum(int sn[10], int n)
{
    int i, c, k, s, pown;

    for(int i = 0; i < 10; i++)
        sn[i] = 0;

    for(k=s=0, pown=1; n > 0; k++, n /=10, pown *=10)
    {
        c = n%10;
        //先补0
        //统计从个位算起前k位 0 ~ 9 个数
        for(i=0; i < 10; i++)                 
            sn[i] += c*k*pown/10; 
       //  统计第k+1位出现 0 ~ (c-1) 个数              
        for(i=0; i < c; i++)                 
            sn[i] += pown; 
       //  统计第k+1位出现 c 个数              
        sn[c] += 1 + s; 
        
        //  去掉第k+1位补 0 个数              
        sn[0] -= pown;

        s += c*pown;
    }
}


void  main(int argc , char *argv[])
{
    int sn[10], i, n=2030;
    if(argc > 1)
        n = atoi(argv[1]);

    printf("n = %d\n", n);    
    statNum(sn, n);
    for(i=0; i < 10; i++)
        printf("%d: %d\n", i,sn[i]); 
}

关于页码中0~9数字出现的次数解决方法

相关推荐