波非那切数列算法

波非那切数列：0 1 1 2 3 5 8 13.....
第n项是第n-1项和n-2项的和。第一项为0，第二项为1。

简单思考，可以用递归：

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

运行起来结果看上去没什么问题，但是如果n很大，那一次递归调用两次本身，类似于二叉树往下分裂，1生2,2生4，对于内存的消耗是指数级增长。当执行test（45）时，运算耗时就达到9s多；执行test（46）时，运算耗时14s；执行test(47)时，运算耗时21s；如果n更大，消耗的时间指数级增长，所以就要思考怎么处理优化这个算法。

我们知道，数列的特性是f(n)=f(n-1)+f(n-2)，循环往复，那能不能写个循环处理呢，一开始需要定义两个变量a和b，每循环一次，a的值变为原来b的值，b的值变为原来a+b的值，根据这个思路，写出下面方法：

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

这个方法只会有两个变量，循环操作，所以比上面递归要节约内存，这里面还有个问题，就是n比较大时，会有数据越界的问题，这时候就需要用字符串来处理结果了：

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