OC算法03：斐波那契数列探索

简介

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由 之前的两数相加。

排列组合

问：有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第 10 级台阶有几种不同的走法?

分析：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13…… 所以，登上十级，有 89 种走法。

答：

- (void)demo{
    // 有10级台阶
    NSInteger tjNum = 10;
    
    NSInteger total = [self getTotalNumOfMethods:tjNum];
    
    NSLog(@"total:%ld",total);
}

- (NSInteger)getTotalNumOfMethods:(NSInteger)num{
    if (num == 0) {
        return 0;
    }
    if (num == 1) {
        return 1;
    }
    if (num == 2) {
        return 2;
    }
    return [self getTotalNumOfMethods:num-1] + [self getTotalNumOfMethods:num - 2];
}

打印结果：89

兔子繁殖问题

斐波那契数列又因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。

问：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

分析：我们不妨拿新出生的一对小兔子分析一下：
第一个月小兔子没有繁殖能力，所以还是一对

两个月后，生下一对小兔对数共有两对

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对
－－－－－－
依次类推可以列出下表：

幼仔对数=前月成兔对数
成兔对数=前月成兔对数+前月幼仔对数
总体对数=本月成兔对数+本月幼仔对数
可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。

答：

- (void)demo1{
    NSInteger month = 12;
    
    NSInteger tuTotal = [self getTuTotalNum:month];
    
    NSLog(@"tuTotal:%ld",tuTotal);
}

- (NSInteger)getTuTotalNum:(NSInteger)month{
    if (month == 0) {
        return 1;
    }
    if (month == 1) {
        return 1;
    }
    if (month == 2) {
        return 2;
    }
    return [self getTuTotalNum:month-1] + [self getTuTotalNum:month - 2];
}

打印结果：233