缘丿谁懂我一生 发表于 2019-11-23 22:34:33

算法优化，萌新求助，怎么让计算更快

问题：
       输入一个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:21:58

其实不含6的数相当于9进制的数，按9进制的数的转化方法来计算就行int count6lessnum(int n) {
        int a = { 0,1,2,3,4,5,5,6,7,8 };//10进制与9进制的对应关系
        int ret = 0, base = 1;
        while (n) {
                ret += a * base;
                n /= 10;
                base *= 9;
        }
        return ret;
}

缘丿谁懂我一生 发表于 2019-11-23 23:33:05

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

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

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


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

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

缘丿谁懂我一生 发表于 2019-11-23 23:38:20

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


#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 发表于 2019-11-23 23:42:30

少考虑了中间是6的情况：
int count6lessnum(int n) {
        int a = { 0,1,2,3,4,5,5,6,7,8 };
        int ret = 0, base = 1;
        while (n) {
                ret += a * base;
                if (n % 10 == 6) {
                        ret = a * base-1;
                }
                n /= 10;
                base *= 9;
        }
        return ret;
}

这下没问题了把

910201513 发表于 2019-11-23 23:46:54

我的思路是先算出位数和最高位，若最高位大于等于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;
    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-24 00:29:45

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




这个有的结果对，有的结果不对是怎么回事{:10_266:}
页: [1]
查看完整版本: 算法优化，萌新求助，怎么让计算更快