我的算法题——蓝桥杯校选

问题描述：

小明非常不喜欢数字 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";
 } 
}