这里定义了“吸血鬼数” https://en.wikipedia.org/wiki/Vampire_number。一个数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表示的字符串进行排列，将其分成两半并检查它是否是吸血鬼数字。哪种方法是最好的？
?**
X ?**
-------
=125460
?标记），我们可以选择数字0、1、2、5、4或6中的任意一个。但仔细分析后，0不是可行的可能性，因为乘积永远不会超过5位数。因此，浪费时间去遍历以0开头的所有数字排列。?标记），情况也是如此。但是，在查看组合时，我们可以再次筛选出一些无法达到目标乘积的数字对。例如，应该丢弃这个组合： 1**
X 2**
-------
=125460
(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
再次，对于第二位可能的数字对进行取值范围测试，同样发现没有任何数字对通过测试：例如 (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
/后的变量仅用于显示算法在没有找到解决方案时会执行的操作。但在实际情况中，搜索树的这部分实际上从未被追随。/*
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 实现。该网站对执行时间有限制，如果出现问题，您需要在其他地方运行它。
伪代码如下：
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
首先，一个简单的改进：如果数字位数小于4或为奇数，则返回false（或者如果v也为负数）。
不需要对v进行排序，只需计算每个数字出现的次数O（n）即可。
您不必检查每个数字，只需检查可能与数字配对的组合。这可以通过回溯来完成，并显着减少了需要检查的数字数量。
最终的排序以检查是否使用了所有数字也是不必要的，只需将两个数字的使用数字相加并与v中的出现次数进行比较即可。
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]++;
}
}
}
}