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

缘丿谁懂我一生

问题：
         输入一个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的情况：

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

这下没问题了把

跳转到最佳答案楼层

Croper

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

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;
}

缘丿谁懂我一生

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的情况：

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

这下没问题了把

910201513

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

参考代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main(void)
{
    int r,max,num;
    char str[40];
    printf("请输入一个整数：");
    scanf("%d",&r);
    max=r;
    do
    {
        max=max/10;
    }
    while(max>9);
    if(max>6)
    {
        num=(max-1)*pow(9,strlen(itoa(r,str,10))-1);
    }
    else
    {
        num=(max)*pow(9,strlen(itoa(r,str,10))-1);
    }
    printf("%d",num);
    system("pause");
    return 0;
}

缘丿谁懂我一生

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

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