检查一个数字是否包含在另一个数字中 [英] Check if one number is contained in other number

查看：71
本文介绍了检查一个数字是否包含在另一个数字中的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

任务是检查第二个输入的数字是否包含在第一个输入的数字中.例如:输入:2357 35(是)，2365 35(否).我有这个想法将第一个数字的数字存储在一个数组中，然后查看这些数字是否与第二个数字的数字相同，以及它们的数组索引之间的差异是否为 1.但是，我在编写时遇到了麻烦这在我的代码中，这就是为什么我的函数部分是空的.我是初学者，我真的希望你能帮我写这部分，检查数字是否相同以及它们的索引之间的差异是否为1.不允许使用字符串.

The task is to check if the second input number is contained in the first input number. For example: Input: 2357 35 (YES), 2365 35 (NO). I had this idea to store the digits of the first number in an array and then see if the digits are the same as the digits of the second number and if the difference between their array indexes is 1. But, I am having a trouble writing this in my code and that is why the part of my function is empty. I am a beginner, and I really hope you could help me to write the part with checking if the digits are the same and if the difference between their indexes is 1. Using string is not permitted.

   #include <stdio.h>
    int number_within_number(unsigned int a, unsigned int b){
       int digit,i=0,counter=0,array[10];
       while(a){
               digit=a%10;
               array[i]=digit;
               a/=10;
               i++;
               counter++;
               }
       while(b){
              digit=b%10;
              array[i]=digit;
              b/=10;
              i++;
              counter++;
               }
      for(i=0;i<counter;i++){?
          return 1; }  
      return 0;
  }
   int main(){
              int a,b;
              printf("Enter a: ");
              scanf("%d", &a);
              printf("Enter b: ");
              scanf("%d", &b);
              if(number_within_number(a,b)==1)
              printf("YES");
              if(number_within_number(a,b)==0)
              printf("NO");
              }

推荐答案

简单/显而易见的方法是使用 sprintf 从数字中获取数字字符串.然后，使用 strstr 查看较小的数字(例如 needle)是否包含在较大的数字(例如 haystack)中.

The easy/obvious way is to use sprintf to get a digit string from a number. Then, use strstr to see if the smaller number (e.g. needle) is contained in the larger number (e.g. haystack).

创建数字数组是一种类似的方法.

Creating arrays of digits is a similar approach.

但是……

有一种更直接的方法可能会更快(快 6 倍).

There is a more direct approach that may be faster (6x faster).

  1. 计算大于 needle 的 10 的幂.(例如 10、100、1000 等).调用这个 mod10.
  2. 计算haystack % mod10.
  3. 如果它等于 needle，我们就有一个匹配项.
  4. 如果不是，将 haystack 除以 10
  5. 重复只要haystack >=need
  1. Calculate the power of 10 that is greater than needle. (e.g. 10, 100, 1000, etc.). Call this mod10.
  2. Compute haystack % mod10.
  3. We have a match if this equals needle.
  4. If not, divide haystack by 10
  5. Repeat as long as haystack >= needle

例如，对于 2357 35，mod10 将为 100:

For example, for 2357 35, mod10 will be 100:

2357 % 100 == 57
235 % 100  == 35

对于 2365 35，mod10 是 100:

For 2365 35, mod10 is 100:

2365 % 100 == 65
236 % 100  == 36

无论如何，这里有一些经过测试的代码:

Anyway here's some code with some testing:

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

#ifdef DEBUG
#define dbgprt(_lvl,_fmt...) \
    do { \
        if (opt_d >= _lvl) \
            printf(_fmt); \
    } while (0)
#else
#define dbgprt(_fmt...) \
    do { } while (0)
#endif

int opt_d;
int opt_n;

// match_mod10 -- fast/direct
int
match_mod10(int hay,int need)
{
    int mod10;
    int haymod;
    int match = 0;

    for (mod10 = 1;  mod10 <= need;  mod10 *= 10);
    dbgprt(2,"mod10=%d\n",mod10);

    while (hay >= need) {
        haymod = hay % mod10;

        dbgprt(2,"hay=%d need=%d haymod=%d\n",hay,need,haymod);

        match = (haymod == need);
        if (match)
            break;

        hay /= 10;
    }

    return match;
}

// match_strstr -- reference implementation
int
match_strstr(int hay,int need)
{
    char haybuf[100];
    char needbuf[100];
    int match;

    sprintf(haybuf,"%d",hay);
    sprintf(needbuf,"%d",need);

    match = (strstr(haybuf,needbuf) != NULL);

    return match;
}

void
dotest(int hay,int need)
{
    int strflg;
    int modflg;
    int fail;

    // get reference value
    if (opt_n)
        strflg = 0;
    else
        strflg = match_strstr(hay,need);

    modflg = match_mod10(hay,need);
    if (opt_n)
        fail = 0;
    else
        fail = (strflg != modflg);

    if (opt_d || fail) {
        printf("%d %d -- strflg=%d modflg=%d %s\n",
            hay,need,strflg,modflg,fail ? "FAIL" : "PASS");
        if (fail)
            exit(1);
    }
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'd':
            opt_d = (*cp != 0) ? atoi(cp) : 1;
            break;
        case 'n':
            opt_n = ! opt_n;
            break;
        }
    }

    do {
        int hay;
        int need;

        if (argc == 2) {
            hay = atoi(argv[0]);
            need = atoi(argv[1]);
            dotest(hay,need);
            break;
        }

        for (need = 2;  need <= 99;  ++need) {
            for (hay = 1;  hay < 1000000;  ++hay)
                dotest(hay,need);
        }

        printf("FINAL: %d %d\n",hay,need);
    } while (0);

    return 0;
}

更新:

来自阿曼:

根据 Craig Estey 的想法，根据他的想法，您可以在没有数组的情况下轻松编码，并且效率会更高.这里我写了函数.

with Craig Estey's idea, By his idea, you can easily code without the array and it will be more efficient. Here I have written the function.

有人使用并改编为回答他们的答案而编写的代码是一件很受人欢迎的事.

It's flattering to have someone use and adapt code written for an answer for their answer.

我决定对各种算法进行基准测试.

I decided to benchmark the various algorithms.

虽然 Aman 的适应速度看起来很快，但实际上它会减慢速度.除了 [reference] strstr 之外，它比其他所有方法都慢.

Although Aman's adaptation seems fast, it actually slows things down. It was slower than every other method except the [reference] strstr.

我的算法和 Aman 的算法都具有相同的最终循环.

Both my algorithm and Aman's have the same final loop.

但是，mod10 算法使用了一个使用乘法的循环.Aman 使用了除法 [比乘法慢].

But, mod10 algorithm used a single loop that used a multiply. Aman's used a divide [which is slower than multiply].

然后，它使用了 pow——这是 昂贵的.这可以用带乘法的循环代替以获得一些加速.

And, then, it used pow--this is expensive. This can be replaced with a loop with a multiply to get some speedup.

我修改了原始的 mod10 方法以使用 mod10 值的缓存/记忆.这提供了一些进一步的加速

I modified the original mod10 method to use caching/memoization of the mod10 value. This provided some further speedup

这是基准输出:

HAY: 1 1000000
NEED: 2 99
TESTS: strstr strstr2 array array2 mod10 aman1 aman2 mod10b

Sorted:
23.726686639 strstr -- sprintf/strstr reference
13.021570598 strstr2 (1.822x faster) (1.822x faster) -- sprintf/strstr (cached)
3.827459623 aman1 (3.402x faster) (6.199x faster) -- Aman's original (with pow)
3.265761858 array (1.172x faster) (7.265x faster) -- decode numbers into arrays
2.875820484 array2 (1.136x faster) (8.250x faster) -- arrays (cached)
2.826747834 aman2 (1.017x faster) (8.394x faster) -- Aman's modified (multiply)
1.873383061 mod10 (1.509x faster) (12.665x faster) -- mod10 algorithm
1.803308872 mod10b (1.039x faster) (13.157x faster) -- mod10 (with caching)

这是基准代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define XFLUSH \
    do { \
        if (! hangflg) \
            break; \
        fputc('\n',stdout); \
        hangflg = 0; \
    } while (0)

int hangflg;

#define dbgok(_lvl) \
    _dbgok(#_lvl[0])

#ifdef DEBUG
#define dbgprt(_lvl,_fmt...) \
    do { \
        if (! dbgok(_lvl)) \
            break; \
        XFLUSH; \
        printf(_fmt); \
    } while (0)
#else
#define dbgprt(_fmt...) \
    do { } while (0)
#endif

typedef long long tsc_t;
typedef unsigned int u32;
typedef unsigned char byte;

int opt_c;
int opt_q;
byte opt_d[256];

int haylim[2];
int needlim[2];
int mod10b_redo;

int outflg = 1;

#define outprt(_fmt...) \
    do { \
        if (outflg) \
            printf(_fmt); \
    } while (0)

static inline byte
_dbgok(int lvl)
{

    return opt_d[(byte) lvl];
}

tsc_t
tscget(void)
{
    struct timespec ts;
    tsc_t tsc;

    clock_gettime(CLOCK_MONOTONIC,&ts);
    tsc = ts.tv_sec;
    tsc *= 1000000000;
    tsc += ts.tv_nsec;

    return tsc;
}

double
tscsec(tsc_t tsc)
{
    double sec;

    sec = tsc;
    sec /= 1e9;

    return sec;
}

// match_mod10 -- fast/direct
int
match_mod10(int hay,int need)
{
    int mod10;
    int haymod;
    int match = 0;

    for (mod10 = 1;  mod10 <= need;  mod10 *= 10);
    dbgprt(L,"mod10=%d\n",mod10);

    while (hay >= need) {
        haymod = hay % mod10;

        dbgprt(L,"hay=%d need=%d haymod=%d\n",hay,need,haymod);

        match = (haymod == need);
        if (match)
            break;

        hay /= 10;
    }

    return match;
}

// match_mod10b -- fast/direct (cached)
int
match_mod10b(int hay,int need)
{
    static int limlo = 0;
    static int limhi = -1;
    int mod10;
    int haymod;
    int match = 0;

    if ((need >= limhi) || (need < limlo)) {
        limlo = 1;
        limhi = 1;
        for (mod10 = 1;  mod10 <= need;) {
            limlo = mod10;
            mod10 *= 10;
            limhi = mod10;
        }
        ++mod10b_redo;
        dbgprt(N,"DEBUG: need=%d mod10=%d limlo=%d limhi=%d mod10b_redo=%d\n",
            need,mod10,limlo,limhi,mod10b_redo);
    }
    mod10 = limhi;

    while (hay >= need) {
        haymod = hay % mod10;

        dbgprt(L,"hay=%d need=%d haymod=%d\n",hay,need,haymod);

        match = (haymod == need);
        if (match)
            break;

        hay /= 10;
    }

    return match;
}

// match_strstr -- reference implementation
int
match_strstr(int hay,int need)
{
    char haybuf[100];
    char needbuf[100];
    int match;

    sprintf(haybuf,"%d",hay);
    sprintf(needbuf,"%d",need);

    match = (strstr(haybuf,needbuf) != NULL);

    return match;
}

// match_strstr -- reference implementation (cached)
int
match_strstr2(int hay,int need)
{
    static int hayold = -1;
    static char haybuf[100];
    static int needold = -1;
    static char needbuf[100];
    int match;

    if (hay != hayold) {
        sprintf(haybuf,"%d",hay);
        hayold = hay;
    }

    if (need != needold) {
        sprintf(needbuf,"%d",need);
        needold = need;
    }

    match = (strstr(haybuf,needbuf) != NULL);

    return match;
}

int
_match_array(int hay,char *haybuf)
{
    char *hayp;

    for (hayp = haybuf;  hay != 0;  ++hayp) {
        *hayp = hay % 10;
        hay /= 10;
    }

    return (hayp - haybuf);
}

// match_array -- array
int
match_array(int hay,int need)
{
    int match = 0;

    char haybuf[100];
    int haylen = _match_array(hay,haybuf);

    char needbuf[100];
    int needlen = _match_array(need,needbuf);

    char *haye = &haybuf[haylen - needlen];
    for (char *hayp = haybuf;  hayp <= haye;  ++hayp) {
        for (int needidx = 0;  needidx < needlen;  ++needidx) {
            match = (hayp[needidx] == needbuf[needidx]);
            dbgprt(L,"match_array: TRY needidx=%d hayp=%d needbuf=%d match=%d\n",
                needidx,hayp[needidx],needbuf[needidx],match);
            if (! match)
                break;
        }
        if (match)
            break;
    }

    return match;
}

// match_array2 -- array (cached)
int
match_array2(int hay,int need)
{
    int match = 0;

    static int hayold = -1;
    static int haylen = -1;
    static char haybuf[100];
    if (hay != hayold) {
        haylen = _match_array(hay,haybuf);
        hayold = hay;
        dbgprt(H,"match_array: HAYSET hay=%d haylen=%d\n",hay,haylen);
    }

    static int needold = -1;
    static int needlen = -1;
    static char needbuf[100];
    if (need != needold) {
        needlen = _match_array(need,needbuf);
        needold = need;
        dbgprt(N,"match_array: NEEDSET need=%d needlen=%d\n",need,needlen);
    }

    char *haye = &haybuf[haylen - needlen];
    for (char *hayp = haybuf;  hayp <= haye;  ++hayp) {
        for (int needidx = 0;  needidx < needlen;  ++needidx) {
            match = (hayp[needidx] == needbuf[needidx]);
            dbgprt(L,"match_array: TRY needidx=%d hayp=%d needbuf=%d match=%d\n",
                needidx,hayp[needidx],needbuf[needidx],match);
            if (! match)
                break;
        }
        if (match)
            break;
    }

    return match;
}

#if 0
typedef u32 arg_t;
#else
typedef int arg_t;
#endif

int
match_aman1(arg_t a, arg_t b)
{
    int temp, b_size = 0, tens = 1;

    temp = b;

    // finding total digits in b
    while (temp) {
        b_size++;
        temp /= 10;
    }

    tens = pow(10, b_size);

    while (a) {
        if ((a % tens) == b)
            return 1;
        a /= 10;
    }

    return 0;
}

int
match_aman2(arg_t a, arg_t b)
{
    int temp, b_size = 0, tens = 1;

    temp = b;

    // finding total digits in b
    while (temp) {
        b_size++;
        temp /= 10;
    }

#if 0
    tens = pow(10, b_size);
#else
    for (;  b_size > 0;  --b_size)
        tens *= 10;
#endif

    while (a) {
        if ((a % tens) == b)
            return 1;
        a /= 10;
    }

    return 0;
}

typedef struct {
    int (*tst_fnc)(int hay,int need);
    const char *tst_tag;
    const char *tst_reason;
    int tst_enable;
    tsc_t tst_elap;
} tst_t;
typedef tst_t *tst_p;
typedef const tst_t *tst_pc;

#define TST(_fnc,_reason) \
    { \
        .tst_fnc = _fnc, \
        .tst_tag = #_fnc, \
        .tst_reason = _reason, \
        .tst_enable = 1 \
    }

tst_t tstlist[] = {
    TST(match_strstr,"sprintf/strstr reference"),
    TST(match_strstr2,"sprintf/strstr (cached)"),
    TST(match_array,"decode numbers into arrays"),
    TST(match_array2,"arrays (cached)"),
    TST(match_mod10,"mod10 algorithm"),
    TST(match_aman1,"Aman's original (with pow)"),
    TST(match_aman2,"Aman's modified (multiply)"),
    TST(match_mod10b,"mod10 (with caching)"),
    { .tst_tag = NULL }
};

#define TSTFORALL(_tst) \
    _tst = tstlist;  _tst->tst_tag != NULL;  ++_tst

const char *
tagof(tst_pc tstcur)
{
    const char *cp;
    const char *tag;

    tag = tstcur->tst_tag;

    cp = strrchr(tag,'_');
    if (cp != NULL)
        tag = cp + 1;

    return tag;
}

void
dochk(int hay,int need)
{
    tst_p tstcur;
    tst_p tstold = NULL;
    int oldflg;
    int curflg;
    int fail;

    for (TSTFORALL(tstcur)) {
        curflg = tstcur->tst_fnc(hay,need);

        if (tstold == NULL) {
            tstold = tstcur;
            oldflg = curflg;
        }
        fail = (curflg != oldflg);

        if (dbgok(C) || fail) {
            if (fail)
                XFLUSH;
            printf("%d %d -- %s=%d %s=%d %s\n",
                hay,need,
                tagof(tstold),oldflg,
                tagof(tstcur),curflg,
                fail ? "FAIL" : "PASS");
            if (fail)
                exit(1);
        }

        tstold = tstcur;
        oldflg = curflg;
    }
}

void
dochkall(void)
{
    int hay;

    hay = haylim[0];

    mod10b_redo = 0;
    for (int iter = 1;  iter <= 10;  ++iter) {
        for (int need = needlim[0];  need <= needlim[1];  ++need)
            dochk(hay,need);
    }

    tsc_t tscbeg = tscget();

    mod10b_redo = 0;
    for (int need = needlim[0];  need <= needlim[1];  ++need) {
        printf("\rneed: %d ",need);
        hangflg = 1;

        fflush(stdout);
        for (hay = haylim[0];  hay <= haylim[1];  ++hay)
            dochk(hay,need);
    }
    tsc_t tscend = tscget();
    tscend -= tscbeg;

    XFLUSH;
    printf("ELAPSED: %.9f\n",tscsec(tscend));
}

void
dorat(double elap,tsc_t tscold)
{
    double ratio = tscsec(tscold);
    const char *tag;

    ratio /= elap;
    if (ratio < 1.0) {
        tag = "slower";
        ratio = 1.0 / ratio;
    }
    else
        tag = "faster";

    outprt(" (%.3fx %s)", ratio,tag);
}

int
tstcmp(const void *vplhs,const void *vprhs)
{
    tst_pc tstlhs = vplhs;
    tst_pc tstrhs = vprhs;
    tsc_t dif;
    int cmp;

    dif = tstrhs->tst_elap - tstlhs->tst_elap;

    cmp = 0;
    if (dif < 0)
        cmp = -1;
    if (dif > 0)
        cmp = 1;

    dbgprt(D,"tstcmp: DIF %.9f %.9f dif=%lld cmp=%d\n",
        tscsec(tstrhs->tst_elap),tscsec(tstlhs->tst_elap),dif,cmp);

    return cmp;
}

int ratflg;

void
dotsc(tst_p tstcur)
{
    tsc_t tscelap = tstcur->tst_elap;
    static tsc_t tscref;
    static tsc_t tscold;

    if (! ratflg) {
        tscref = tscelap;
        tscold = tscelap;
    }

    double elap = tscsec(tscelap);
    outprt("%.9f %s",elap,tagof(tstcur));

    if (ratflg) {
        dorat(elap,tscold);
        dorat(elap,tscref);
    }

    ratflg = 1;

    if (tstcur->tst_reason != NULL)
        outprt(" -- %s",tstcur->tst_reason);

    outprt("\n");

    tscold = tscelap;
}

void
dotscall(void)
{
    tst_p tstcur;
    tsc_t tscelap;

    outflg = ! opt_q;
    outprt("\n");
    outprt("Unordered:\n");
    ratflg = 0;
    for (TSTFORALL(tstcur)) {
        tsc_t tscbeg = tscget();

        for (int need = needlim[0];  need <= needlim[1];  ++need) {
            for (int hay = haylim[0];  hay <= haylim[1];  ++hay)
                tstcur->tst_fnc(hay,need);
        }

        tscelap = tscget();
        tscelap -= tscbeg;
        tstcur->tst_elap = tscelap;

        dotsc(tstcur);
    }

    int tstcnt = 0;
    for (TSTFORALL(tstcur), ++tstcnt);
    qsort(tstlist,tstcnt,sizeof(tst_t),tstcmp);

    outflg = 1;
    outprt("\n");
    outprt("Sorted:\n");
    ratflg = 0;
    for (TSTFORALL(tstcur))
        dotsc(tstcur);
}

void
rangeget(char *cp,int *lim)
{

    lim[0] = -1;
    lim[1] = -1;

    lim[0] = strtol(cp,&cp,10);
    if (*cp++ == ',')
        lim[1] = strtol(cp,&cp,10);
    else
        lim[1] = lim[0];
}

void
tstopt(char *bp)
{
    static int initflg = 1;
    tst_p tstcur;
    char *cp;
    char **av;
    char *argv[100];
    int negflg;

    av = argv;
    while (1) {
        cp = strtok(bp,",");
        *av = cp;

        if (cp == NULL)
            break;

        bp = NULL;
        ++av;
    }

    if (initflg) {
        initflg = 0;

        negflg = 0;
        for (av = argv;  *av != NULL;  ++av) {
            if (strchr(*av,'-') != NULL) {
                negflg = 1;
                break;
            }
        }

        for (TSTFORALL(tstcur))
            tstcur->tst_enable = negflg;
    }

    for (av = argv;  *av != NULL;  ++av) {
        bp = *av;
        cp = strrchr(bp,'-');

        negflg = (cp != NULL);
        if (negflg)
            *cp = 0;

        for (TSTFORALL(tstcur)) {
            const char *tag = tagof(tstcur);
            if (strcmp(tag,bp) == 0) {
                tstcur->tst_enable = ! negflg;
                break;
            }
        }
    }
}

void
dbgopt(char *bp)
{

    if (*bp == 0) {
        memset(opt_d,1,sizeof(opt_d));
        printf("dbgopt: enable all\n");
    }

    for (;  *bp != 0;  ++bp) {
        opt_d[(byte) *bp] = 1;
        printf("dbgopt: enable %c\n",*bp);
    }
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'c':  // check mode
            opt_c = ! opt_c;
            break;
        case 'd':
            dbgopt(cp);
            break;
        case 'q':
            opt_q = ! opt_q;
            break;
        case 'T':
            tstopt(cp);
            break;
        }
    }

    do {
        if (argc == 2) {
            rangeget(argv[0],haylim);
            rangeget(argv[1],needlim);
            break;
        }

        rangeget("1,1000000",haylim);
        rangeget("2,99",needlim);
    } while (0);
    printf("HAY: %d %d\n",haylim[0],haylim[1]);
    printf("NEED: %d %d\n",needlim[0],needlim[1]);

    printf("TESTS:");
    tst_p tstrhs;
    tst_p tstlhs = tstlist;
    for (TSTFORALL(tstrhs)) {
        if (! tstrhs->tst_enable)
            continue;
        printf(" %s",tagof(tstrhs));

        if (tstlhs != tstrhs)
            *tstlhs = *tstrhs;
        ++tstlhs;
    }
    printf("\n");
    tstlhs->tst_tag = NULL;

    do {
        if (! opt_c) {
            dotscall();
            break;
        }

        dochkall();
    } while (0);

    dbgprt(N,"DEBUG: mod10b_redo=%d\n",mod10b_redo);

    return 0;
}

这篇关于检查一个数字是否包含在另一个数字中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆