在 Java 中处理非常长的字符串（斐波那契问题）

Question

我正在研究 return 字符串 0 或 1 的斐波那契问题，并通过输入

给出的字符串对它们进行计数

f(0) = "0", f(1) = "1" , f(2) = "10"

当我运行我的代码在更大的 n 时，我的 java 是错误的

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3745)
    at java.base/java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:172)
    at java.base/java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:538)
    at java.base/java.lang.StringBuilder.append(StringBuilder.java:174)
    at fibo.sfibo(fibo.java:16)
    at fibo.main(fibo.java:42)

我想是因为我在变量中存储了太长的字符串谁能帮我处理长字符串

static String sfibo(int n){
    String a = "0";
    String b = "1";
    String c = "";
    int i=0;
    for (i=2;i<=n;i++){
        c = b+a;
        a = b;
        b = c;
    }
    return c;    
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine();
    String check = sc.nextLine();
    String text = sfibo(n);
    int lastindex = text.indexOf(check);
    int counter =1;
    while(1==1){
        lastindex = text.indexOf(check, lastindex+1);

        if (lastindex>=0){
            counter++;  
        }else{
            break;
        }
    }
   System.out.println(counter);
   sc.close();
}

编辑：我已经尝试使用BigInteger来存储数据，但它仍然溢出

Exception in thread "main" java.lang.ArithmeticException: BigInteger would overflow supported range
        at java.base/java.math.BigInteger.reportOverflow(BigInteger.java:1151)
        at java.base/java.math.BigInteger.checkRange(BigInteger.java:1146)
        at java.base/java.math.BigInteger.<init>(BigInteger.java:1121)
        at java.base/java.math.BigInteger.shiftLeft(BigInteger.java:3315)
        at fibo.sfibo(fibo.java:10)
        at fibo.main(fibo.java:22)

但现在我可以运行 sfibo(45) 上次出错 sfibo(43) 这是我的代码

static BigInteger sfibo(int n){
        BigInteger b = BigInteger.ONE;
        BigInteger c = new BigInteger("2");
        for (int i=3;i<=n;i++){
            BigInteger tmp = c;
            c = c.shiftLeft(b.bitLength()).add(b);
            b = tmp;
        }
        return c;
}

Answer 1

一个字符串，假设是一个现代的虚拟机，每个字符大约需要 1 个字节，只要我们说该字符串只包含 0 和 1 字符，有几十个开销最重要的是。因此，如果您的字符串包含大约 500 个零和一，则该字符串的内存负载约为 510 字节。鉴于您运行内存不足，请忘记 10，它相形见绌。就是里面有多少'digits'。

一个实际的数字使用每个零或一个而不是一个字节的一位。它的效率实际上提高了 8 倍。不幸的是，你不能只是使用 long - 这里的重点是你的 fib 数字比适合 long（64 位）的数字大。

相反，您需要一个任意长度的数字，但每个二进制数字不超过一位。

有几种方法可以做到这一点，但最明显和最简单的方法是使用 java.math.BigInteger。

这为您带来了 8 倍的收益：您的代码在达到某个数字（例如 100 万）之前一直有效 zeroes/ones，将 String 替换为 BigInteger 将使您达到800万zeroes/ones.

然而，这实际上并没有给你带来太多好处：Fib 增长得非常快。

更进一步，您根本无法再使用内存，您必须插入 4TB 硬盘并开始向其中写入数据。

毫无疑问，到那时需要几天的时间。

通常您需要退后一步：如果您尝试计算 Fib(10000000)，为什么，以及您实际需要输出的哪些方面？这些数字对于简单的计算机工作来说太大了，你需要得到 'smart' 并找出你需要的具体方面。当然不是 'every digit'，因为确实有数万亿。

在 Java 中处理非常长的字符串（斐波那契问题）

Working with really long String in Java (Fibonacci problem)

java

fibonacci