问题描述:
小明非常不喜欢数字 2,包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2,小明将它称为洁净数。
请问在整数 1 至 n 中,洁净数有多少个?
输入格式
输入的第一行包含一个整数 n。
输出格式
输出一行包含一个整数,表示答案。
样例输入
30
样例输出
18
评测用例规模与约定
对于 40% 的评测用例,1 <= n <= 10000。
对于 80% 的评测用例,1 <= n <= 100000。
对于所有评测用例,1 <= n <= 1000000。
思路:假设n取值可以取到0,
则若n为9则有
0 1 2 3 4 5 6 7 8 9
若n为10则有
0 1 2 3 4 5 6 7 8 9
10
此方法非暴力解决方法!!!
不难看出,当不满一行时可进行分别讨论得出不满一行的个数,当一行已满其个数为10-1=9。则有当前假象式:10/10=1…0 则有191+0=9;12/10=1…2,191+(2-1)=10。当位数不为个位且为2时,如22,不难看出21 22都不为洁净数,其相当于20,所以当先计算个位时为算式:290-1=1。再计算十位时发现为数字2则需减去之前个位的,算式为:291-1-1=16.当数大于2时只需减去2那一行即可,如30的算式为:(3-1)*9=18。综上,当遇到成百上千位时,只需递归拆解运算即可。
以下是我的代码仅供参考:
int Calcul(int n,int N,int flag,int Counts,int p){
if(N<2)//对凑不出整十行的,进行判断
N=N*pow(9,flag);//
else
{
if(N==2&&flag!=0)
N=2*pow(9,flag)-1-p;//位数不为个位时,要减去之前的计数
else
N=(N-1)*pow(9,flag);
}
if(n<10){
if(n<2)//根据位数得到目前位数数量
Counts=n*pow(9,flag+1)+N;
if(n==2)
Counts=n*pow(9,flag+1)-1-p;//若存在2的位数,则需减去前面所计算的小位数,如229等同于220亦等同于199
if(n>2)
Counts=(n-1)*pow(9,flag+1)+N;
}else
{//大于十位记录当前位数于P
Counts=N;
p+=N;
N=n%10;
n=n/10;
flag++;
Counts=Counts+Calcul(n,N,flag,Counts,p);
}
return Counts;
}
int main(){
while(true){
cout<<"请输入整数n:";
int n,p=0;
cin>>n;
int flag=0;//位数
int N=0;//当前位数得到的总数
int Counts=0;//数字数量
N=n%10;
n=n/10;
cout<<Calcul(n,N,flag,Counts,p)<<"\n";
}
}