检查拼写的数字是否在C++范围内

Question

我想在输入部分输入时检查范围列表(最小值,最大值)的(数字)输入; 换句话说,我需要一个优雅的算法来检查一个数字的前缀与一个范围(不使用正则表达式).

样本测试用例:

 1 is in (  5,   9) -> false
 6 is in (  5,   9) -> true
 1 is in (  5,  11) -> true  (as 10 and 11 are in the range)
 1 is in (  5, 200) -> true  (as e.g. 12 and 135 are in the range)
11 is in (  5,  12) -> true
13 is in (  5,  12) -> false 
13 is in (  5,  22) -> true
13 is in (  5, 200) -> true  (as 130 is in the range)
 2 is in (100, 300) -> true  (as 200 is in the range)

你有什么主意吗？

Answer 1

我相信,当且仅当以下情况之一时,输入才是可接受的:

• 它是转换为字符串的下限的前缀子字符串

要么

• 输入后跟任意数量的附加零(可能没有)都属于该范围

例如,第一条规则是必需的13 is in range (135, 140).第二条规则是例如2 is in range (1000, 3000).

可以通过一系列乘以10来有效地测试第二规则,直到缩放的输入超过上限.

Answer 2

迭代公式:

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;    // FIXME handle negative and zero-prefixed numbers
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

更简单[编辑:更有效; 见下面]方法是使用截断整数除法:

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

测试和分析:

#include <iostream>
#include <chrono>

bool ecatmur_in_range_mul(int input, int min, int max)
{
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

bool ecatmur_in_range_div(int input, int min, int max)
{
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

bool t12_isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = {
{ ecatmur_in_range_mul, "ecatmur_in_range_mul"},
{ ecatmur_in_range_div, "ecatmur_in_range_div"},
{ t12_isInRange, "t12_isInRange"},
};

struct test { int input, min, max; bool result; } tests[] = {
{  1,   5,   9, false },
{  6,   5,   9, true },
{  1,   5,  11, true }, // as 10 and 11 are in the range
{  1,   5, 200, true }, // as e.g. 12 and 135 are in the range
{ 11,   5,  12, true },
{ 13,   5,  12, false },
{ 13,   5,  22, true },
{ 13,   5, 200, true }, // as 130 is in the range
{  2, 100, 300, true }, // as 200 is in the range
{ 13, 135, 140, true }, // Ben Voigt
{ 13, 136, 138, true }, // MSalters
};
int main() {
    for (auto a: algos)
        for (auto t: tests)
            if (a.fn(t.input, t.min, t.max) != t.result)
                std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != "
                    << t.result << "\n";

    for (auto a: algos) {
        std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
        for (auto t: tests)
            for (int i = 1; i < t.max * 2; ++i)
                for (volatile int j = 0; j < 1000; ++j) {
                    volatile bool r = a.fn(i, t.min, t.max);
                    (void) r;
                }
        std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
        std::cout << a.name << ": "
            << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n';
    }
}

令人惊讶的是(至少对我来说)迭代分工最快:

ecatmur_in_range_mul: 17331000
ecatmur_in_range_div: 14711000
t12_isInRange: 15646000