find所有的4位数的吸血鬼号码
我正在解决一个问题，找出所有的4位数的吸血鬼号码。
吸血鬼号码 v = x * y被定义为一个具有“n”偶数个数字的数字，通过乘以一对“n / 2”数字数字（其中数字是从原始数字以任何顺序获得的）x和y在一起。 如果v是一个吸血鬼号码，那么x＆y就称为它的“牙齿”。
吸血鬼数字的例子是：
1. 1260=21*60 2. 1395=15*93 3. 1530=30*51 我已经尝试过蛮力algorithm来合并给定数字的不同数字并将它们相乘。 但是这种方法效率很低，花费了很多时间。
有没有一个更有效的algorithm解决这个问题？
或者，您可以使用此页面上描述的吸血鬼编号属性（从维基百科链接）：
Pete Hartley发现了一个重要的理论结果：
If x·y is a vampire number then x·y == x+y (mod 9)certificate：设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）mod9 = d（x·y）mod9 =（d（x）+ d（y））mod9 =（d（x）mod9 + d（y）mod9） mod 9 =（x mod 9 + y mod 9）mod 9 =（x + y）mod 9
在（（0,0），（2,2），（3,6），（5,8），（6,3），（8,8）中的同余的解是（x mod 9，y mod 9） 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
因为它们是{(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100} {(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100} ，只有4*40 = 160迭代，当一个蛮力给你104迭代。 如果考虑到>= 1000约束，则可以执行更less的操作，例如，如果j < 1000/i则可以避免检查。
现在你可以很容易地扩大发现超过4位数的吸血鬼=）
迭代所有可能的牙齿（100×100 = 10000个可能性），并且发现它们的产品是否与牙齿具有相同的数字。
又一个蛮力（C）版本，有一个免费的冒泡sorting来引导…
#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; }
运行几乎瞬间。 variables名称不太具有描述性，但应该很明显
基本思想是从两个潜在的牙齿开始，把它们分解成数字，并对数字进行sorting以便于比较。 然后我们对产品也做同样的事情 – 把它分解成数字和sorting。 然后我们从sorting的数字重新构成两个整数，如果它们相等，我们有一个匹配。
可能的改进：1）以1000 / i开始j而不是i以避免if (p < 1000) ... ，2）可能使用插入sorting而不是冒泡sorting（但是谁会注意到这2个额外的掉期？） ，3）使用真正的swap()实现，4）直接比较数组，而不是从它们中构build一个合成整数。 不知道那些会有任何可衡量的差异，除非你运行在一个Commodore 64或什么东西…
编辑：出于好奇，我把这个版本，并推广了一些工作的4,6和8位数的情况下 – 没有任何大的优化，它可以find所有的8位吸血鬼数字在<10秒.. 。
这是一个丑陋的黑客（蛮力，排列手动检查，不安全的缓冲区操作，产生愚蠢等），但它的工作。 你的新练习是改进它：P
维基百科声称有7个吸血鬼数字是4位长。 完整的代码已经find了他们所有的 ，甚至一些重复。
编辑： 这是一个稍微好一点的比较器function。
编辑2： 这是一个C ++版本 ，它使用一个std::map （并且存储特定吸血鬼号码的最后一次出现以及它的因子）来统一结果（因此避免了重复）。 它也符合至less其中一个因素不应以0结尾的标准，即如果两个被乘数是可以被当前整除的，那么数字不是吸血鬼号码。 这个testing寻找6位数的吸血鬼编号，根据维基百科的说法，它确实find了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; }
我不会用暴力手段轻易放弃。 你有不同的数字，你必须通过1000到9999。 我会把这个集合分成若干个子集，然后把线程起来处理每个子集。
你可以进一步划分每个数字的各种组合的工作; IIRC我的离散math，你有4 * 3 * 2或24组合每个数字来尝试。
生产者/消费者的方法可能是值得的。
迭代似乎对我来说很好，因为你只需要做一次这个查找所有的值，然后你可以caching它们。 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]
编辑：完全蛮力，淘汰相同的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; } }
C＃中使用LINQ的蛮力版本：
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); } } }
类似于上面提到的，我的方法是首先find一个数字的所有排列，然后将它们分成两个两位数字，并testing它们的乘积是否等于原始数字。
上面的另一个有趣的讨论是一个数字可以有多less排列。 这里是我的看法：（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 } } }
我会尝试的方法是循环遍历[1000，9999]中的每个数字，并testing其数字的任何排列（中间分割）是否相乘。
这将需要（9999 – 1000）* 24 = 215,976testing，这应该执行现代机器上可接受的快速。
我肯定会分开存储数字，所以你可以避免做一些分割从一个整数提取数字。
如果你编写你的代码，以至于你只做整数加法和乘法运算（也许偶尔需要进行分割），那应该是相当快的。 你可以通过跳过两个数字对来进一步提高速度，“明显”不会起作用 – 例如前导零（请注意，最大的产品可以由一位数字和两位数字产生的是9 * 99或891）。
另外请注意，这种方法是不平行的（ http://en.wikipedia.org/wiki/Embarrassingly_parallel ），所以如果你真的需要加速，那么你应该考虑在不同的线程中testing数字。
<?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位数字加上一些重复。 您可以进一步处理数据并删除重复项。
在我看来，如果不依靠任何特别抽象的见解来进行尽可能less的testing，那么您可能想要重复一遍f牙，剔除任何明显无意义的候选人。
例如，因为x*y == y*x大概只有一半的search空间可以通过评估y > x情况来消除。 如果最大的两位数的方阵是99，那么最小的四位数字是11，所以不要低于11。
编辑：
好吧，把我想到的所有东西都扔进混合体（尽pipe看上去与领先的解决scheme无关）。
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); } }
和testing，因为我没有看到任何人使用直方图，但：
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是吸血鬼
我是编程新手……但是在find所有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（）块中的布尔expression式
我已经编辑了一下Owlstead的algorithm，使它对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; }
}
这个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)
