1

さて、私は友人の1人が私にやらせてくれた課題を解決しようとしています。まあBigInteger、最初の9桁を切り落とす方法があったので、最後の9桁を切り落とすように管理しました。時間がかかりすぎました。

最初の9と最後の9が必要な理由はBigInteger、最初と最後がパンデジタルである場所を探しているからです。

意味がわからない場合はn = new BigInteger("123456789987654321")、「123456789」と「987654321」を別々に取得する必要があります。これは非常に遅いプロセスであるため、BigIntegerを文字列に変換したくありません。

私はここでスピードを求めています、私はこの解決策に困惑しています。黄金比の使用について何か聞いたことがありますか？興味があれば、これが私のコードです。

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(350_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++)
        {   

            // TODO: Check if the head is pandigital as well.
            BigInteger tailing9Digits = tailing9Digits(prev1);
            boolean tailPandigital = isPanDigital(tailing9Digits);

            if (tailPandigital)
            {                   
                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)
    {
        // STUCK HERE.
        return null;
    }

    public static BigInteger tailing9Digits(BigInteger x) 
    {
        return x.remainder(BigInteger.TEN.pow(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

4 に答える 4

1

BigInteger速度を気にするなら、これは私が使用することをお勧めするものではありません。そのメソッドのほとんどは実装が不十分であり、これにより通常、コードが非常に遅くなります。

分割統治法には、除算と基数の変換に役立つと思われるトリックがあります。

まず、BigInteger'smultiply()は2次式です。それを回避する必要があります。そうしないと、これらの分割統治法はスピードアップにつながりません。高速フーリエ変換による乗算は、適度に高速で優れています。

BigIntegeraを基数10に変換する場合は、半分（ビット単位）に分割して次のように記述しa * 256^k + b. ます。実行できる1つの方法は、再帰的に基数10に変換aしてから、2乗を繰り返して小数に変換し、基数10で変換することです。乗算して結果に追加します。また、最初の数桁のみに関心があるため、の最初の数桁が。のような小さなものを追加しても影響を受けない場合は、変換する必要がない場合もあります。b256^ka256^kbba * 256^kb

同様のトリックが除算でも機能します。

この方法を使用して、ビットシフトと抽出を行うことができますtoByteArray()。

于 2013-03-07T04:48:10.700 に答える
0

私はJavaの初心者です。BigIntegerを文字列のみに変換していますが、コードよりも少し高速です。

import java.math.BigInteger;
public class Main {
    public static void main(String args[])
    {       
        long timeStart = System.currentTimeMillis();
        String biStr = new BigInteger("123456789987654321").toString();
        int length=(biStr.length())/2;
        String[] ints = new String[length];
        String[] ints2 = new String[length];
        for(int i=0; i<length; i++) {
            int j=i+length;
            ints[i] = String.valueOf(biStr.charAt(i));
            ints2[i] = String.valueOf(biStr.charAt(j));
            System.out.println(ints[i] +"  |  "+ints2[i]);
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }
}
于 2013-03-07T05:23:59.013 に答える
0

さて、これがあなたが必要としているものだと私は信じています：

import java.math.BigInteger;

public class PandigitalCheck {

    public static void main(String[] args) {

        BigInteger num = new BigInteger("12345678907438297438924239987654321");
        long timeStart = System.currentTimeMillis();
        System.out.println("Is Pandigital: " + isPandigital(num));
        long timeEnd = System.currentTimeMillis();
        System.out.println("Time Taken: " + (timeEnd - timeStart) + " ms");
    }

    private static boolean isPandigital(BigInteger num) {
        if (getTrailing9Digits(num).compareTo(getLeading9Digits(num)) == 0) {
            return true;
        }

        return false;
    }

    private static BigInteger getLeading9Digits(BigInteger num) {
        int length = getBigIntLength(num);
        BigInteger leading9 = BigInteger.ZERO;
        for (int i = 0; i < 9; i++) {
            BigInteger remainder = num.divide(BigInteger.TEN.pow(length - 1 - i));
            leading9 = leading9.add(remainder.multiply(BigInteger.TEN.pow(i)));
            num = num.remainder(BigInteger.TEN.pow(length - 1 - i));
        }

        return leading9;
    }

    private static int getBigIntLength(BigInteger num) {
        for (int i = 1; ; i++) {
            if (num.divide(BigInteger.TEN.pow(i)) == BigInteger.ZERO) {
                return i;
            }
        }
    }

    private static BigInteger getTrailing9Digits(BigInteger num) {
        return num.remainder(BigInteger.TEN.pow(9));
    }

}

出力は次のとおりです。

Is Pandigital: true
Time Taken: 0 ms

それは法案に適合しますか？

于 2013-03-07T05:19:04.473 に答える
0

多分これは速すぎないかもしれませんが、少なくとも単純です

    BigInteger n = new BigInteger("123456789987654321");
    BigInteger n2 = n.divide(BigInteger.TEN.pow(new BigDecimal(n).precision() - 9));
    BigInteger n1 = n.remainder(new BigInteger("1000000000"));
    System.out.println(n1);
    System.out.println(n2);

出力

987654321
123456789
于 2013-03-07T05:08:13.647 に答える