3

我正在尝试拆分一个大整数的数字。让我更具体一点。我正在使用斐波那契数列生成一个大整数，现在使用这个算法我需要循环，直到找到一个 BigInteger，其中前 9 位数字和后 9 位数字都是泛数字。唯一的问题是我必须循环的数量是 300K（现在 BigInteger 将变得如此巨大）。

我尝试将 BigInteger 转换为字符串，然后使用“substring(begin, end)”。但是，这太慢了，仅仅做 10 万个索引就花了将近 28 分钟。

对此有一个数学解决方案，但我不完全确定它是什么，如果有人能引导我朝着正确的方向前进，我将不胜感激。注意：我不是直接要求答案，只是朝着找到正确答案迈出一步。

这是我的代码，以防您想知道：

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(300_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n)
    {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);        
        for (int i = 0; i < n; i++)
        {
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    static BigInteger[] pows = new BigInteger[16];

    static {
        for (int i = 0; i < 16; i++) {
            pows[i] = BigInteger.TEN.pow(i);
        }
    }

    static boolean isPanDigital(BigInteger n) {
         if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
           return false;
        }
        boolean[] foundDigits = new boolean[9];


        boolean isPanDigital = true;
        for (int i = 1; i <= 9; i++) {
            BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
            for (int j = 0; j < foundDigits.length; j++) {
                if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
                    foundDigits[j] = true;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            isPanDigital = isPanDigital && foundDigits[i];
        }

        return isPanDigital;
    }
}

更新，设法弄清楚如何生成前 9 位数字（而且它似乎并不太慢）。但是，我在生成最后 9 位数字时遇到问题。

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(300_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n)
    {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);        
        for (int i = 0; i < n; i++)
        {
            if (prev1.toString().length() > 19)
            {
                String leading9Digits = leading9Digits(prev1);
                if (isPanDigital(BigInteger.valueOf(Integer.valueOf(leading9Digits))))
                {
                    System.out.println("Solved at index: " + i);
                    break;
                }
            }
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    public static String leading9Digits(BigInteger x) {
        int log10 = (x.bitLength() - 1) * 3 / 10;
        x = x.divide(BigInteger.TEN.pow(Math.max(log10 + 1 - 9, 0)));
        return x.toString().substring(0, 9);
    }

    static BigInteger[] pows = new BigInteger[16];

    static {
        for (int i = 0; i < 16; i++) {
            pows[i] = BigInteger.TEN.pow(i);
        }
    }

    static boolean isPanDigital(BigInteger n) {
         if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
           return false;
        }
        boolean[] foundDigits = new boolean[9];


        boolean isPanDigital = true;
        for (int i = 1; i <= 9; i++) {
            BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
            for (int j = 0; j < foundDigits.length; j++) {
                if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
                    foundDigits[j] = true;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            isPanDigital = isPanDigital && foundDigits[i];
        }

        return isPanDigital;
    }
}
4

1 回答 1

1

好的，我对您的代码进行了一些优化。

  • 你的leading9Digits方法不应该返回 a String，它应该返回一个数字。如果他们愿意，允许代码的其他部分将其转换为字符串。
  • BigInteger.pow()每次代码循环调用都是浪费。您可以预先计算所有这些 10 的幂并将它们存储在一个数组中。
  • 您不必使用内部循环来检查泛数字性。如果您必须将boolean数组中的一个单元格增加两次，那么它就不是泛数字的。此外，您可以提前退出0.
  • 使用mod 1000000000计算trailing9digits很容易
  • 您可以预先创建常量并存储它们，而不是每次都创建它们。您的方式适用于基元，但不适用于对象。

请注意，我尝试使用 aString而不是余数，它们的结果大致相同。我将两者都包含在您的代码中。

而且，最后，正确的答案不在前 300,000 个；大约是329,000。在我的机器上运行大约需要 29 秒。

import java.math.BigInteger;

public class Main {
    private static final BigInteger NINE = BigInteger.valueOf(9);
    private static final BigInteger BILLION = BigInteger.valueOf(1000000000);
    private static final double log10_2 = Math.log10(2);
    private static final double CORRECTION = 9d;
    private static final int ARRAY_SIZE = 131072;

    static BigInteger[] pows = new BigInteger[ARRAY_SIZE];

    static {
        pows[0] = BigInteger.ONE;
        for (int i = 1; i < ARRAY_SIZE; i++) {
            pows[i] = pows[i - 1].multiply(BigInteger.TEN);
        }
    }

    public static void main(String... strings) {
        long timeStart = System.currentTimeMillis();
        fib(500_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: "
                + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n) {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);
        for (int i = 0; i < n; i++) {
            if (prev1.bitLength() > 30) {
                if (isDualPanDigital(prev1)) {
                    System.out.println("Solved at index: " + i);
                    break;
                }
            }
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    public static BigInteger leading9Digits(BigInteger x) {
        int dividePower = (int) (x.bitLength() * log10_2 - CORRECTION);
        BigInteger y = x.divide(pows[dividePower]);
        if (y.compareTo(BILLION) != -1) y = y.divide(BigInteger.TEN);
        return y;
    }

    public static BigInteger trailing9Digits(BigInteger x) {
        return x.mod(BILLION);
    }

    static boolean isDualPanDigital(BigInteger n) {
        boolean leading = isPanDigital(leading9Digits(n));
        boolean trailing = isPanDigital(trailing9Digits(n));

        if (leading && trailing) {
            System.out.format("leadingDigits: %s, trailingDigits: %s%n",
                    leading9Digits(n), trailing9Digits(n));
        }
        return leading && trailing;
    }

    static boolean isPanDigital(BigInteger n) {
        if (!n.remainder(NINE).equals(BigInteger.ZERO)) {
            return false;
        }

        return isPanDigitalString(n);
    }

    private static boolean isPanDigitalMath(BigInteger n) {
        boolean[] foundDigits = new boolean[10];

        for (int i = 1; i <= 9; i++) {
            int digit = n.remainder(pows[i]).divide(pows[i - 1]).intValue();
            if (digit == 0)
                return false;
            if (foundDigits[digit - 1])
                return false;
            else
                foundDigits[digit - 1] = true;
        }

        return true;
    }

    private static boolean isPanDigitalString(BigInteger n) {
        boolean[] foundDigits = new boolean[9];

        String s = n.toString();
        if (s.length() < 9) {
            return false;
        }

        for (int i = 0; i < 9; i++) {
            int digit = s.charAt(i) - '1';
            if (digit == -1 || foundDigits[digit])
                return false;
            foundDigits[digit] = true;
        }

        return true;
    }
}
于 2014-04-01T19:58:54.047 回答