代码之家 › 专栏 › 技术社区 › Skadoosh

在Java中为自由范围生成吸血鬼号码(适用于大范围)

elixir numbers parallel-processing algorithm java

Skadoosh · 技术社区 · 6 年前

吸血鬼数是具有偶数位数的自然数,可以分解为两个整数。这两个因素被称为毒牙,必须具有以下特性:

它们各自包含原始数字位数的一半它们一起由与原始数字完全相同的数字组成其中最多有一个尾随零

吸血鬼号码及其毒牙示例:1260:(21,60)

这是一个简单的代码,可以生成4位数的吸血鬼数字。如何修改此选项以高效地为大数(100000)生成吸血鬼数

import java.util.Arrays;


public class Vampire
{
    final static int START = 11, END = 1000;
    public static void main(String[] args)
    {
        char[] kChar, checkChar;
        String kStr, checkStr;
        int k;
        for(int i=START; i<END; i++) {
                for(int i1=i; i1<100; i1++) {

                    k = i * i1;

                    kStr = Integer.toString(k);
                    checkStr = Integer.toString(i) + Integer.toString(i1);



                    kChar = kStr.toCharArray();
                    checkChar = checkStr.toCharArray();

                    Arrays.sort(kChar);
                    Arrays.sort(checkChar);

                    if(Arrays.equals(kChar, checkChar) ) {
                        System.out.println(i + " * " + i1 + " = " + k);
                    }
                }
            }
    }
}

0 回复 | 直到 6 年前

second 6 年前

我想出了这个,基本上和你的方法一样, 只是针对稍微“更大”的范围进行了调整。

在我的电脑上,完全扫描8位数范围内的所有吸血鬼数字只需不到1秒,而扫描10位数范围内的吸血鬼数字大约需要80秒。除此之外的任何事情都需要一段时间。。。

我还添加了消除两个尾随零的尖牙,这在你的定义中没有提到。

import java.util.Arrays;

public class Vampire {

    final static int START = 10, END = 10000;

    public static void main(String[] args) {

        for (int fangA = START; fangA < END; fangA++) {

            String sFangA = String.valueOf(fangA);
            boolean trailingZeros = sFangA.endsWith("0");           
            int max = (int) Math.min(END, Math.pow(10, sFangA.length()));

            for (long fangB = fangA; fangB < max; fangB++) {

                long candidate = fangA * fangB;
                if (candidate % 9 == (fangA + fangB) % 9) {  

                    String sCandidate = String.valueOf(candidate);
                    String sFangB = String.valueOf(fangB);

                    if ((trailingZeros && sFangB.endsWith("0")) == false) {

                        char[] cVampire = sCandidate.toCharArray();
                        Arrays.sort(cVampire);

                        char[] cFangs = (sFangA + sFangB).toCharArray();
                        Arrays.sort(cFangs);

                        if (Arrays.equals(cVampire, cFangs)) {
                            System.out.println(sFangA + " * " + sFangB + " = " + sCandidate);
                        }
                    }
                }
            }
        }
    }
}

你也可以检查一下 page .它包含一个优化的 c 程序和它所基于的算法的描述。

但计算所有14位吸血鬼数字仍然需要大约19个小时(早在2002年,在一台像样的pc上,现在可能会快一点)。

我注意到 (fangA + fangB) % 9 似乎总是0或4。我认为这与我们的假设有关 Pete Hartley ,但我真的无法解释。

使用这些知识可以优化内部循环,并跳过9个可能值中的7个。10位数字的结果是相同的(我没有进一步测试),时间改善约为15%(约68秒)。

[81页提到如何应用,但我还没有弄清楚]

编辑:

START 和 END 描述每个毒牙的搜索范围(而不是吸血鬼号码)。如果你只想得到一个特定范围的吸血鬼数字,那么将其应用到你得到的结果中。除非你有一个有效的方法来生成 vampire number 这种方法似乎要快得多。

Math.pow(10, sFangA.length()) 用于将内部循环中的搜索限制为与fangA具有相同位数的fangB。

我添加了 Math.min 以确保方布的射程也在 开始 和 终止 (在此之前,方B的范围始终是方A的完整数字范围)。