Java - Pisano 周期计算错误

Question

我正在尝试制作一个程序，输出斐波那契数列中某个用户输入的数字的皮萨诺周期。程序一直很好，直到我到达 10。程序会无限循环。当我有一个包含 120 个余数的数组时(10 的皮萨诺周期是 60，因此要检查数组是否重复，我至少需要 60*2=120 个余数)，我会检查数组。但数组并不相同。这是数组(余数 1 到 60 和 61 到 120)

    [1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9,  0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0]
    [1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 0, 4, 4, 4, 8, 2, 0, 4, 4, 8, 4, 0, 6, 6, 2, 6, 0, 6, 6, 4, 4, 6, 0, 6, 4, 0, 4, 2, 4, 6, 0, 8, 4, 0, 4, 4, 8, 4, 2, 8, 4, 4]

这是我的代码:

主要代码:`导入java.util.Scanner;

公共(public)类 PisanoPeriod {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    boolean quit = false;
    while (!quit) {
        System.out.print("Enter a number: ");
        int divisor = scan.nextInt();
        FibonacciSequence f = new FibonacciSequence();
        System.out.println("Computing...");
        System.out.println("The Pisano Period for "+divisor+" is: "+f.getPisanoPeriod(divisor));            
        printDivisor(20);
        System.out.print("Do you want to do another one? (y/n): ");
        String reply = scan.next();
        if (reply.equals("n") || reply.equals("no")) {
            printDivisor(20);
            System.out.println("Bye!");
            quit = true;
        }
    }

}

private static void printDivisor(int n) {
    System.out.print("\n");
    for (int i=1; i<=n; i++) {
        System.out.print("*");
        if (i==n) {
            System.out.print("\n\n");
        }
    }
}
}

还有 FibonacciSequence 类，问题可能是:`导入java.util.Arrays;

公共(public)类斐波那契数列{

private double[] Sequence = new double[2];
private BadNumberException badnumexception = new BadNumberException("Number of fibonnacci numbers is too small.");
private TooLittleNumbersException tlnexception = new TooLittleNumbersException();

public FibonacciSequence() {
    try {
      generate(10);
    }
    catch(BadNumberException e) {System.out.println(e.getMessage());}
}

private int getSequenceLength() {
    return Sequence.length;
}

private boolean checkForPattern(int[] array) {
    int half_point = array.length/2;
    boolean return_boolean = true;
    for (int i=0; i<half_point; i++){
        if (array[i]!=array[i+half_point]){
            return_boolean = false;

            break;
        }
        else {
            if (i==half_point-1) {
                System.out.println(Arrays.toString(Arrays.copyOfRange(array, 0, half_point)));
                System.out.println(Arrays.toString(Arrays.copyOfRange(array, half_point, array.length)));
            }
        }
    }
    if (array.length==120){
        System.out.println(Arrays.toString(Arrays.copyOfRange(array, 0, half_point)));
        System.out.println(Arrays.toString(Arrays.copyOfRange(array, half_point, array.length)));
    }
    return return_boolean;
}

public int getPisanoPeriod(int n) {
    int return_value = -1;
    int max_index_counter=0;
    boolean error = true;
    while (error) {
        try {
          boolean pattern_reached = false;
          int[] remainder_array = new int[0];
          int index_counter = 0;
          while (!pattern_reached) {
              if (index_counter>=max_index_counter) {
                  max_index_counter = index_counter;
                  System.out.println(max_index_counter);
              }
              int[] temp_array = new int[remainder_array.length+1];
              for (int i=0; i<remainder_array.length; i++) {
                  temp_array[i] = remainder_array[i];
              }
              remainder_array = temp_array;
              remainder_array[index_counter] = (int) (Sequence[index_counter]%n);
              //System.out.println(Arrays.toString(Sequence));
              if (remainder_array.length%2==0 && index_counter>n)
                  pattern_reached = checkForPattern(remainder_array);
              index_counter++;
          }
          return_value = remainder_array.length/2;
          error = false;
        }
        catch (IndexOutOfBoundsException e) {
            try {
                throw tlnexception;
            } catch (TooLittleNumbersException a) {
                try {
                    //if (getSequenceLength()<50)
                    generate(getSequenceLength()+1);
                    /*else
                        error=false;*/
                    //System.out.println(getSequenceLength()+10);
                } catch (BadNumberException b) {}
            }
        }
    }
    return return_value;
}

public void generate(int n) throws BadNumberException {

    if (n<=2) throw badnumexception;
    double[] generated_array = new double[n];
    generated_array[0] = 1;
    generated_array[1] = 1;
    for (int i=2; i<n; i++) {
        generated_array[i] = generated_array[i-1]+generated_array[i-2];
        //System.out.println(generated_array[i]);
    }
    Sequence = generated_array;
}
}

预先感谢您提供任何提示。

Answer 1

问题显然在于 remainder_array[index_counter] = (int) (Sequence[index_counter]%n); 行的转换机制；

转换将整数从 double 向下舍入，因此两个数组中的余数不同。我不能使用很长时间，因为它没有那么多的内存容量。因此，我将 BigInteger 类用于 Sequence 数组，这解决了问题。