我的算法題——藍橋杯校選

問題描述：

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