我正在解决一个问题，找出所有 4 位数的吸血鬼数字。
吸血鬼数v =x*y 定义为具有“n”个偶数位数的数字，由一对“n/2”位数字相乘形成（其中数字以任意顺序从原始数字中取出）x和 y 在一起。如果 v 是一个吸血鬼数，那么 x&y 和被称为它的“毒牙”。
吸血鬼数字的例子是：
1. 1260=21*60
2. 1395=15*93
3. 1530=30*51
我尝试了蛮力算法来组合给定数字的不同数字并将它们相乘。但这种方法效率极低，而且占用大量时间。
有没有更有效的算法解决这个问题？
或者您可以使用此页面上描述的吸血鬼数字的属性（从 Wikipedia 链接）：
Pete Hartley 发现的一个重要理论结果：
If x·y is a vampire number then x·y == x+y (mod 9)证明：设 mod 为二进制模运算符，d(x) 为 x 的十进制数字之和。众所周知，对于所有 x，d(x) mod 9 = x mod 9。假设 x·y 是吸血鬼。然后它包含与 x 和 y 相同的数字，特别是 d(x·y) = d(x)+d(y)。这导致： (x·y) mod 9 = d(x·y) mod 9 = (d(x)+d(y)) mod 9 = (d(x) mod 9 + d(y) mod 9) mod 9 = (x mod 9 + y mod 9) mod 9 = (x+y) mod 9
同余的解是 (x mod 9, y mod 9) in {(0,0), (2,2), (3,6), (5,8), (6,3), (8, 5)}
所以你的代码可能看起来像这样：
for(int i=18; i<100; i=i+9){ // 18 is the first multiple of 9 greater than 10
for(int j=i; j<100; j=j+9){ // Start at i because as @sh1 said it's useless to check both x*y and y*x
checkVampire(i,j);
}
}
for(int i=11; i<100; i=i+9){ // 11 is the first number greater than 10 which is = 2 mod 9
for(int j=i; j<100; j=j+9){
checkVampire(i,j);
}
}
for(int i=12; i<100; i=i+9){
for(int j=i+3; j<100; j=j+9){
checkVampire(i,j);
}
}
for(int i=14; i<100; i=i+9){
for(int j=i+3; j<100; j=j+9){
checkVampire(i,j);
}
}
// We don't do the last 2 loops, again for symmetry reasons
由于它们是每个集合中的 40 个元素，例如{(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100}，因此您只进行4*40 = 160迭代，当蛮力为您提供 10^4 次迭代时。如果考虑到>= 1000约束，您可以执行更少的操作，例如，您可以避免检查 if j < 1000/i。
现在您可以轻松放大以找到超过 4 位数的吸血鬼 =)
遍历所有可能的尖牙（100 x 100 = 10000 种可能性），并找出它们的乘积是否与尖牙具有相同的数字。
另一个蛮力（C）版本，带有免费的冒泡排序启动......
#include <stdio.h>
static inline void bubsort(int *p)
{ while (1)
{ int s = 0;
for (int i = 0; i < 3; ++i)
if (p[i] > p[i + 1])
{ s = 1;
int t = p[i]; p[i] = p[i + 1]; p[i + 1] = t;
}
if (!s) break;
}
}
int main()
{ for (int i = 10; i < 100; ++i)
for (int j = i; j < 100; ++j)
{ int p = i * j;
if (p < 1000) continue;
int xd[4];
xd[0] = i % 10;
xd[1] = i / 10;
xd[2] = j % 10;
xd[3] = j / 10;
bubsort(xd);
int x = xd[0] + xd[1] * 10 + xd[2] * 100 + xd[3] * 1000;
int yd[4];
yd[0] = p % 10;
yd[1] = (p / 10) % 10;
yd[2] = (p / 100) % 10;
yd[3] = (p / 1000);
bubsort(yd);
int y = yd[0] + yd[1] * 10 + yd[2] * 100 + yd[3] * 1000;
if (x == y)
printf("%2d * %2d = %4d\n", i, j, p);
}
return 0;
}
几乎立即运行。变量名称不是太具有描述性，但应该很明显......
基本思想是从两个潜在的尖牙开始，将它们分解成数字，然后对数字进行排序以便于比较。然后我们对产品做同样的事情——把它分解成数字并排序。然后我们从排序后的数字重新构成两个整数，如果它们相等，我们就有一个匹配项。
可能的改进：1）开始j而1000 / i不是i避免必须做if (p < 1000) ...，2）可能使用插入排序而不是冒泡排序（但谁会注意到这两个额外的交换？），3）使用真正的swap()实现，4）直接比较数组而不是从它们中构建一个合成整数。但是，不确定其中任何一个都会产生任何可衡量的差异，除非您在 Commodore 64 或其他设备上运行它...
编辑：出于好奇，我采用了这个版本并对其进行了更多概括，以适用于 4、6 和 8 位数的情况——无需任何重大优化，它可以在 < 10 秒内找到所有 8 位数的吸血鬼数字。 .
这是一个丑陋的黑客（蛮力，手动检查排列，不安全的缓冲区操作，产生欺骗等），但它完成了工作。你的新练习是改进它：P
维基百科声称有 7 个 4 位数长的吸血鬼数字。完整的代码已经找到了它们，甚至有些重复。
编辑： 这是一个稍微好一点的比较器功能。
编辑 2： 这是一个 C++ 版本std::map，它使用一个（并将特定吸血鬼数字的最后一次出现及其因子存储在其中）来唯一结果（因此它避免重复）。它还满足至少一个因数不应以 结尾的标准0，即如果两个被乘数届时都可整除，则该数不是吸血鬼数。该测试查找 6 位数的吸血鬼数字，根据 Wikipedia 的说法，它确实找到了其中的 148 个。
原代码：
#include <stdio.h>
void getdigits(char buf[], int n)
{
while (n) {
*buf++ = n % 10;
n /= 10;
}
}
int is_vampire(const char n[4], const char i[2], const char j[2])
{
/* maybe a bit faster if unrolled manually */
if (i[0] == n[0]
&& i[1] == n[1]
&& j[0] == n[2]
&& j[1] == n[3])
return 1;
if (i[0] == n[1]
&& i[1] == n[0]
&& j[0] == n[2]
&& j[1] == n[3])
return 1;
if (i[0] == n[0]
&& i[1] == n[1]
&& j[0] == n[3]
&& j[1] == n[2])
return 1;
if (i[0] == n[1]
&& i[1] == n[0]
&& j[0] == n[3]
&& j[1] == n[2])
return 1;
// et cetera, the following 20 repetitions are redacted for clarity
// (this really should be a loop, shouldn't it?)
return 0;
}
int main()
{
for (int i = 10; i < 100; i++) {
for (int j = 10; j < 100; j++) {
int n = i * j;
if (n < 1000)
continue;
char ndigits[4];
getdigits(ndigits, n);
char idigits[2];
char jdigits[2];
getdigits(idigits, i);
getdigits(jdigits, j);
if (is_vampire(ndigits, idigits, jdigits))
printf("%d * %d = %d\n", i, j, n);
}
}
return 0;
}
带有 LINQ 的 C# 中的蛮力版本：
class VampireNumbers
{
static IEnumerable<int> numberToDigits(int number)
{
while(number > 0)
{
yield return number % 10;
number /= 10;
}
}
static bool isVampire(int first, int second, int result)
{
var resultDigits = numberToDigits(result).OrderBy(x => x);
var vampireDigits = numberToDigits(first)
.Concat(numberToDigits(second))
.OrderBy(x => x);
return resultDigits.SequenceEqual(vampireDigits);
}
static void Main(string[] args)
{
var vampires = from fang1 in Enumerable.Range(10, 89)
from fang2 in Enumerable.Range(10, 89)
where fang1 < fang2
&& isVampire(fang1, fang2, fang1 * fang2)
select new { fang1, fang2 };
foreach(var vampire in vampires)
{
Console.WriteLine(vampire.fang1 * vampire.fang2
+ " = "
+ vampire.fang1
+ " * "
+ vampire.fang2);
}
}
}
迭代对我来说似乎很好，因为您只需要执行一次即可找到所有值，然后您可以缓存它们。Python(3) 版本大约需要 1.5 秒：
# just some setup
from itertools import product, permutations
dtoi = lambda *digits: int(''.join(str(digit) for digit in digits))
gen = ((dtoi(*digits), digits) for digits in product(range(10), repeat=4) if digits[0] != 0)
l = []
for val, digits in gen:
for check1, check2 in ((dtoi(*order[:2]), dtoi(*order[2:])) for order in permutations(digits) if order[0] > 0 and order[2] > 0):
if check1 * check2 == val:
l.append(val)
break
print(l)
哪个会给你[1260, 1395, 1435, 1530, 1827, 2187, 6880]
I wouldn't have given up so easily on brute force. You have distinct set of numbers, 1000 to 9999 that you must run through. I would divide up the set into some number of subsets, and then spin up threads to handle each subset.
You could further divide the work be coming up with the various combinations of each number; IIRC my discrete math, you have 4*3*2 or 24 combinations for each number to try.
A producer / consumer approach might be worthwhile.
编辑：完全蛮力清除相同的 X 和 Y 值...
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Vampire {
public static void main(String[] args) {
for (int x = 10; x < 100; x++) {
String sx = String.valueOf(x);
for (int y = x; y < 100; y++) {
int v = x * y;
String sy = String.valueOf(y);
String sv = String.valueOf(v);
if (sortVampire(sx + sy).equals(sortVampire(sv))) {
System.out.printf("%d * %d = %d%n", x, y, v);
}
}
}
}
private static List<Character> sortVampire(String v) {
List<Character> vc = new ArrayList<Character>();
for (int j = 0; j < v.length(); j++) {
vc.add(v.charAt(j));
}
Collections.sort(vc);
return vc;
}
}
和上面说的类似，我的方法是先找出一个数的所有排列，然后将它们一分为二，形成两个两位数，并测试它们的乘积是否等于原数。
上面另一个有趣的讨论是一个数字可以有多少个排列。以下是我的观点：（1）一个四位数相同的数有1个排列；（2）一个只有两个不同数字的数字有6个排列（它是否包含零无关紧要，因为我们不在乎排列后它是否仍然是一个4位数字）；(3) 三个不同数字的数有 12 次排列；(4) 具有所有四个不同数字的数字有 24 种排列。
public class VampireNumber {
// method to find all permutations of a 4-digit number
public static void permuta(String x, String s, int v)
{for(int i = 0; i < s.length(); i++)
{permuta( x + s.charAt(i), s.substring(0,i) + s.substring(i+1), v);
if (s.length() == 1)
{x = x + s;
int leftpart = Integer.parseInt(x.substring(0,2));
int rightpart = Integer.parseInt(x.substring(2));
if (leftpart*rightpart == v)
{System.out.println("Vampir = " + v);
}
}
}
}
public static void main(String[] args){
for (int i = 1000; i < 10000; i++) {
permuta("", Integer.toString(i), i); //convert the integer to a string
}
}
}
在我看来，要在不依赖任何特别抽象的见解的情况下执行尽可能少的测试，您可能想要遍历尖牙并剔除任何明显毫无意义的候选人。
例如，由于x*y == y*x只评估y > x. 如果最大的两位数是 99，那么最小的可以组成一个四位数的数字是 11，所以不要从低于 11 开始。
编辑：
好的，把我想到的所有东西都混在一起（即使它与领先的解决方案相比看起来很傻）。
for (x = 11; x < 100; x++)
{
/* start y either at x, or if x is too small then 1000 / x */
for (y = (x * x < 1000 ? 1000 / x : x); y < 100; y++)
{
int p = x * y;
/* if sum of digits in product is != sum of digits in x+y, then skip */
if ((p - (x + y)) % 9 != 0)
continue;
if (is_vampire(p, x, y))
printf("%d\n", p);
}
}
和测试，因为我还没有看到任何人使用直方图，但是：
int is_vampire(int p, int x, int y)
{
int h[10] = { 0 };
int i;
for (i = 0; i < 4; i++)
{
h[p % 10]++;
p /= 10;
}
for (i = 0; i < 2; i++)
{
h[x % 10]--;
h[y % 10]--;
x /= 10;
y /= 10;
}
for (i = 0; i < 10; i++)
if (h[i] != 0)
return 0;
return 1;
}
1260 1395 1435 1530 1827 2187 6880是吸血鬼
我是编程新手......但是找到所有 4 位吸血鬼数字只有 12 种组合。我糟糕的答案是：
public class VampNo {
public static void main(String[] args) {
for(int i = 1000; i < 10000; i++) {
int a = i/1000;
int b = i/100%10;
int c = i/10%10;
int d = i%10;
if((a * 10 + b) * (c * 10 + d) == i || (b * 10 + a) * (d * 10 + c) == i ||
(a * 10 + d) * (b * 10 + c) == i || (d * 10 + a) * (c * 10 + b) == i ||
(a * 10 + c) * (b * 10 + d) == i || (c * 10 + a) * (d * 10 + b) == i ||
(a * 10 + b) * (d * 10 + c) == i || (b * 10 + a) * (c * 10 + d) == i ||
(b * 10 + c) * (d * 10 + a) == i || (c * 10 + b) * (a * 10 + d) == i ||
(a * 10 + c) * (d * 10 + b) == i || (c * 10 + a) * (b * 10 + d) == i)
System.out.println(i + " is vampire");
}
}
}
现在的主要任务是简化 If() 块中的布尔表达式
我会尝试的方法是遍历 [1000, 9999] 中的每个数字，并测试其数字的任何排列（在中间分割）是否相乘以形成它。
这将需要 (9999 - 1000) * 24 = 215,976 次测试，在现代机器上执行速度应该可以接受。
我肯定会单独存储数字，这样你就可以避免不得不做一些像一堆除法这样的事情来从一个整数中提取数字。
如果您编写代码时只进行整数加法和乘法运算（可能偶尔进行除法运算），那么它应该非常快。您可以通过跳过“显然”不起作用的两位数对来进一步提高速度 - 例如，带有前导零的那些（请注意，一位数和两位数可以产生的最大乘积是 9 * 99 或 891）。
另请注意，这种方法是令人尴尬的并行（http://en.wikipedia.org/wiki/Embarrassingly_parallel），所以如果你真的需要加快速度，那么你应该考虑在单独的线程中测试数字。
<?php
for ($i = 10; $i <= 99; $j++) {
// Extract digits
$digits = str_split($i);
// Loop through 2nd number
for ($j = 10; $j <= 99; $j++) {
// Extract digits
$j_digits = str_split($j);
$digits[2] = $j_digits[0];
$digits[3] = $j_digits[1];
$product = $i * $j;
$product_digits = str_split($product);
// check if fangs
$inc = 0;
while (in_array($digits[$inc], $product_digits)) {
// Remove digit from product table
/// So AAAA -> doesnt match ABCD
unset($product_digits[$array_serach($digits[$inc], $product_digits)]);
$inc++;
// If reached 4 -> vampire number
if ($inc == 4) {
$vampire[] = $product;
break;
}
}
}
}
// Print results
print_r($vampire);
?>
在 PHP 上花了不到一秒钟的时间。甚至无法告诉它必须运行 8100 次计算……计算机速度很快！
结果：
给你所有的 4 位数字加上一些重复。您可以进一步处理数据并删除重复项。
我对 Owlstead 的算法进行了一些编辑，以使其对 Java 初学者/学习者更容易理解。
import java.util.Arrays;
public class Vampire {
public static void main(String[] args) {
for (int x = 10; x < 100; x++) {
String sx = Integer.toString(x);
for (int y = x; y < 100; y++) {
int v = x * y;
String sy = Integer.toString(y);
String sv = Integer.toString(v);
if( Arrays.equals(sortVampire(sx + sy), sortVampire(sv)))
System.out.printf("%d * %d = %d%n", x, y, v);
}
}
}
private static char[] sortVampire (String v){
char[] sortedArray = v.toCharArray();
Arrays.sort(sortedArray);
return sortedArray;
}
}
这是我的代码。要生成僵尸号码，我们需要使用 Random 类 :)
import java.io.PrintStream;
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
class VampireNumbers {
static PrintStream p = System.out;
private static Set<Integer> findVampireNumber() {
Set<Integer> vampireSet = new HashSet<Integer>();
for (int y = 1000; y <= 9999; y++) {
char[] numbersSeparately = ("" + y).toCharArray();
int numberOfDigits = numbersSeparately.length;
for (int i = 0; i < numberOfDigits; i++) {
for (int j = 0; j < numberOfDigits; j++) {
if (i != j) {
int value1 = Integer.valueOf("" + numbersSeparately[i] + numbersSeparately[j]);
int ki = -1;
for (int k = 0; k < numberOfDigits; k++) {
if (k != i && k != j) {
ki = k;
}
}
int kj = -1;
for (int t = 0; t < numberOfDigits; t++) {
if (t != i && t != j && t != ki) {
kj = t;
}
}
int value21 = Integer.valueOf("" + numbersSeparately[ki] + numbersSeparately[kj]);
int value22 = Integer.valueOf("" + numbersSeparately[kj] + numbersSeparately[ki]);
if (value1 * value21 == y && !(numbersSeparately[j] == 0 && numbersSeparately[kj] == 0)
|| value1 * value22 == y
&& !(numbersSeparately[j] == 0 && numbersSeparately[ki] == 0)) {
vampireSet.add(y);
}
}
}
}
}
return vampireSet;
}
public static void main(String[] args) {
Set<Integer> vampireSet = findVampireNumber();
Iterator<Integer> i = vampireSet.iterator();
int number = 1;
while (i.hasNext()) {
p.println(number + ": " + i.next());
number++;
}
}
}
此 python 代码运行速度非常快 (O(n2))
result = []
for i in range(10,100):
for j in range(10, 100):
list1 = []
list2 = []
k = i * j
if k < 1000 or k > 10000:
continue
else:
for item in str(i):
list1.append(item)
for item in str(j):
list1.append(item)
for item in str(k):
list2.append(item)
flag = 1
for each in list1:
if each not in list2:
flag = 0
else:
list2.remove(each)
for each in list2:
if each not in list1:
flag = 0
if flag == 1:
if k not in result:
result.append(k)
for each in result:
print(each)