Java: 检查arraylist是否是斐波那契数列的一部分

Question

我的学校作业是实现一种检查给定 ArrayList 是否属于斐波那契数列的方法。

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

我知道我必须检查数组中的一个数字和下一个数字是否属于斐波那契数列，但是我遇到了很多麻烦，因为你应该接受数组（如果有的话）序列的一部分，而不只是从一开始。

例如：0 1 1 2 3 5 和 2 3 5 8 13 21 一样被接受。

到目前为止，这是我的代码。我知道它有很大的缺陷，但我真的不知道如何继续。

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;
}

非常感谢任何帮助！

Answer 1

private boolean isFib(final List<Integer> li) {
    //check if each int is the sum of the two prior ints
    for (int i = 2; i < li.size(); i++) {
        if (li.get(i) != li.get(i - 1) + li.get(i - 2)) {
            return false;
        }
    }

    //reverse the fibonacci sequence and check if we end up at the correct starting point (0, 1)
    int i1 = li.get(0);
    int i2 = li.get(1);

    while (i1 > 0) {
        final int tmp = i1;
        i1 = i2 - i1;
        i2 = tmp;
    }

    return i1 == 0 && i2 == 1;
}

Answer 2

好吧，您的代码有一些问题。首先，如果你的数组至少有 3 个项目，你检查是否只有前三个是斐波那契数列的开始：

//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 将 return 为真。

您需要做的是将其分成两个任务：

找到序列中的第一个相关数字（即如果数组以 7 开头，您知道这不是序列的一部分；或者，如果它以 8 开头，你知道你需要从 8 开始检查。
找到 "start" 后，只需检查数组的其余部分是否遵循斐波那契规则。您需要手动验证前两项。

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;
}

Answer 3

我建议一个解决方案，它在单独的 Iterator<Integer> 中抽象出斐波那契数列生成器，然后使用它来检查提供的列表是否与序列的任何部分匹配。

迭代器非常简单明了：

public static class FiboIterator implements Iterator<Integer> {

    @Override
    public boolean hasNext() { return true; }

    int i = -1, j = -1;   // previous two items of Fibo sequence

    @Override
    public Integer next() {
        int k = (i < 0) ? (j < 0 ? 0 : 1) : (i + j);
        i = j;
        j = k;
        return k;
    }
}

主要检查方法：

public static boolean isFibo(List<Integer> seq) {
    if (seq.size() < 3)
        return false;
    final Iterator<Integer> f = new FiboIterator();
    int start = seq.get(0), k;
    while ((k = f.next()) < start);         // roll Fibo to match the starting item in input
    if (start != k)                         // starting item doesn't match
        return false;
    if (start == 1 && seq.get(1) != 1)      // special case: [1, 2, ...]
        f.next(); 
    for (int i = 1; i < seq.size(); i++) {  // check if other items match
        if (seq.get(i) != f.next())
            return false;
    }
    return true;
}

最后是一些单元测试：

@Test
public void testFibo() {
    assertTrue(isFibo(Arrays.asList(0, 1, 1, 2)));
    assertTrue(isFibo(Arrays.asList(1, 1, 2, 3, 5)));
    assertTrue(isFibo(Arrays.asList(1, 2, 3, 5, 8)));
    assertTrue(isFibo(Arrays.asList(5, 8, 13, 21, 34)));

    assertFalse(isFibo(Arrays.asList(1, 2, 0)));
    assertFalse(isFibo(Arrays.asList(1, 0, 1)));
    assertFalse(isFibo(Arrays.asList(5, 5, 10, 15)));
}

Java: 检查arraylist是否是斐波那契数列的一部分

Java: check if arraylist is part of fibonacci sequence

java

arraylist

fibonacci