[已解决]算法优化，萌新求助，怎么让计算更快

缘丿谁懂我一生

问题：
         输入一个r，计算区间[1,r]内有多少个不含数字6的数。



#include<stdio.h>
#include<stdlib.h>

int main()
{
    long long m,j,r=10000000;
    int i,count=0;
    //scanf("%I64d",&r);
    for(m=1;m<=r;m++)
    {
        j=m;
        while(j!=0)
        {
            i=j%10;
            if(i!=6)
            {
                if(i==j) count++;
            }
            else break;
            j/=10;
        }
    }
    printf("%d",count);
    return 0;
}

最佳答案

月排行榜 / 总排行榜

Croper

2019-11-23 23:42:30

少考虑了中间是6的情况：

1. 
   
2. int count6lessnum(int n) {
   
3.         int a[10] = { 0,1,2,3,4,5,5,6,7,8 };
   
4.         int ret = 0, base = 1;
   
5.         while (n) {
   
6.                 ret += a[n % 10] * base;
   
7.                 if (n % 10 == 6) {
   
8.                         ret = a[7] * base-1;
   
9.                 }
   
10.                 n /= 10;
    
11.                 base *= 9;
    
12.         }
    
13.         return ret;
    
14. }
    

复制代码

这下没问题了把

跳转到最佳答案楼层

Croper

其实不含6的数相当于9进制的数，按9进制的数的转化方法来计算就行

1. int count6lessnum(int n) {
   
2.         int a[10] = { 0,1,2,3,4,5,5,6,7,8 };  //10进制与9进制的对应关系
   
3.         int ret = 0, base = 1;
   
4.         while (n) {
   
5.                 ret += a[n % 10] * base;
   
6.                 n /= 10;
   
7.                 base *= 9;
   
8.         }
   
9.         return ret;
   
10. }

复制代码

缘丿谁懂我一生

Croper 发表于 2019-11-23 23:21
其实不含6的数相当于9进制的数，按9进制的数的转化方法来计算就行

好像结果不对，不知道是不是我的打开方式有问题，大佬能发下源代码嘛
我是这样写的：

#include<stdio.h>
#include<stdlib.h>


int count6lessnum(int n)
{
    int a[10] = { 0,1,2,3,4,5,5,6,7,8 };  //10进制与9进制的对应关系
    int ret = 0, base = 1;
    while (n)
    {
        ret += a[n % 10] * base;
        n /= 10;
        base *= 9;
    }
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    printf("%d",count6lessnum(n));
}

缘丿谁懂我一生

还有我自己想了个但是也是结果不对，请大佬修改：


#include<stdio.h>
#include<stdlib.h>

int main()
{
    int m,j,r=1234567;
    int i,count1=0,count2=1;
    int x=1,y=0;
    //scanf("%I64d",&r);
    int r1,r2;
    r1=r/1000;
    r2=r%1000;
    printf("r1=%d\n",r1);
    printf("r2=%d\n",r2);

    for(m=1;m<r1;m++)
    {
        j=m;
        while(j!=0)
        {
            i=j%10;
            if(i!=6)
            {
                if(i==j) count1++;
            }
            else break;
            j/=10;
        }
    }
    printf("count1=%d\n",count1);

    for(m=1;m<1000;m++)
    {
        j=m;
        while(j!=0)
        {
            i=j%10;
            if(i!=6)
            {
                if(i==j) count2++;
            }
            else break;
            j/=10;
        }
    }
    printf("count2=%d\n",count2);

    for(m=1;m<=r2;m++)
    {
        j=m;
        while(j!=0)
        {
            i=j%10;
            if(i!=6)
            {
                if(i==j) x++;
            }
            else break;
            j/=10;
        }
    }
    printf("x=%d\n",x);

    for(m=1;m<1000;m++)
    {
        j=m;
        while(j!=0)
        {
            i=j%10;
            if(i!=6)
            {
                if(i==j) y++;
            }
            else break;
            j/=10;
        }
    }
    printf("y=%d\n",y);

    printf("%d",count1*count2+x+y);
    return 0;
}

Croper

少考虑了中间是6的情况：

1. 
   
2. int count6lessnum(int n) {
   
3.         int a[10] = { 0,1,2,3,4,5,5,6,7,8 };
   
4.         int ret = 0, base = 1;
   
5.         while (n) {
   
6.                 ret += a[n % 10] * base;
   
7.                 if (n % 10 == 6) {
   
8.                         ret = a[7] * base-1;
   
9.                 }
   
10.                 n /= 10;
    
11.                 base *= 9;
    
12.         }
    
13.         return ret;
    
14. }
    

复制代码

这下没问题了把

910201513

我的思路是先算出位数和最高位，若最高位大于等于6，则不不包括6的数字有（最高位-1）*（（位数-1）个9相乘）
若最大位小于6，则最高位*（（位数-1）个9相乘）/*排列组合*/

参考代码

1. #include<stdio.h>
   
2. #include<string.h>
   
3. #include<stdlib.h>
   
4. #include<math.h>
   
5. int main(void)
   
6. {
   
7.     int r,max,num;
   
8.     char str[40];
   
9.     printf("请输入一个整数：");
   
10.     scanf("%d",&r);
    
11.     max=r;
    
12.     do
    
13.     {
    
14.         max=max/10;
    
15.     }
    
16.     while(max>9);
    
17.     if(max>6)
    
18.     {
    
19.         num=(max-1)*pow(9,strlen(itoa(r,str,10))-1);
    
20.     }
    
21.     else
    
22.     {
    
23.         num=(max)*pow(9,strlen(itoa(r,str,10))-1);
    
24.     }
    
25.     printf("%d",num);
    
26.     system("pause");
    
27.     return 0;
    
28. }

复制代码

缘丿谁懂我一生

缘丿谁懂我一生 发表于 2019-11-23 23:38
还有我自己想了个但是也是结果不对，请大佬修改：

这个有的结果对，有的结果不对是怎么回事