3
我想分裂一個大整數的數字。讓我更具體一點。我正在使用Fibonacci序列生成一個大整數,現在使用這個算法我需要循環,直到找到一個BigInteger,其中前9位數字和最後9位數字是pandigital。唯一的問題是我必須循環的數量是300K(現在BigInteger會非常龐大)。分裂BigIntegers數字
我已經嘗試將BigInteger轉換爲字符串,然後使用「substring(begin,end)」。但是,這太慢了,只花了將近28分鐘來完成10萬個指數。
有一個數學解決方案,但我不完全確定它是什麼,如果有人可以帶領我在正確的方向很多將不勝感激。注意:我不直接要求答案,只是尋找正確答案的一步。
這裏是我的代碼,以防萬一你想知道:
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;
}
}
'但是,這是如此之慢,......什麼是慢?字符串轉換本身?取子串?還是計算過程? – 2013-03-05 05:58:03
緩慢的部分是BigInteger的子字符串,因爲你正在子串如此龐大的數字。如果我把它提高了,可能需要6個小時300k – 2013-03-05 05:59:12
對不起,還是不明白:'BigInteger.toString()'或'String.substring'。你只需要9個符號,它不應該花費太多時間。 – 2013-03-05 06:02:48