检查数字是否为吸血鬼数字的最快方法？
Fastest way to check if a number is a vampire number?
这里定义了一个吸血鬼号https://en.wikipedia.org/wiki/Vampire_number。数字 V 是吸血鬼数字，如果：
- 它可以表示为 X*Y 使得 X 和 Y 各有 N/2 位，其中 N 是 V 中的位数
- X 和 Y 都不应有尾随零
- X & Y 一起应该和 V 有相同的数字
我想出了一个解决办法，
strV = sort(toString(V))
for factor <- pow(10, N/2) to sqrt(V)
if factor divides V
X <- factor
Y <- V/factor
if X and Y have trailing zeros
continue
checkStr = sort(toString(X) + toString(Y))
if checkStr equals strV return true
另一种可能的解决方案是将V代表的字符串排列并分成两半，然后检查它是否是吸血鬼数字。哪种方法最好？
这里有一些建议：
首先是一个简单的改进：如果位数<4或奇数return false（或者如果v也是负数）。
不需要排序v，统计每个数字出现多少次O(n)即可。
您不必检查每个数字，只需检查数字可能的组合。这可以通过回溯来完成，并显着减少必须检查的数字量。
检查是否所有数字都被使用的最后排序也不需要，只需将两个数字的使用数字相加并与 v.[=15 中出现的次数进行比较=]
这里是类 JS 语言的代码，整数永不溢出，V 参数是一个不带前导 0 的整数字符串：
编辑： 事实证明，代码不仅是 JS-like，而且是有效的 JS 代码，并且没有问题确定 1047527295416280 确实是一个吸血鬼号码 (jsfiddle)。
var V, v, isVmp, digits, len;
function isVampire(numberString) {
V = numberString;
if (V.length < 4 || V.length % 2 == 1 )
return false;
v = parseInt(V);
if (v < 0)
return false;
digits = countDigits(V);
len = V.length / 2;
isVmp = false;
checkNumbers();
return isVmp;
}
function countDigits(s) {
var offset = "0".charCodeAt(0);
var ret = [0,0,0,0,0,0,0,0,0,0];
for (var i = 0; i < s.length; i++)
ret[s.charCodeAt(i) - offset]++;
return ret;
}
function checkNumbers(number, depth) {
if (isVmp)
return;
if (typeof number == 'undefined') {
for (var i = 1; i < 10; i++) {
if (digits[i] > 0) {
digits[i]--;
checkNumbers(i, len - 1);
digits[i]++;
}
}
} else if (depth == 0) {
if (v % number == 0) {
var b = v / number;
if (number % 10 != 0 || b % 10 != 0) {
var d = countDigits('' + b);
if (d[0] == digits[0] && d[1] == digits[1] && d[2] == digits[2] &&
d[3] == digits[3] && d[4] == digits[4] && d[5] == digits[5] &&
d[6] == digits[6] && d[7] == digits[7] && d[8] == digits[8] &&
d[9] == digits[9])
isVmp = true;
}
}
} else {
for (var i = 0; i < 10; i++) {
if (digits[i] > 0) {
digits[i]--;
checkNumbers(number * 10 + i, depth - 1);
digits[i]++;
}
}
}
}
在伪代码中：
if digitcount is odd return false
if digitcount is 2 return false
for A = each permutation of length digitcount/2 selected from all the digits,
for B = each permutation of the remaining digits,
if either A or B starts with a zero, continue
if both A and B end in a zero, continue
if A*B == the number, return true
此处仍有许多优化可以执行，主要是确保每对可能的因素只尝试一次。换句话说，如何在选择排列时最好地检查重复数字？
但这就是我要使用的算法的要点。
P.S.: 你不是在寻找素数，那么为什么要使用素数测试呢？你只关心这些是不是vampire数字；只有极少数可能的因素。无需检查所有数字直到 sqrt(number).
我在这里提出的算法不会遍历所有数字排列。它将尽可能快地消除可能性，以便实际上只测试一小部分排列。
通过示例解释算法
以下是基于示例编号 125460 的工作原理。如果您可以直接阅读代码，则可以跳过此（长）部分：
一开始两个毒牙（即吸血鬼因素）显然是不知道的，问题可以表示如下：
?**
X ?**
-------
=125460
对于第一个因素最左边的数字（标记为 ?），我们可以选择 0、1、2、5、4 或 6 中的任何一个数字。但仔细分析，0 不会是一种可行的可能性，因为产品永远不会超过 5 位数字。因此，遍历所有以零开头的数字排列是浪费时间。
对于第二个因数最左边的数位（也标有?），同理。但是，在查看组合时，我们可以再次过滤掉一些无法帮助实现目标产品的对。例如，这个组合应该被丢弃：
1**
X 2**
-------
=125460
用这些数字可以得到的最大数字是 199x299 = 59501（忽略我们连 9 都没有的事实），这甚至不到所需数字的一半。所以我们应该拒绝组合 (1, 2)。出于同样的原因，可以丢弃对 (1, 5) 以占据这些位置。类似地，对 (4, 5)、(4, 6) 和 (5, 6) 也可以被拒绝，因为它们产生的产品太大 (>= 200000)。我将这种类型称为测试——确定目标号码是否在某个选定数字对 "range test".
的范围内
在这个阶段，第一颗和第二颗尖牙之间没有区别，所以我们也不必研究第二个数字小于第一个的一对，因为它们反映了一对已经被研究过的（或拒绝）。
所以在所有可能占据第一个位置的对中（有 30 种可能性从一组 6 位数字中取出 2 位数字），只需要研究以下 4 位：
(1, 6), (2, 4), (2, 5), (2, 6)
在更详细的表示法中，这意味着我们将搜索限制在这些数字模式中：
1** 2** 2** 2**
X 6** X 4** X 5** X 6**
------- ------- ------- -------
=125460 =125460 =125460 =125460
A B C D
很明显，这种在查看其他位置之前就减少了可能性大大减少了搜索树。
该算法将按顺序考虑这 4 种可能性中的每一种，并针对每种可能性检查下一个数字位置的可能性。所以先分析配置A：
1?*
X 6?*
-------
=125460
可用于 ? 标记位置的对是这 12 个：
(0, 2), (0, 4), (0, 5)
(2, 0), (2, 4), (2, 5)
(4, 0), (4, 2), (4, 5)
(5, 0), (5, 2), (5, 4)
同样，我们可以通过应用范围测试来消除对。让我们以一对 (5, 4) 为例。这意味着我们有因子 15* 和 64*（此时 * 是未知数字）。这两者的乘积将最大化为 159 * 649，即 103191（再次忽略我们甚至没有 9 可用的事实）：这对于达到目标来说太低了，因此可以忽略这一对。通过进一步应用范围测试，可以丢弃所有这12对，因此配置A内的搜索到此为止：那里没有解决方案。
然后算法移动到配置 B:
2?*
X 4?*
-------
=125460
再次，范围测试应用于第二个位置的可能对，结果再次证明这些对中的 none 通过了测试：例如 (5, 6) 永远不能代表更大的产品比 259 * 469 = 121471，这（只是）太小了。
然后算法移动到选项 C:
2?*
X 5?*
-------
=125460
在所有 12 个可能的对中，只有以下对可以通过范围测试：(4, 0), (4, 1), (6, 0), (6, 1)。所以现在我们有如下二级配置：
24* 24* 26* 26*
X 50* X 51* X 50* X 51*
------- ------- ------- -------
=125460 =125460 =125460 =125460
Ca Cb Cc Cd
在配置Ca中，没有一对通过范围测试。
在配置 Cb 中，对 (6, 0) 通过，并导致解决方案：
246
X 510
-------
=125460
此时算法停止搜索。结果很明显。与蛮力排列检查算法相比，所查看的配置总数非常少。这是搜索树的可视化：
*-+-- (1, 6)
|
+-- (2, 4)
|
+-- (2, 5) -+-- (4, 0)
| |
| +-- (4, 1) ---- (6, 0) = success: 246 * 510
/ /
| +-- (6, 0)
| |
| +-- (6, 1)
|
+-- (2, 6) ---- (0, 1) ---- (4, 5) = success: 204 * 615
下面的变体 / 仅用于显示算法在未找到解决方案的情况下还能做什么。但在这个实际案例中，搜索树的那部分实际上从未被跟踪过。
我不清楚时间复杂度，但似乎 运行 对于较大的数字相当好，表明在早期阶段消除数字会使搜索树的宽度非常窄。
这是一个实时 JavaScript 实现，它在激活时也会 运行 一些测试用例（并且它还有一些其他优化 -- 请参阅代码注释）。
/*
Function: vampireFangs
Arguments:
vampire: number to factorise into two fangs, if possible.
Return value:
Array with two fangs if indeed the argument is a vampire number.
Otherwise false (not a vampire number) or null (argument too large to
compute)
*/
function vampireFangs(vampire) {
/* Function recurse: for the recursive part of the algorithm.
prevA, prevB: partial, potential fangs based on left-most digits of the given
number
counts: array of ten numbers representing the occurrence of still
available digits
divider: power of 100, is divided by 100 each next level in the search tree.
Determines the number of right-most digits of the given number that
are ignored at first in the algorithm. They will be considered in
deeper levels of recursion.
*/
function recurse(vampire, prevA, prevB, counts, divider) {
if (divider < 1) { // end of recursion
// Product of fangs must equal original number and fangs must not both
// end with a 0.
return prevA * prevB === vampire && (prevA % 10 + prevB % 10 > 0)
? [prevA, prevB] // Solution found
: false; // It's not a solution
}
// Get left-most digits (multiple of 2) of potential vampire number
var v = Math.floor(vampire/divider);
// Shift decimal digits of partial fangs to the left to make room for
// the next digits
prevA *= 10;
prevB *= 10;
// Calculate the min/max A digit that can potentially contribute to a
// solution
var minDigA = Math.floor(v / (prevB + 10)) - prevA;
var maxDigA = prevB ? Math.floor((v + 1) / prevB) - prevA : 9;
if (maxDigA > 9) maxDigA = 9;
for (var digA = minDigA; digA <= maxDigA; digA++) {
if (!counts[digA]) continue; // this digit is not available
var fangA = prevA + digA;
counts[digA]--;
// Calculate the min/max B digit that can potentially contribute to
// a solution
var minDigB = Math.floor(v / (fangA + 1)) - prevB;
var maxDigB = fangA ? (v + 1) / fangA - prevB : 9;
// Don't search mirrored A-B digits when both fangs are equal until now.
if (prevA === prevB && digA > minDigB) minDigB = digA;
if (maxDigB > 9) maxDigB = 9;
for (var digB = minDigB; digB <= Math.min(maxDigB, 9); digB++) {
if (!counts[digB]) continue; // this digit is not available
var fangB = prevB + digB;
counts[digB]--;
// Recurse by considering the next two digits of the potential
// vampire number, for finding the next digits to append to
// both partial fangs.
var result = recurse(vampire, fangA, fangB, counts, divider / 100);
// When one solution is found: stop searching & exit search tree.
if (result) return result; // solution found
// Restore counts
counts[digB]++;
}
counts[digA]++;
}
}
// Validate argument
if (typeof vampire !== 'number') return false;
if (vampire < 0 || vampire % 1 !== 0) return false; // not positive and integer
if (vampire > 9007199254740991) return null; // beyond JavaScript precision
var digits = vampire.toString(10).split('').map(Number);
// A vampire number has an even number of digits
if (!digits.length || digits.length % 2 > 0) return false;
// Register per digit (0..9) the frequency of that digit in the argument
var counts = [0,0,0,0,0,0,0,0,0,0];
for (var i = 0; i < digits.length; i++) {
counts[digits[i]]++;
}
return recurse(vampire, 0, 0, counts, Math.pow(10, digits.length - 2));
}
function Timer() {
function now() { // try performance object, else use Date
return performance ? performance.now() : new Date().getTime();
}
var start = now();
this.spent = function () { return Math.round(now() - start); }
}
// I/O
var button = document.querySelector('button');
var input = document.querySelector('input');
var output = document.querySelector('pre');
button.onclick = function () {
var str = input.value;
// Convert to number
var vampire = parseInt(str);
// Measure performance
var timer = new Timer();
// Input must be valid number
var result = vampire.toString(10) !== str ? null
: vampireFangs(vampire);
output.textContent = (result
? 'Vampire number. Fangs are: ' + result.join(', ')
: result === null
? 'Input is not an integer or too large for JavaScript'
: 'Not a vampire number')
+ '\nTime spent: ' + timer.spent() + 'ms';
}
// Tests (numbers taken from wiki page)
var tests = [
// Negative test cases:
[1, 999, 126000, 1023],
// Positive test cases:
[1260, 1395, 1435, 1530, 1827, 2187, 6880,
102510, 104260, 105210, 105264, 105750, 108135,
110758, 115672, 116725, 117067, 118440,
120600, 123354, 124483, 125248, 125433, 125460, 125500,
13078260,
16758243290880,
24959017348650]
];
tests.forEach(function (vampires, shouldBeVampire) {
vampires.forEach(function (vampire) {
var isVampire = vampireFangs(vampire);
if (!isVampire !== !shouldBeVampire) {
output.textContent = 'Unexpected: vampireFangs('
+ vampire + ') returns ' + JSON.stringify(isVampire);
throw 'Test failed';
}
});
});
output.textContent = 'All tests passed.';
N: <input value="1047527295416280"><button>Vampire Check</button>
<pre></pre>
由于 JavaScript 使用 64 位浮点表示，上面的代码片段只接受最多 253-1 的数字。超过该限制会导致精度下降，从而导致结果不可靠。
由于Python没有这样的限制，我也在eval.in上放了一个Python实现。该站点对执行时间有限制，因此如果这成为问题，您必须 运行 在其他地方执行。
这里定义了一个吸血鬼号https://en.wikipedia.org/wiki/Vampire_number。数字 V 是吸血鬼数字，如果：
- 它可以表示为 X*Y 使得 X 和 Y 各有 N/2 位，其中 N 是 V 中的位数
- X 和 Y 都不应有尾随零
- X & Y 一起应该和 V 有相同的数字
我想出了一个解决办法，
strV = sort(toString(V))
for factor <- pow(10, N/2) to sqrt(V)
if factor divides V
X <- factor
Y <- V/factor
if X and Y have trailing zeros
continue
checkStr = sort(toString(X) + toString(Y))
if checkStr equals strV return true
另一种可能的解决方案是将V代表的字符串排列并分成两半，然后检查它是否是吸血鬼数字。哪种方法最好？
这里有一些建议：
首先是一个简单的改进：如果位数<4或奇数return false（或者如果v也是负数）。
不需要排序
v，统计每个数字出现多少次O(n)即可。您不必检查每个数字，只需检查数字可能的组合。这可以通过回溯来完成，并显着减少必须检查的数字量。
检查是否所有数字都被使用的最后排序也不需要，只需将两个数字的使用数字相加并与
v.[=15 中出现的次数进行比较=]
这里是类 JS 语言的代码，整数永不溢出，V 参数是一个不带前导 0 的整数字符串：
编辑： 事实证明，代码不仅是 JS-like，而且是有效的 JS 代码，并且没有问题确定 1047527295416280 确实是一个吸血鬼号码 (jsfiddle)。
var V, v, isVmp, digits, len;
function isVampire(numberString) {
V = numberString;
if (V.length < 4 || V.length % 2 == 1 )
return false;
v = parseInt(V);
if (v < 0)
return false;
digits = countDigits(V);
len = V.length / 2;
isVmp = false;
checkNumbers();
return isVmp;
}
function countDigits(s) {
var offset = "0".charCodeAt(0);
var ret = [0,0,0,0,0,0,0,0,0,0];
for (var i = 0; i < s.length; i++)
ret[s.charCodeAt(i) - offset]++;
return ret;
}
function checkNumbers(number, depth) {
if (isVmp)
return;
if (typeof number == 'undefined') {
for (var i = 1; i < 10; i++) {
if (digits[i] > 0) {
digits[i]--;
checkNumbers(i, len - 1);
digits[i]++;
}
}
} else if (depth == 0) {
if (v % number == 0) {
var b = v / number;
if (number % 10 != 0 || b % 10 != 0) {
var d = countDigits('' + b);
if (d[0] == digits[0] && d[1] == digits[1] && d[2] == digits[2] &&
d[3] == digits[3] && d[4] == digits[4] && d[5] == digits[5] &&
d[6] == digits[6] && d[7] == digits[7] && d[8] == digits[8] &&
d[9] == digits[9])
isVmp = true;
}
}
} else {
for (var i = 0; i < 10; i++) {
if (digits[i] > 0) {
digits[i]--;
checkNumbers(number * 10 + i, depth - 1);
digits[i]++;
}
}
}
}
在伪代码中：
if digitcount is odd return false
if digitcount is 2 return false
for A = each permutation of length digitcount/2 selected from all the digits,
for B = each permutation of the remaining digits,
if either A or B starts with a zero, continue
if both A and B end in a zero, continue
if A*B == the number, return true
此处仍有许多优化可以执行，主要是确保每对可能的因素只尝试一次。换句话说，如何在选择排列时最好地检查重复数字？
但这就是我要使用的算法的要点。
P.S.: 你不是在寻找素数，那么为什么要使用素数测试呢？你只关心这些是不是vampire数字；只有极少数可能的因素。无需检查所有数字直到 sqrt(number).
我在这里提出的算法不会遍历所有数字排列。它将尽可能快地消除可能性，以便实际上只测试一小部分排列。
通过示例解释算法
以下是基于示例编号 125460 的工作原理。如果您可以直接阅读代码，则可以跳过此（长）部分：
一开始两个毒牙（即吸血鬼因素）显然是不知道的，问题可以表示如下：
?**
X ?**
-------
=125460
对于第一个因素最左边的数字（标记为 ?），我们可以选择 0、1、2、5、4 或 6 中的任何一个数字。但仔细分析，0 不会是一种可行的可能性，因为产品永远不会超过 5 位数字。因此，遍历所有以零开头的数字排列是浪费时间。
对于第二个因数最左边的数位（也标有?），同理。但是，在查看组合时，我们可以再次过滤掉一些无法帮助实现目标产品的对。例如，这个组合应该被丢弃：
1**
X 2**
-------
=125460
用这些数字可以得到的最大数字是 199x299 = 59501（忽略我们连 9 都没有的事实），这甚至不到所需数字的一半。所以我们应该拒绝组合 (1, 2)。出于同样的原因，可以丢弃对 (1, 5) 以占据这些位置。类似地，对 (4, 5)、(4, 6) 和 (5, 6) 也可以被拒绝，因为它们产生的产品太大 (>= 200000)。我将这种类型称为测试——确定目标号码是否在某个选定数字对 "range test".
的范围内在这个阶段，第一颗和第二颗尖牙之间没有区别，所以我们也不必研究第二个数字小于第一个的一对，因为它们反映了一对已经被研究过的（或拒绝）。
所以在所有可能占据第一个位置的对中（有 30 种可能性从一组 6 位数字中取出 2 位数字），只需要研究以下 4 位：
(1, 6), (2, 4), (2, 5), (2, 6)
在更详细的表示法中，这意味着我们将搜索限制在这些数字模式中：
1** 2** 2** 2**
X 6** X 4** X 5** X 6**
------- ------- ------- -------
=125460 =125460 =125460 =125460
A B C D
很明显，这种在查看其他位置之前就减少了可能性大大减少了搜索树。
该算法将按顺序考虑这 4 种可能性中的每一种，并针对每种可能性检查下一个数字位置的可能性。所以先分析配置A：
1?*
X 6?*
-------
=125460
可用于 ? 标记位置的对是这 12 个：
(0, 2), (0, 4), (0, 5)
(2, 0), (2, 4), (2, 5)
(4, 0), (4, 2), (4, 5)
(5, 0), (5, 2), (5, 4)
同样，我们可以通过应用范围测试来消除对。让我们以一对 (5, 4) 为例。这意味着我们有因子 15* 和 64*（此时 * 是未知数字）。这两者的乘积将最大化为 159 * 649，即 103191（再次忽略我们甚至没有 9 可用的事实）：这对于达到目标来说太低了，因此可以忽略这一对。通过进一步应用范围测试，可以丢弃所有这12对，因此配置A内的搜索到此为止：那里没有解决方案。
然后算法移动到配置 B:
2?*
X 4?*
-------
=125460
再次，范围测试应用于第二个位置的可能对，结果再次证明这些对中的 none 通过了测试：例如 (5, 6) 永远不能代表更大的产品比 259 * 469 = 121471，这（只是）太小了。
然后算法移动到选项 C:
2?*
X 5?*
-------
=125460
在所有 12 个可能的对中，只有以下对可以通过范围测试：(4, 0), (4, 1), (6, 0), (6, 1)。所以现在我们有如下二级配置：
24* 24* 26* 26*
X 50* X 51* X 50* X 51*
------- ------- ------- -------
=125460 =125460 =125460 =125460
Ca Cb Cc Cd
在配置Ca中，没有一对通过范围测试。
在配置 Cb 中，对 (6, 0) 通过，并导致解决方案：
246
X 510
-------
=125460
此时算法停止搜索。结果很明显。与蛮力排列检查算法相比，所查看的配置总数非常少。这是搜索树的可视化：
*-+-- (1, 6)
|
+-- (2, 4)
|
+-- (2, 5) -+-- (4, 0)
| |
| +-- (4, 1) ---- (6, 0) = success: 246 * 510
/ /
| +-- (6, 0)
| |
| +-- (6, 1)
|
+-- (2, 6) ---- (0, 1) ---- (4, 5) = success: 204 * 615
下面的变体 / 仅用于显示算法在未找到解决方案的情况下还能做什么。但在这个实际案例中，搜索树的那部分实际上从未被跟踪过。
我不清楚时间复杂度，但似乎 运行 对于较大的数字相当好，表明在早期阶段消除数字会使搜索树的宽度非常窄。
这是一个实时 JavaScript 实现，它在激活时也会 运行 一些测试用例（并且它还有一些其他优化 -- 请参阅代码注释）。
/*
Function: vampireFangs
Arguments:
vampire: number to factorise into two fangs, if possible.
Return value:
Array with two fangs if indeed the argument is a vampire number.
Otherwise false (not a vampire number) or null (argument too large to
compute)
*/
function vampireFangs(vampire) {
/* Function recurse: for the recursive part of the algorithm.
prevA, prevB: partial, potential fangs based on left-most digits of the given
number
counts: array of ten numbers representing the occurrence of still
available digits
divider: power of 100, is divided by 100 each next level in the search tree.
Determines the number of right-most digits of the given number that
are ignored at first in the algorithm. They will be considered in
deeper levels of recursion.
*/
function recurse(vampire, prevA, prevB, counts, divider) {
if (divider < 1) { // end of recursion
// Product of fangs must equal original number and fangs must not both
// end with a 0.
return prevA * prevB === vampire && (prevA % 10 + prevB % 10 > 0)
? [prevA, prevB] // Solution found
: false; // It's not a solution
}
// Get left-most digits (multiple of 2) of potential vampire number
var v = Math.floor(vampire/divider);
// Shift decimal digits of partial fangs to the left to make room for
// the next digits
prevA *= 10;
prevB *= 10;
// Calculate the min/max A digit that can potentially contribute to a
// solution
var minDigA = Math.floor(v / (prevB + 10)) - prevA;
var maxDigA = prevB ? Math.floor((v + 1) / prevB) - prevA : 9;
if (maxDigA > 9) maxDigA = 9;
for (var digA = minDigA; digA <= maxDigA; digA++) {
if (!counts[digA]) continue; // this digit is not available
var fangA = prevA + digA;
counts[digA]--;
// Calculate the min/max B digit that can potentially contribute to
// a solution
var minDigB = Math.floor(v / (fangA + 1)) - prevB;
var maxDigB = fangA ? (v + 1) / fangA - prevB : 9;
// Don't search mirrored A-B digits when both fangs are equal until now.
if (prevA === prevB && digA > minDigB) minDigB = digA;
if (maxDigB > 9) maxDigB = 9;
for (var digB = minDigB; digB <= Math.min(maxDigB, 9); digB++) {
if (!counts[digB]) continue; // this digit is not available
var fangB = prevB + digB;
counts[digB]--;
// Recurse by considering the next two digits of the potential
// vampire number, for finding the next digits to append to
// both partial fangs.
var result = recurse(vampire, fangA, fangB, counts, divider / 100);
// When one solution is found: stop searching & exit search tree.
if (result) return result; // solution found
// Restore counts
counts[digB]++;
}
counts[digA]++;
}
}
// Validate argument
if (typeof vampire !== 'number') return false;
if (vampire < 0 || vampire % 1 !== 0) return false; // not positive and integer
if (vampire > 9007199254740991) return null; // beyond JavaScript precision
var digits = vampire.toString(10).split('').map(Number);
// A vampire number has an even number of digits
if (!digits.length || digits.length % 2 > 0) return false;
// Register per digit (0..9) the frequency of that digit in the argument
var counts = [0,0,0,0,0,0,0,0,0,0];
for (var i = 0; i < digits.length; i++) {
counts[digits[i]]++;
}
return recurse(vampire, 0, 0, counts, Math.pow(10, digits.length - 2));
}
function Timer() {
function now() { // try performance object, else use Date
return performance ? performance.now() : new Date().getTime();
}
var start = now();
this.spent = function () { return Math.round(now() - start); }
}
// I/O
var button = document.querySelector('button');
var input = document.querySelector('input');
var output = document.querySelector('pre');
button.onclick = function () {
var str = input.value;
// Convert to number
var vampire = parseInt(str);
// Measure performance
var timer = new Timer();
// Input must be valid number
var result = vampire.toString(10) !== str ? null
: vampireFangs(vampire);
output.textContent = (result
? 'Vampire number. Fangs are: ' + result.join(', ')
: result === null
? 'Input is not an integer or too large for JavaScript'
: 'Not a vampire number')
+ '\nTime spent: ' + timer.spent() + 'ms';
}
// Tests (numbers taken from wiki page)
var tests = [
// Negative test cases:
[1, 999, 126000, 1023],
// Positive test cases:
[1260, 1395, 1435, 1530, 1827, 2187, 6880,
102510, 104260, 105210, 105264, 105750, 108135,
110758, 115672, 116725, 117067, 118440,
120600, 123354, 124483, 125248, 125433, 125460, 125500,
13078260,
16758243290880,
24959017348650]
];
tests.forEach(function (vampires, shouldBeVampire) {
vampires.forEach(function (vampire) {
var isVampire = vampireFangs(vampire);
if (!isVampire !== !shouldBeVampire) {
output.textContent = 'Unexpected: vampireFangs('
+ vampire + ') returns ' + JSON.stringify(isVampire);
throw 'Test failed';
}
});
});
output.textContent = 'All tests passed.';
N: <input value="1047527295416280"><button>Vampire Check</button>
<pre></pre>
由于 JavaScript 使用 64 位浮点表示，上面的代码片段只接受最多 253-1 的数字。超过该限制会导致精度下降，从而导致结果不可靠。
由于Python没有这样的限制，我也在eval.in上放了一个Python实现。该站点对执行时间有限制，因此如果这成为问题，您必须 运行 在其他地方执行。