前9位数字的切割
好吧，我正试着解决一个挑战，我的一个朋友给我做的，嗯，我已经把最后9位数从一个BigInteger井切下来，我有办法切断前9位，但是太慢了，太长了。
我需要前9和最后9的原因是因为我正在寻找一个BigInteger，其中第一个和最后一个是泛数字。
如果你不明白我说的n = new BigInteger("123456789987654321")是什么意思的话，那么我需要分别得到"123456789“和"987654321”，而 not 想要将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
Stack Overflow用户
发布于 2013-03-07 04:48:10
如果你关心速度的话，我建议你不要使用BigInteger。它的大多数方法都没有得到很好的实现，这通常导致代码非常慢。
在除法和基数转换方面有一个分而治之的技巧，你可能会发现这很有帮助。
首先，BigInteger的multiply()是二次型的。你需要解决这个问题，否则这些分而治之的技巧不会导致任何加速。通过快速傅里叶变换进行乘法是相当快和好的。
如果要将BigInteger转换为基数10，将其拆分成一半(按位)并将其写入a * 256^k + b.，您可以做的一件事是递归地将a和b转换为基数- 10，然后通过重复平方将256^k转换为十进制，然后在基数10中，将a乘以256^k并向结果中添加b。此外，由于您只对前几位数字感兴趣，如果b的前几位数字不可能通过添加像b这样小的东西来影响，那么甚至不需要转换b。
同样的技巧也适用于组织。
您可以使用toByteArray()方法进行位移位和提取。
Stack Overflow用户
发布于 2013-03-07 05:08:13
也许这不是太快，但至少很简单
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
123456789Stack Overflow用户
发布于 2013-03-07 05:19:04
我相信这就是你所需要的：
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符合要求吗？
https://stackoverflow.com/questions/15262999
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号