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

Question

我在下面的代码中生成了一个斐波那契数列，该数列根据 NSArray 数字中的最高数字停止。我正在尝试检查数字数组中的数字是否都是斐波那契数。我如何比较数字和 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;