Java：arraylistがフィボナッチ配列の一部であるかどうかを調べる

Question

私の学校への割り当ては、与えられたArrayListがフィボナッチ配列の一部であるかどうかをチェックする方法を実装することです。

配列が空であってはならないと

大きなより3.私は、アレイと次の1の1つの数がフィボナッチ数列の一部であるかどうかを確認する必要があることを理解しなければなりません、しかし、私はたくさんありますシーケンスの一部であって最初からではない場合は、配列を受け入れることになっているからです。

例：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

あなたのコードにはいくつか問題があります。あなたの配列は、少なくとも3つの項目である場合にのみ、最初の3は、フィボナッチ数列の開始であればまず第一に、あなたは確認してください。これはシーケンスの一部ではないある0 1 1 5を意味するよう

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

これは、悪いですtrueを返します。あなたがする必要がどのような

は、次の2つのタスクにこれを分割されます。シーケンスの最初の関連する番号を（検索

• すなわち配列が7で始まる場合、あなたはこのシーケンスの一部ではありません知っていますまた、8で始まる場合は、8以降のチェックを開始する必要があります）。
• "開始"が見つかったら、配列の残りの部分がフィボナッチルールに従っているかどうかを確認してください。最初の2つの項目を手動で確認する必要があります。

---

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 2

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 3

私は、提供されたリストは、シーケンスの任意の部分と一致するかどうかを確認するためにそれを使用して、別のIterator<Integer>でフィボナッチ数列ジェネレータを抽象化するソリューションをお勧めしたいです。

イテレータは非常にシンプルで簡単です：最後に

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

といくつかのユニットテスト：

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

主なチェック方法

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