C语言从数字n到m有多少的不带4的整数

客官°小女子只卖身不卖艺 2022-09-30 06:16 122阅读 0赞

## **C语言从数字n到m有多少的不带4的整数** ##

#include<stdio.h>
    #define min(a,b) a>b?b:a
    #define max(a,b) a>b?a:b
    int count;
    int maxn = 1000000;
    long long a[1000000];
    int judge(int n)
    {
        while(n)
        {
            int x = n%10;
            if(x == 4)
                return 0;
            n/=10;
        }
        return 1;
    }
    void init()
    {
        a[1] = 1;
        a[2] = 2;
        for(int i=3; i<=maxn; i++)
        {
            if(judge(i) == 1)
            {
                a[i] += a[i-1]+1;
            }
            else
            {
                a[i] = a[i-1];
            }
        }
    }
    int main()
    {
        int t;
        init();
        while(~scanf("%d",&t))
        {
            while(t--)
            {
                int n,m;
                scanf("%d %d",&n,&m);
                int Min = min(n,m);
                int Max = max(n,m);
                printf("%lld\n",a[Max]-a[Min-1]);
            }
        }
        return 0;
     }

这里使用 void init() 来把不含4的整数写入数组，利用判断方法隔去含4的数字，最后只需要用 a\[Max\]-a\[Min-1\] 计算即可，复杂度（小白不会算，应该简单点吧）

**另一种方法就是一个一个算，太费时间了**

int judge(int n)
    {
        while(n)
        {
            int x = n%10;
            if(x == 4)
                return 0;
            n/=10;
        }
        return 1;
    }

简单粗暴

欢迎讨论更简单的方法