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


[解决办法]
从n最高位到最低位，递归列出各数位的数字。
[code=Java]
public class Main {

public Main () {
start ();
}

public static void main (String args[]) {
new Main ();
}

private void start () {
iarr_1 = new int[String.valueOf (n).length ()];
g (0);
}

private void g (int a) {
if (a == iarr_1.length) {
h ();
return;
}
for (int i = 0; i < 10; i++) {
iarr_1[a] = i;
g (a+1);
}
}

private void h () {
boolean b = true;
for (int i = 0; i < iarr_1.length; i++) {
b = (iarr_1[i] == 0 && b == true) ? true:false;
if (!b) {
iarr_2[iarr_1[i]]++;
}
}
j++;
//
if (j >= n) {
for (int i = 0; i < iarr_2.length; i++) {
System.out.println (i + "_" + iarr_2[i]);
}
System.exit (0);
}
}

private final int n = 12;
private int[] iarr_1;
private int[] iarr_2 = new int[10];
private int j = -1;

}[code]
[解决办法]
0-9里面 各个数字均出现1次

00-99里面 各个数字均出现10+ 1*10 = 20

000-999里面 各个数字均出现 100 + 20*10 = 120

0000-9999里面各个数字均出现 1000 + 120*10 = 2200

同理 100-199 1出现在百位 那就可以直接用 100+20 就是1出现的次数 其他数字保持20

反推就可以拆解任意n

34567

30000 因为万位是3 所以 1 2 3 均出现 10000+2200*3 其他均出现 2200 * 3
4000 因为千为是4 所以 1 2 3 4 均出现 1000 + 120 *4 其他均出现 120*4
500 因为百位是5 所以 1 2 3 4 5 均出现 100 + 20*5 其他均出现 20 *5
60 因为十位是6 所以 1 2 3 4 5 6 均出现 10 + 1*6 其他均出现 1*6
7 个为是7 所以 1 2 3 4 5 6 7 都出现 1+0*7 其他0*7

这样1出现16600+1480+200+16+1 = 18297次
[解决办法]
int n1,n2,n3,n4,n5,n6,n7,n8,n9,n0;

fun(int n){
if(n/10>0){
fun(n/10);
}
else{
switch(n%10){
case 1:
n1++;
break;
case 2:
n2++;
break;
case 3:
n3++;
break;
case 4:
n4++;
break;
case 5:
n5++;
break;
case 6:
n6++;
break;
case 7:
n7++;
break;
case 8:
n8++;
break;
case 9:
n9++;
break;
case 0:
n0++;
break;
}
}
}
[解决办法]
计算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]); }