问题描述：一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6

页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。

算法设计：给定表示书的总页码的10

进制整数n (1≤n≤10^9) 。计算书的全部页码中分别用到多少次数字0，1，2，…，9。

数据输入：输入数据由文件名为input.txt的文本文件提供。每个文件只有1行，给出表示书的总页码的整数n。

结果输出：将计算结果输出到文件output.txt中。输出文件共有10行，将第k行输出页码中用到数字k-1的次数，k=1,2,…10。

输入文件示例

输出文件示例

input.txt

output.txt

11

1

4

1

1

1

1

1

1

1

1

分析与解答：考察由0,1,2,…,9组成的所有的n位数，从n个0到n个9共有10^n个n位数。在这10^n个n位数中，0,1,2,…,9每个数字使用次数相同，设为f(n)。f(n)满足如下递归式：

由此可知，f(n) = n × 10^(n-1)

据此，可以从高位向低位进行统计，再减去多余的0的个数即可。

package com.algorithm.johnchang.ch1;

import java.io.BufferedReader;

import java.io.FileOutputStream;

import java.io.FileReader;

import java.io.IOException;

import java.io.PrintStream;

//import java.util.Scanner;

/**

* 统计数字问题 给定表示书的总页码的十进制整数m(1<= m <= 10的9次方)， 计算书的全部页码中分别用到多少次数字0，1，2，……，9

*

* @author John.Chang

*

* @version 1.0

*/

public class StatisticsProblem {

// 保存最终结果的数组

private int[] result;

/**

* Constructor，初始化结果数组

*/

public StatisticsProblem() {

this.result = new int[10];

}

/**

* 求解整数幂

*

* @param a

* 底数

* @param b

* 指数

* @return a的b次方

*/

public static int power(int a, int b) {

return (int) Math.pow(a, b);

}

/**

* 用递归来求解所有n位数中每个数字出现的次数

*

* @param n

* 位数

* @return 10的n次方个n位数中每个数字出现的次数

*/

public static int func1(int n) {

if (n == 0) {

return 0;

}

if (n == 1) {

return 1;

} else {

return 10 * func1(n - 1) + power(10, n - 1);

}

}

/**

* 直接使用递推表达式求解所有n位数中每个数字出现的次数

*

* @param n

* 位数

* @return 10的n次方个n位数中每个数字出现的次数

*/

public static int func2(int n) {

return n * power(10, n - 1);

}

/**

* 给定书的总页码的十进制整数，计算每个数字出现的次数

*

* @param num

* 书的总页码整数

*/

public void statistic(int num) {

// 获取整数m的位数

int length = String.valueOf(num).length();

// 从高位向低位进行统计，再减去多余的0的个数

for (int i = length; i > 0; i--) {

// 计算出第i位(从低位向高位)对应的数bitnum

int a = power(10, i);

int b = power(10, i - 1);

int bitnum = (num % a) / b;

int j;

// 计算比bitnum小的数字出现的次数

for (j = 0; j < bitnum; j++) {

// 计算比bitnum小的数字在第i位出现的次数

result[j] += b;

// 当第i位为比bitnum小的数字时，计算所有数字在后面i-1位中出现的次数

for (int k = 0; k <= 9; k++) {

// result[k] += func1(i - 1);

result[k] += func2(i - 1);

}

}

// 计算bitnum在第i位出现的次数

result[j] += num % b + 1;

// 最后对于数字0需减去多余的0的个数

result[0] -= b;

}

}

@SuppressWarnings("resource")

public static void main(String[] args) throws IOException {

// 从控制台输入获取书的总页码整数num

// Scanner scanner = new Scanner(System.in);

// int num = scanner.nextInt();

// 从input.txt文本文件中读入书的总页码整数num

BufferedReader br = new BufferedReader(new FileReader("input.txt"));

int num = Integer.parseInt(br.readLine());

StatisticsProblem sp = new StatisticsProblem();

sp.statistic(num);

// 输出统计结果

PrintStream ps = new PrintStream(new FileOutputStream("output.txt"));

for (int i = 0; i < 10; i++) {

// 输出结果到控制台

System.out.println(sp.result[i]);

// 输出结果到output.txt文本文档中

ps.println(sp.result[i]);

}

}

}