如何检查数组是否包含斐波那契数列？

Question

我在下面的代码中生成了一个基于NSArray数字中的最高数字停止的斐波那契数列。我正在检查numbers数组中的数字是否都是斐波那契数。我如何比较数字和fibonacciArray，以便如果数字都是斐波纳契数字，我的函数将返回yes，如果数字数组中的某些数字不是斐波那契数字，则返回no？

编辑：下面是示例性测试阵列是否有帮助..

[self onlyFibonacciValues:@[@21, @2, @8, @3]]; 
[self onlyFibonacciValues:@[@21, @6, @2]]; 


- (BOOL)onlyFibonacciValues:(NSArray *)numbers { 

NSArray *newNumbers = [numbers sortedArrayUsingDescriptors:@[[NSSortDescriptor sortDescriptorWithKey:@"intValue" ascending:YES]]]; 
NSMutableArray *sortedArray = [newNumbers mutableCopy]; 

NSInteger firstFibonacci = 1; 
NSInteger secondFibonacci = 2; 

NSInteger lastObjectInArray = [sortedArray.lastObject integerValue]; 

NSMutableArray *fibonacciArray = [NSMutableArray new]; 
[fibonacciArray addObject:[NSNumber numberWithInteger:firstFibonacci]]; 
[fibonacciArray addObject:[NSNumber numberWithInteger:secondFibonacci]]; 

while (lastObjectInArray > secondFibonacci) { 

    secondFibonacci = secondFibonacci + firstFibonacci; 
    firstFibonacci = secondFibonacci - firstFibonacci; 

    [fibonacciArray addObject:[NSNumber numberWithInteger:secondFibonacci]]; 

} 

return YES; 
} 

Answer 1

这是没有必要生成斐波那契数的所有新的数组，以便从当前的阵列检查值。所有你需要做的就是遍历当前数组的元素，检查每个元素到下一个斐波那契数。你可以在一个循环中做到这一点：

int curr = 1, prev = 1; 
for (NSNumber *n in newNumbers) { // You do not need a mutable copy of the sorted array 
    int v = [n intValue]; 
    while (curr < v) { 
     curr += prev; 
     prev = curr-prev; 
    } 
    // At this point curr is the next Fibonacci number 
    // which is greater than or equal to the current value 
    // in the array. Holes and duplicates are allowed. 
    if (curr != v) return NO; 
} 
return YES;