计算机算法设计与分析1-1

问题描述：

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

本来就是暴力写的，看了看数据范围到e9，O—O

然后看了看答案的递归公式，咋推出来的我也布吉岛，还现学了一波差分方程怎么解，最后还是参考了大佬的博客。

传送门

计算机算法设计与分析1-1

下面说一下步骤

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;
}

计算机算法设计与分析1-1

相关推荐