2014-10-07 69 views
1

我在下面的代碼中生成了一個基於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; 
} 

回答

2

這是沒有必要生成斐波那契數的所有新的數組,以便從當前的陣列檢查值。所有你需要做的就是遍歷當前數組的元素,檢查每個元素到下一個斐波那契數。你可以在一個循環中做到這一點:

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; 
+0

如果數字是這樣的,你的公式會工作嗎? [self onlyFibonacciValues:@ [@ 21,@ 6,@ 2]]; – Jon 2014-10-07 03:07:52

+0

@JonJungemann你的意思是你被允許在序列中有一個「洞」?..目前不是,但變化是相當小的... – dasblinkenlight 2014-10-07 03:09:21

+0

對不起,我應該更具體的 – Jon 2014-10-07 03:11:17