统计数字问题
一本书的页码从自然数1开始顺序编码到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示而不是06或006等。数字计数问题对给定书的总页码n，计算书的全部页码分别用到多少次数字0，1，2，3 。。。9。
算法分析
设n为数字的位数，f(n)为各个数字出现的次数
0
1
2
3
…
9
f(1)=1。这时我们发现当n为1时，每个数字出现的次数都是1次，我们在计算当n为2时的情况，找出其中的规律。
当n=2时
00
01
…
09
10
11
…
99
分析：我们把0~9看成一个整体，发现在个位上它重复了10次，也就是说0
~9出现的次数都为10次，十位上每个数字又都出现了10次，所以，f(2)=
20。
当n=3时
000
001
002
…
010
011
…
099
100
…
999
分析：我们用同样的方法可以看出，在00~99中每个数字出现的次数是20，
又因为在个位和十位上重复出现了10次，所以在个位和十位上出现200次，
在百位上每个数字出现的个数是10^2次，所以f(3)=300。
规律：f(n）的次数为f(n-1)*10加上10^(n-1)。
所以，f(n)=f(n-1)*10+10^(n-1) n>1
f(1)=1 n=1
我们可以发现
f(n)的规律为递归函数。我们判断是否能找到它的非递归式。
f(n)=n*10^(n-1） （求法放在最后）
题目规定不能有多余的前导数字0，像06用6表示，所以说我们还要去掉多余的前导0，公式为S(n）={(10^n)-1}/9。（算法很简单，是一个等比数列）
#include<iostream>
#include<cmath>
using namespace std;
int weishu(int n); //计算这个数是多少位
int zuigao(int n); //计算这个数最高位数字是多少
int yushu(int n); //计算这个数除最高位后的余数是多少
int f(int n); //计算0~9出现的相同次数
int S(int n); //计算多余0的个数,等比数列求和公式，公式q=10
void CountDigit(int page,int num[]); //计算page中0~9出现的次数，（统计数字问题）
int main() {
int page; //计算的页码值
while( 1) {
cout<<endl<<"请输入一个页码,以0结束程序:"<<endl;
cin>>page;
if(page==0) break;
int num[10]= { 0}; //保存0~9的个数，例如num[0]，代表0出现的次数
CountDigit(page,num); //统计数学问题
num[0]=num[0]-S(page); //减去多余的0的个数
cout<<"数字0~9出现的次数分别为："<<endl;
for(int i=0; i<10; i++)
cout<<num[i]<<' ';
cout<<endl;
}
return 0;
}
int weishu(int n) { //计算这个数是多少位
int i = 0;
while (n) {
n /= 10;
i++;
}
return i;
}
int zuigao(int n) { //计算这个数最高位数字是多少
return n / (int)pow(10.0, weishu(n) - 1);
}
int yushu(int n) { //计算这个数除最高位后的余数是多少
return n % (int)pow(10.0, weishu(n) - 1);
}
int f(int n) { //计算0~9出现的相同次数
return n * (int)pow(10.0, n - 1);
}
int ling(int n) { //计算多余0的个数,等比数列求和公式，公式q=10
return (1 - (int)pow(10.0, weishu(n))) / (1 - 10);
}
void CountDigit(int page,int num[]) { //计算page中0~9出现的次数，（统计数字问题）
//求位数
//求最高位
//去除最高位后的余数，比如4321，去年最高位4后，m1=321
int n = weishu(page); //求位数
int m = zuigao(page); //求最高位数字
int m1 = yushu(page);//求去除最高位的余数。
int x=f(n-1); //第一步（求0~9出现的相同次数）
for(int i=0; i<10; i++) //第二步。计算m组
num[i] += x*m;
for(int i=0; i<m; i++) //第三步
num[i] += (int)pow(10.0,n-1);
num[m] += m1+1; //第四步
num[0] += (n-weishu(m1)-1)*(m1+1); //修正去掉最高位后，余数为 0xxx的情形。例如：40021,m=4,m1=21;还有22(即m1+1)个00是有效0
if(m1==0)return; //递归出口。递归到余数m1=0，即当递归到page是一位数时，还需执行else递归体一次。
else CountDigit(m1,num); //递归体。例如求4321，到求321，到求21
}
分析主函数的每个步骤，假设page为4321，它是一位4位数，在我们上面的讲解中，全部都是将位数取满计算，例 9，99。面对这种无法取满的情况，我们先计算后三位，为x=f(n-1),然后在乘最高位的m，计算重复的步骤，这就是第一二步的内容。在第三步中计算万位上的数字出现次数，这里的代码为num[i]+=(int)pow(10.0,n-1),此时我们已经计算到了0000~3999的数字出现次数，然后我们看下一步，现在我们要的就是4000到4321的次数，但是我们可以看出，主函数是一个递归体，我们可以求出除最高位之后的余数m1，然后CountDight(m1,num),直到m1=0为止。这就是最后两步的内容。
也就是说我们现在只需要计算4000~4321的万位出现的次数。为num[m]+=m1+1即可。
此时如果进行代码运行可以求出4321的次数，但如果page=105，计算如下
这里我们计算0出现的次数，10，20，，90共9次，100有2次，101，102，，105共5次，共16次，此时出现了问题，原因是当m1求余数时，m1直接等于5，而忽略了10x中的有效0，所以增加函数num[0] += (n-weishu(m1)-1)*(m1+1)。
这里介绍一下，函数的非递归式的求法：
