1-m之间的自然数排成一排其中8出现了多少次

admin

1、最直接的方法是模拟，碰到一个数字，就分解它，统计8的个数，这样很直观，但是这显然不是最好的方法，时间复杂度太高。
2、另外一种分析就是统计法，0-9 之间有1个8，0-99之间有20个，0-999之间有300个*** 。0-m之间的数字化成很多区间去统计，这样逻辑比较复杂，但是程序运行会很快。

admin

第二种方法

admin

wzd同学的这个做法是我比较认同的一种做法，非常好，但是就是程序写得不漂亮，我来给他改一改

diggersun

wyl同学的这个方法很新颖，请他讲讲自己的思路。

admin

1. #include<iostream>
   
2. using namespace std;
   
3. int s,i,x,n,t;
   
4. int main()
   
5. {
   
6.     cin>>n;
   
7.     for (i=1;i<=n;i++)
   
8.     {
   
9.         x=i;  ///保存现场
   
10.         while (x!=0)
    
11.         {
    
12.             t=x%10;x=x/10;  
    
13.             if (t==8) s++; ///  s+=(t==8)
    
14.         }
    
15.     }
    
16.     cout<<s;
    
17.     return 0;
    
18. }
    

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <cstdio>
   
5. #include <cstdlib>
   
6. using namespace std;
   
7. long long to=1,all=0;
   
8. char a[10000];
   
9. int main()
   
10. {
    
11.     scanf("%s",a);
    
12.     int l=strlen(a);
    
13.     for(int i=l-1,j=0;i>=0;i--,j++)
    
14.     {
    
15.         if(a[i]>='8')
    
16.             all+=to;
    
17.         all+=((j*to/10)*(a[i]-'0'));
    
18.         to*=10;
    
19.     }
    
20.     printf("%lld",all);
    
21.     return 0;
    
22. }

复制代码

wzd(temp)

#include <cstdio>
#include <cstdlib>
using namespace std;
int m;
int dfs_(int k)
{
    if(k<10 && k>=8)
        return 1;
    if(k<8)
        return 0;

    int i=0;
    int temp=k;
    int MOD=1;
    while(temp>0)
    {
        temp=temp/10;
        i++;
        MOD*=10;
    }
    MOD/=10;
    int first=k/MOD;
    if(first>=8)
    {
        if(first==8)
            return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+(k-MOD*first+1));
        else
            return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+MOD);
    }
    else
        return (first*dfs_(MOD-1)+dfs_(k-MOD*first));
}
int main()
{
    scanf("%d",&m);

    printf("%d\n",dfs_(m));

    return 0;
}

wzd(temp)

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. using namespace std;
   
4. int m;
   
5. int dfs_(int k)
   
6. {
   
7.     if(k<10 && k>=8)
   
8.         return 1;
   
9.     if(k<8)
   
10.         return 0;
    
11. 
    
12.     int temp=k;
    
13.     int MOD=1;
    
14.     while(temp>0)
    
15.     {
    
16.         temp=temp/10;
    
17.         MOD*=10;
    
18.     }
    
19.     MOD/=10;
    
20.     int first=k/MOD;
    
21.     if(first>=8)
    
22.     {
    
23.         if(first==8)
    
24.             return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+(k-MOD*first+1));
    
25.         else
    
26.             return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+MOD);
    
27.     }
    
28.     else
    
29.         return (first*dfs_(MOD-1)+dfs_(k-MOD*first));
    
30. }
    
31. int main()
    
32. {
    
33.     scanf("%d",&m);
    
34. 
    
35.     printf("%lld\n",dfs_(m));
    
36. 
    
37.     return 0;
    
38. }

复制代码

吴语林

吴语林 发表于 2018-5-1 20:32

a>='8'  额外加一个  10^位数

其他以正常方式累加  ps：加10^(位数-1)*位数