检查一个拼写的数字是否在C ++的范围内
我想检查（数字）input与范围列表（最小，最大），而部分inputinput; 换句话说，我需要一个优雅的algorithm来检查一个数字的前缀与范围（不使用正则expression式）。
样本testing案例：
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 eg 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) 你有什么主意吗？
我相信只有在以下情况下，input才是可接受的：
- 它是转换为string的下界的前缀子string
要么
- input后跟任意数量的附加零（可能没有）落入范围内
第一个规则是例如13 is in range (135, 140)所要求的13 is in range (135, 140) 。 第二个规则是例如2 is in range (1000, 3000)所要求的2 is in range (1000, 3000) 。
第二个规则可以通过一系列乘以10来有效地testing，直到缩放的input超过上限。
迭代公式：
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; }
testing和分析：
#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 eg 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'; } }
令人惊讶的是（至less对我来说）迭代分割出来速度最快：
ecatmur_in_range_mul: 17331000 ecatmur_in_range_div: 14711000 t12_isInRange: 15646000
bool isInRange(int input, int min, int max) { int multiplier = 1; while(input*multiplier <= max) { if(input >= min / multiplier) return true; multiplier *= 10; } return false; }
它通过你所有的testing。
一个简单的解决scheme是生成范围内的所有N位前缀。 所以，对于11 is in ( 5, 12)你需要5到12之间的所有数字的两位数字前缀。显然这只是10,11和12。
通常，对于数字X到Y，可能的N位前缀可以通过以下algorithm获得：
X = MIN(X, 10^(N-1) ) ' 9 has no 2-digit prefix so start at 10 Y = Y - (Y MOD 10^N) ' 1421 has the same 2 digit prefix as 1400 WHILE (X < Y) LIST_PREFIX += PREFIX(N, X) ' Add the prefix of X to the list. X += 10^(TRUNCATE(LOG10(X)) - N+1) ' For N=2, go from 1200 to 1300
给定值n ，以半开范围[ n ， n + 1）开始，并按照数量级继续：
- [10 n ，10（ n + 1））
- [100 n ，100（ n + 1））
- [1000 n ，1000（ n + 1））
- …
继续，直到迭代的范围与目标范围重叠，或者两个范围不能重叠。
#include <iostream> bool overlaps(int a, int b, int c, int d) { return a < c && c < b || c < a && a < d; } bool intersects(int first, int begin, int end) { int last = first + 1; ++end; while (first <= end) { if (overlaps(first, last, begin, end)) return true; first *= 10; last *= 10; } return false; } int main(int argc, char** argv) { std::cout << std::boolalpha << intersects( 1, 5, 9) << '\n' << intersects( 6, 5, 9) << '\n' << intersects( 1, 5, 11) << '\n' << intersects( 1, 5, 200) << '\n' << intersects(11, 5, 12) << '\n' << intersects(13, 5, 12) << '\n' << intersects(13, 5, 22) << '\n' << intersects(13, 5, 200) << '\n' << intersects( 2, 100, 300) << '\n' << intersects(13, 135, 140) << '\n'; }
使用范围是必要的，以防止遗漏的情况。 考虑n = 2和目标范围[21,199]。 2不在范围内，所以我们乘以10; 20不在范围内，所以我们再乘以10; 200不在范围内，也没有更高的数字，所以朴素algorithm终止于假阴性。
我更喜欢使用已经实现的algorithm的方法。 虽然很多其他的解决scheme使用10recursion的划分，但我认为使用O(1)复杂度为10的对数更好，整个解决scheme的复杂度是O(1) 。
让我们把问题分成两部分。
第一部分将处理这样的情况：当number * 10^n在min和max之间至less一个n 。 这将让我们检查例如number = 12和min,max = 11225,13355 ，即x = 12000 = 12*10^3之间的min和max 。 如果这个testing检查出来，这意味着结果是True 。
第二部分将处理number开始时min或max 。 例如，如果number = 12 ， min,max = 12325,14555 ，则第一个testing将失败，因为12000不在min和max之间（并且对于任何n将会失败所有其他数字12*10^n n ）。 但是第二次testing会发现12是12325的开始，并返回True 。
第一
我们来检查一下，如果等于或大于min的第一个x = number*10^n小于或等于max （所以min <= x <= max, where x is number*10^n for any integer n ）。 如果它大于max ，那么所有其他的值都会更大，因为我们取最小值。
log(number*10^n) > log(min) log(number) + log(10^n) > log(min) log(number) + n > log(min) n > log(min) - log(number) n > log(min/number)
为了得到与之比较的数字，我们只计算第一个满意的n ：
n = ceil(log(min/number))
然后计算一下数字x ：
x = number*10^n
第二
我们应该检查我们的数字是否是任何一个边界的文字开始。
我们只是计算x ，以与数字相同的数字开始，最后以0 s填充，长度与min相同：
magnitude = 10**(floor(log10(min)) - floor(log10(number))) x = num*magnitude
然后检查min和x差值（大小标度）是否小于1且大于或等于0 ：
0 <= (min-x)/magnitude < 1
所以，如果number是121 ， min是132125 ，那么magnitude是1000 ， x = number*magnitude是121000 。 min - x给出132125-121000 = 11125 ，应该小于1000 （否则min开始会大于121 ），所以我们把它与magnitude除以它的值并与1进行比较。 如果min是121000 ，那么没关系，但如果min是122000 ，那么OK就122000 ，这就是为什么0 <=和< 1 。
相同的algorithm是max 。
伪代码
把它全部用伪代码给出这个algorithm：
def check(num,min,max): # num*10^n is between min and max #------------------------------- x = num*10**(ceil(log10(min/num))) if x>=min and x<=max: return True # if num is prefix substring of min #------------------------------- magnitude = 10**(floor(log10(min)) - floor(log10(num))) if 0 <= (min-num*magnitude)/magnitude < 1: return True # if num is prefix substring of max #------------------------------- magnitude = 10**(floor(log10(max)) - floor(log10(num))) if 0 <= (max-num*magnitude)/magnitude < 1: return True return False
这个代码可以通过避免重复计算log10(num)来优化。 另外，在最后的解决scheme中，我将从浮点到整数范围（ magnitude = 10**int(floor(log10(max)) - floor(log10(num))) ），然后执行所有的比较而不分割，即0 <= (max-num*magnitude)/magnitude < 1 – > 0 <= max-num*magnitude < magnitude 。 这将减轻舍入错误的可能性。
另外，可以用magnitude = 10**(floor(log10(min/num)))来代替magnitude = 10**(floor(log10(min)) - floor(log10(num))) magnitude = 10**(floor(log10(min/num))) ，其中log10只计算一次。 但是我不能certificate它总会带来正确的结果，我也不能反驳它。 如果有人能certificate这一点，我将非常感激。
testing（使用Python）： http : //ideone.com/N5R2j （您可以编辑input以添加其他testing）。
我来到这个新的简单的解决scheme，同时考虑@Ben Voigt的美丽的解决scheme的certificate：
让我们回到我们进行数字比较的小学。 问题如下：检查数字“ A ”是否在数字“ B ”和数字“ C ”的范围内
解决scheme：在数字的左侧添加必要的零（所有数字都有相同的位数）我们从最左边的数字开始。 将其与另外两个数字中的等同数字进行比较。
-
如果A的数字小于B的数字或大于C的数字，则A不在该范围内。
-
如果不是的话，我们用A的下一个数字和B和C的等价数字来重复这个过程。
重要问题：为什么我们不停在那里？ 为什么我们检查下一个数字？
重要答案：因为从B到C的等价物之间的A的数字到现在为止还没有足够的理由做出决定！ （明显的权利？）
这反过来又意味着可能有一组数字可能使A超出范围。
和LIKEWISE
可能有一组数字可能会把A放在范围内
这是另一种说法A可以是范围内的数字的前缀。
那不是我们要找的？ ：d
该algorithm的主干将基本上是每个input事件的简单比较：
- 在min的左边加上一些零（如果有必要的话），以使min和max的长度相等。
- 将inputA与最小和最大的等同数字进行比较（从左边减去最小和最大的相应数字，而不是右边 ）
- inputA <= 最大的对应部分AND > = 最小的对应部分？ （no：返回false，yes：返回true）
这里的错误和真实expression了“到现在为止”的情况，正如问题所要求的那样。
(input >= lower_bound) && input <= upper_bound OR (f(input) >= lower_bound) && (f(input) <= upper_bound) OR (lower_bound - f(input) < pow(10, n_digits_upper_bound - n_digits_input)) && (lower_bound - f(input) > 0) where f(input) == (input * pow(10, n_digits_upper_bound - n_digits_input)) 1 is in ( 5, 9) -> 1 * pow(10,0) -> same -> false 6 is in ( 5, 9) -> true 1 is in ( 5, 11) -> 1 * pow(10,1) -> 10 is in (5,11) -> true 1 is in ( 5, 200) -> 1 * pow(10,2) -> 100 is in (5, 200) -> true 11 is in ( 5, 12) -> true 13 is in ( 5, 12) -> 13 * pow(10,0) -> same -> false 13 is in ( 5, 22) -> true 13 is in ( 5, 200) -> true 2 is in (100, 300) -> 2 * pow(10,2) -> 200 is in (100,300) -> true 4 is in (100, 300) -> 4 * pow(10,2) -> 400 is in (100,300) -> false 13 is in (135, 140) -> 135 - 130 -> true 14 is in (135, 139) -> 135 - 140 -> false
所有困难的情况都是下界数量less于上界的情况。 只要打破两个（或三个）的范围。 如果AB是集合A和B的并集，则x in AB x in A意味着x in A或者x in B 。 所以：
13 is in (5, 12) => 13 is in (5, 9)或13 is in (10, 12)
13 is in (5, 120) => 13 is in (5, 9)或13 is in (10, 99)或13 is in (100, 120)
然后， 截断以匹配长度。 即
13 is in (5, 120) => 13 is in (5, 9)或13 is in (10, 99)或13 is in (10 , 12 0 )
在第二次重写之后，它变成一个简单的数字检查。 请注意，如果你有10,99的范围出现，那么你有所有可能的2位数的前缀，并不需要检查，但这是一个优化。 （我假设我们忽略前缀00-09）
是的另一个答案。 inputX和界限MIN和MAX
WHILE (X < MIN) IF X is a prefix of MIN x = 10*x + next digit of MIN ELSE x = 10*x RETURN (x>= MIN && x<=MAX)
这是通过“键入”下一个最低的数字。 因此13 in (135, 140)的硬性案例13 in (135, 140)增加了5来产生135，而不是零。
不pipe你select什么样的实现方法，你都应该考虑进行大量的unit testing。 因为你问的问题就像你写testing驱动开发（TDD）的testing一样。 所以我build议，当你正在等待合适的algorithm跳出堆栈溢出时，编写你的unit testing：
如果您提供的示例在您的示例中没有得到结果，则使testing失败。 写一些其他的极限testing用例就可以了。 然后，如果您碰巧使用了错误或错误的algorithm，您很快就会知道。 一旦你的考试通过，你就会知道你已经达到了你的目标。
此外，它将保护你免受未来的任何倒退
也许我在考虑这一点，但假设最小 – 最大整数范围都是正的（即大于或等于零），这个代码块应该很好地做到这一点：
bool CheckRange(int InputValue, int MinValue, int MaxValue) { // Assumes that: // 1. InputValue >= MinValue // 2. MinValue >= 0 // 3. MinValue <= MaxValue // if (InputValue < 0) // The input value is less than zero return false; // if (InputValue > MaxValue) // The input value is greater than max value return false; // if (InputValue == 0 && InputValue < MinValue) return false; // The input value is zero and less than a non-zero min value // int WorkValue = InputValue; // Seed a working variable // while (WorkValue <= MaxValue) { if (WorkValue >= MinValue && WorkValue <= MaxValue) return true; // The input value (or a stem) is within range else WorkValue *= 10; // Not in range, multiply by 10 to check stem again } // return false; }
好，晚会有点晚了，但是这里…
请注意，我们在这里讨论用户input ，所以仅仅// TODO: consider overflow不够的// TODO: consider overflow 。 validation用户input是一场战争，而angular落最终将导致IED爆炸。 （好吧，也许不是那么戏剧化，但仍然…）事实上，ecatmur的有用testing工具中只有一个algorithm可以正确处理拐angular的情况（ {23, 2147483644, 2147483646, false} 23,21447483644,2147483646 {23, 2147483644, 2147483646, false} ），testing工具如果t.max太大，本身就会陷入无限循环。
唯一通过的是ecatmur_in_range_div，我认为这很好。 但是，可以通过添加一些检查来使其稍快一些：
bool in_range_div(int input, int min, int max) { if (input > max) return false; if (input >= min) return true; if (max / 10 >= min) return true; while (input < min) { min /= 10; max /= 10; } return input <= max; }
“取决于”多快？ 如果min和max是编译时常量，那将是特别有用的。 前两个testing是显而易见的，我想; 第三个可以用各种方法certificate，但最简单的方法是观察ecatmur循环的行为：当循环结束时，input> = min但是<10 * min，所以如果10 * min <max，则input必须小于最大值
用分而不是乘法来expression算术应该是一种习惯; 我知道，我们大多数人都是这样想的，即分裂是不合理的 ，必须避免。 但是，不同于乘法，除法不会溢出。 事实上，每当你发现自己写作：
if (a * k < b) ...
要么
for (..., a < b, a *= k)
或这些主题的其他变化，你应该立即将其标记为整数溢出，并将其更改为等效的分区。
实际上，除了一个重要的（但是常见的）情况之外，情况也一样：
if (a + k < b) ...
要么
a += k; if (a < b) ...
也是不安全的， 除非 k是1，并且你知道在加法之前a <b。 这个例外让正常的循环工作没有太多的想法。 但是请注意，这是我曾经用作面试问题的一部分：
// enumerate every kth element of the range [a, b) assert(a < b); for (; a < b; a += k) { ... }
可悲的是，很less有候选人得到它。
我现在要删除这个答案，除了它显示失败的方法。
在检查
Str(min).StartWith(input)，您需要用数字检查是否有任何10^n*Val(input)在范围内，正如Ben Voight当前的答案所述。
失败的尝试
由于本Voigt的评论编辑：（我已经错过了他的第一点在他现在的答案：前缀匹配到最低是好的。
基于@Ben Voigt的见解，我的解决scheme是检查Min与当前input。 如果不是， PadRight当前input以0作为string的Max长度。 然后，如果这个修改后的input在Min和Max之间词法上 （即被当作string处理），那么它是可以的。
伪代码：
Confirm input has only digits, striping leading 0s (most easily done by converting it to an integer and back to a string) check = Str(min).StartsWith(input) If Not check Then testInput = input.PadRight(Len(Str(max)), '0') check = Str(min) <= testInput && testInput <= Str(max) End If
int input = 15; int lower_bound = 1561; int upper_bound = 1567; int ipow = 0; while (lower_bound > 0) { if (lower_bound > input) { ++ipow; lower_bound = lower_bound / 10; } else { int i = pow(10, ipow) * input; if (i < upper_bound) { return true; } return false; } } return false;
