波非那切數(shù)列：0 1 1 2 3 5 8 13.....
第n項(xiàng)是第n-1項(xiàng)和n-2項(xiàng)的和。第一項(xiàng)為0，第二項(xiàng)為1。

簡(jiǎn)單思考，可以用遞歸：

NSInteger test(NSInteger n)
{
    if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        return test(n-1) + test(n-2);
    }
}

運(yùn)行起來(lái)結(jié)果看上去沒(méi)什么問(wèn)題，但是如果n很大，那一次遞歸調(diào)用兩次本身，類似于二叉樹往下分裂，1生2,2生4，對(duì)于內(nèi)存的消耗是指數(shù)級(jí)增長(zhǎng)。當(dāng)執(zhí)行test（45）時(shí)，運(yùn)算耗時(shí)就達(dá)到9s多；執(zhí)行test（46）時(shí)，運(yùn)算耗時(shí)14s；執(zhí)行test(47)時(shí)，運(yùn)算耗時(shí)21s；如果n更大，消耗的時(shí)間指數(shù)級(jí)增長(zhǎng)，所以就要思考怎么處理優(yōu)化這個(gè)算法。

我們知道，數(shù)列的特性是f(n)=f(n-1)+f(n-2)，循環(huán)往復(fù)，那能不能寫個(gè)循環(huán)處理呢，一開始需要定義兩個(gè)變量a和b，每循環(huán)一次，a的值變?yōu)樵瓉?lái)b的值，b的值變?yōu)樵瓉?lái)a+b的值，根據(jù)這個(gè)思路，寫出下面方法：

- (long)test:(long)n
{
    if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        long a = 0;
        long b = 1;
        for (int i = 0; i < n-1; i++) {
            b = a + b;
            a = b - a;
        }
        return b;
    }
}

這個(gè)方法只會(huì)有兩個(gè)變量，循環(huán)操作，所以比上面遞歸要節(jié)約內(nèi)存，這里面還有個(gè)問(wèn)題，就是n比較大時(shí)，會(huì)有數(shù)據(jù)越界的問(wèn)題，這時(shí)候就需要用字符串來(lái)處理結(jié)果了：

- (NSString *)calculate:(NSInteger)n
{
    if (0 == n) {
        return @"0";
    } else if (1 == n) {
        return @"1";
    } else {
        NSString *a = @"0";
        NSString *b = @"1";
        for (int i = 0; i < n-1; i++) {
            if (i == 16) {
            }
            b = [self subStr1:a str2:b];
            a = [self minusStr1:b str2:a];
        }
        return b;
    }
}

- (NSString *)subStr1:(NSString *)str1 str2:(NSString *)str2
{
    NSMutableString *result = [NSMutableString string];
    NSInteger maxLength = MAX(str1.length, str2.length);
    BOOL flag = NO;
    for (int i = 0; i < maxLength; i++) {
        int num1 = 0;
        int num2 = 0;
        if (str1.length > i) {
            num1 = [[str1 substringWithRange:NSMakeRange(str1.length - i - 1, 1)] intValue];
        }
        if (str2.length > i) {
            num2 = [[str2 substringWithRange:NSMakeRange(str2.length - i - 1, 1)] intValue];
        }
        [result insertString:[NSString stringWithFormat:@"%d", (num1 + num2 + (flag ? 1 : 0)) % 10] atIndex:0];
        flag = num1 + num2 + (flag ? 1 : 0) > 9;
    }
    if (flag) {
        [result insertString:@"1" atIndex:0];
    }
    return [result copy];
}

- (NSString *)minusStr1:(NSString *)str1 str2:(NSString *)str2
{
    NSMutableString *result = [NSMutableString string];
    NSInteger maxLength = MAX(str1.length, str2.length);
    BOOL flag = NO;
    for (int i = 0; i < maxLength; i++) {
        int num1 = 0;
        int num2 = 0;
        if (str1.length > i) {
            num1 = [[str1 substringWithRange:NSMakeRange(str1.length - i - 1, 1)] intValue];
        }
        if (str2.length > i) {
            num2 = [[str2 substringWithRange:NSMakeRange(str2.length - i - 1, 1)] intValue];
        }
        int insertValue = num1 - num2 - (flag ? 1 : 0);
        if (insertValue < 0) {
            insertValue += 10;
        }
        [result insertString:[NSString stringWithFormat:@"%d", insertValue] atIndex:0];
        flag = num1 - (flag ? 1 : 0) < num2;
    }
    while ([[result substringToIndex:1] isEqualToString:@"0"]) {
        result = [result substringFromIndex:1];
    }
    return [result copy];
}