計算機算法設計與分析1-1

問題描述：

一本書的頁碼從自然數1開始計數，直到自然數n。書的頁碼按照通常的習慣編排，每個頁碼都不包含多餘的前導數字0。例如，第6頁用數字6表示，而不是06或006等。數字計數問題要求對給定書的總頁碼n，計算出書的全部頁碼中分别用到多少次數字0，1，2，...，9。

本來就是暴力寫的，看了看資料範圍到e9，O—O  

然後看了看答案的遞歸公式，咋推出來的我也布吉島，還現學了一波差分方程怎麼解，最後還是參考了大佬的部落格。

傳送門 

下面說一下步驟

1.确定數字長度，log10(n)+1,如1000長度為4

2.分區間，區間長度為10^n

如230,區間長度100，000-099，100-199 (至于為什麼不算200-230,下面會處理)

3.在每個區間内0-9這10個數字出現的次數相同（除了首位，即100-199的1會多出一些）

将0-9除了首位外出現的次數算出來

4.計算首位出現的次數

5.将算過的地方去掉，并且處理0（如10300,在取餘得到300時要将中間的0計算求和）

6.遞歸處理餘數

7.得到結果後減去多算的0，這也就是網上說的補0遞歸法

#include<bits/stdc++.h>
using namespace std;
int ans[10];
void solve(int n)
{
	int len=log10(n)+1;
	int digit=n/(round(pow(10,len-1)));
	for(int i=0;i<=9;i++)
		ans[i]+=digit*(len-1)*round(pow(10,len-2));
	for(int i=0;i<digit;i++)
		ans[i]+=round(pow(10,len-1));
	int tep=n%(int)round(pow(10,len-1));
	ans[digit]+=1+tep;
	if(tep==0)
	{
		ans[0]+=len-1;
		return ;
	}
	else
	{
		int len1=log10(tep)+1;
		ans[0]+=(tep+1)*(len-len1-1);
		return solve(tep);
	}
}
int main()
{
	int n;
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d",&n);
	solve(n);
	int len=log10(n)+1;
	for(int i=0;i<len;i++)
		ans[0]-=round(pow(10,i));
	for(int i=0;i<=9;i++)
		printf("%d\n",ans[i]);
	return 0;
}