统计数字问题

问题描述： 一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如第6页用6表示，而不是06或006。数字统计问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0,1,2,3,…,9。 编程任务： 给定表示书的总页码的十进制整数n(1<<n<<109)。编程计算书的全部页码中分别用到多少次数字0,1,2,3,…,9。 数据输入： 输入数据由文件名input.txt的文本文件提供。每个文件只有1行，给出表示书的总页码的整数n。 结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。输出文件共有10行，在第k行输出页码中用到数字k-1的次数，k=1,2,3,…,10。 输入文件示例 输出文件示例 Input.txt output.txt 11 1 4 1 1 1 1 1 1 1 1 1 问题分析： 考察由0,1,2,3,…,9组成的所有n位数。从n个0到n个9共有10^n个n位数。在这10^n个n位数中，0,1,2,3,…,9每个数字使用次数相同，设为f(n)。f(n)满足如下递归式： f(n) = 10f(n-1)+10^(n-1)………………… (n>1) f(n) =1……………………………………… (n=1) 由此可知，f(n)=n*10^(n-1)。 据此，可从高位向低位进行统计，再减去多余的0的个数即可。