Java - 改变斐波那契兔子 - Java 堆空间错误

Question

情况是这样的 - 斐波那契通过研究一对每月繁殖的兔子和另一对将在下个月繁殖的兔子，开发了他的递归序列 f(n) = f(n-1) + f(n-2)。我正在改变这种情况，使它们在第一个月后不再繁殖，而是在第二个月后繁殖。我输出中的数字是正确的。然而，我的问题是，45 个月后，由于某种原因，我收到了 Java 堆空间错误。我尝试过使用 long 和 double 来代替，但没有成功。请让我知道你在想什么。代码:

import java.util.*;
import java.io.*;
import java.lang.System.*;

public class Rabbits {
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new File("rabbits.dat"));
        int numSets = Integer.parseInt(in.nextLine().trim());
        for(int curSet = 0; curSet<numSets; curSet++){
            ArrayList<Integer> population = new ArrayList<>();
            population.add(0);
            int months = Integer.parseInt(in.nextLine().trim());
            for(int i = 0; i < months; i++){
                int matured = 0;
                for(int pos = 0; pos<population.size(); pos++){
                    population.set(pos, population.get(pos)+1);
                    if(population.get(pos)>=3){
                        matured++;
                    }
                }
                for(int n = 0; n<matured; n++){
                    population.add(0);
                }
            }
            System.out.println("Months: " + months + " Population: " + population.size());
        }
    }

}

输入:

28
1
2
3
4
5
6
7
8
9
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100

和输出:

--------------------Configuration: <Default>--------------------
Months: 1 Population: 1
Months: 2 Population: 1
Months: 3 Population: 2
Months: 4 Population: 3
Months: 5 Population: 4
Months: 6 Population: 6
Months: 7 Population: 9
Months: 8 Population: 13
Months: 9 Population: 19
Months: 10 Population: 28
Months: 15 Population: 189
Months: 20 Population: 1278
Months: 25 Population: 8641
Months: 30 Population: 58425
Months: 35 Population: 395033
Months: 40 Population: 2670964
Months: 45 Population: 18059374
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2245)
    at java.util.Arrays.copyOf(Arrays.java:2219)
    at java.util.ArrayList.grow(ArrayList.java:213)
    at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:187)
    at java.util.ArrayList.add(ArrayList.java:411)
    at Rabbits.main(Rabbits.java:22)

Process completed.

Answer 1

不幸的是，您目前的做法行不通。您为每只兔子保留一个整数。由于兔子的数量迅速增加，因此无法将每只兔子都放在一个数组中。

由于您只需要知道兔子的年龄，因此您可以保留代表特定年龄的兔子数量的变量。随着每个月的过去，所有兔子的年龄都会增加，新兔子在 0 岁时出生。

通过这种方式，您可以跟踪成熟兔子的数量，以及每个年龄段的兔子数量。

最终的种群数量只是不同年龄段所有兔子的总和。

Scanner in = new Scanner(new File("src/q22565464/rabbits.dat"));
int numSets = Integer.parseInt(in.nextLine().trim());

for(int curSet = 0; curSet<numSets; curSet++){
   int months = Integer.parseInt(in.nextLine().trim());
   // Could be converted to an array, left for clarity's sake
   long matured = 0;
   long age2 = 0;
   long age1 = 0;
   long age0 = 1;

   for(int i = 0; i < months; i++){
    // the ages of the rabbits increase with each month
       matured += age2;
       age2 = age1;
       age1 = age0;
       age0 = matured;
   }
   System.out.println("Months: " + months + " Population: " + (matured+age2+age1+age0));
}
in.close();