Java的：检查是否ArrayList是斐波纳契数列的一部分 [英] Java: check if arraylist is part of fibonacci sequence

问题描述

我对学校的任务是实施检查，如果给定的方法的ArrayList 是斐波那契序列的一部分。

My assignment for school is to implement a method that checks if a given ArrayList is part of the Fibonacci sequence.

该数组不能为空，且必须大于3。

The array must not be empty and must be bigger than 3.

我明白，我要检查，如果数组和下一个中一个号码是斐波那契序列的一部分，但是我有很多与它的麻烦，因为你应该接受数组，如果它的任何部分序列而不是仅仅从一开始。

I understood that I have to check if one number of the array and the next one are part of the Fibonacci sequence, however I have a lot of trouble with it since you're supposed to accept the array if it's any part of the sequence and not just from the start.

例如： 0 1 1 2 3 5 将被接受，以及 2 3 5 8 13 21 。

e.g.: 0 1 1 2 3 5 will be accepted as well as 2 3 5 8 13 21.

这是我的code为止。我知道这是非常有缺陷的，但我真的不知道如何继续前进。

This is my code so far. I know it's very flawed but i really have no clue how to move on.

public class ArrayCheck {
 /**
 * Tests if the given array is a part of the Fibonacci sequence.
 *
 * @param arr array to be tested
 * @return true if the elements are part of the fibonacci sequence
 */
public boolean isFibonacci(ArrayList<Integer> arr) {
    //check if array exists
    if(arr.size() == 0)
        return false;

    //check if array is bigger than 3
    if (arr.size() < 3)
        return false;

    //check for the startsequence of 0,1,1
    else if(arr.get(0) == 0 && arr.get(1) == 1 && arr.get(2) == 1)
        return true;

    //check every number in array
    for(int i = 0; i < arr.size(); i++) {
        //check if i >= 2 is fib
        if(i >= 2) {
            int fibn = i;
            int nextfib = i + 1;

            int fibnew = (fibn - 1) + (fibn - 2);
            int fibnext = (nextfib - 1) + (nextfib - 2);

            if (arr.get(i) != fibnew && arr.get(i + 1) != fibnext)
                return false;
        }
        //check if the order is right
        if(arr.get(i) > arr.get(i+1))
            return false;
    }
    return true;
}

任何帮助是极大AP preciated！

Any help is greatly appreciated!

推荐答案

好了，你有你的code的几个问题。首先，如果你的数组至少为3项，检查是否只有前三个是斐波那契序列的开始：

Well, you have a few issues with your code. First of all, if you array is at least 3 items, you check if only the first three are the start of the Fibonacci sequence:

//check for the startsequence of 0,1,1
else if(arr.get(0)==0 && arr.get(1)==1 && arr.get(2)==1){
    return true;
}

这是不好的，因为这意味着 0 1 1 5 这不是序列的一部分将返回true。

This is bad, as this mean 0 1 1 5 which is not part of the sequence will return true.

您需要做的是这样分成两个任务：

What you need to do is split this into two tasks:

• 找到序列中的第一个相关的数字（即如果阵列 7 开始，你知道这是不是序列的一部分;或者，如果它开始与 8 ，你知道你需要开始从 8 检查起）。


• 一旦你找到启动，只需检查阵列的其余部分遵循斐波纳契规则。你需要手动验证前两个项目。

• Find the first relevant number in the sequence (i.e. if the array starts with 7, you know this isn't a part of the sequence; alternatively, if it starts with 8, you know you need to start checking from 8 onward).
• Once you've found the "start", simply check that the rest of the array follows the Fibonacci rule. you'll need to manually verify the first two items.

public boolean isFibonacci(ArrayList<Integer> arr) {

    if (arr.size() < 3){
        return false;
    }

    /** find if the first element is part of the sequence: **/

    int fib1 = 0;
    int fib2 = 1;

    while (fib1 < arr.get(0)) {
        int tmp = fib1 + fib2;
        fib1 = fib2;
        fib2 = tmp;
    }

    if (fib1 != arr.get(0)) {
        // first element is not part of Fibonacci sequence
        return false;
    }

    if (fib2 != arr.get(1)) {
       // the first two elements are not part of the Fibonacci sequence
       return false;
    }

    /*** now simply verify that the rest of the elements uphold the rule:
         each element is the sum of the two previous ones: **/

    for(int i=2; i < arr.size(); i++) {

        // make sure there are no negatives in the array:
        if (arr.get(i) < 0)
           return false;

        if (arr.get(i) != (arr.get(i-1) + arr.get(i-2)))
           return false;

    }

    //everything checks out okay - return true:
    return true;
}

这篇关于Java的：检查是否ArrayList是斐波纳契数列的一部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！