斐波那契系列问题

准备校招的！ 这些是一本书的笔记吧—程序员代码面试指南：IT名企算法与数据结构题目最优解（左程云）。

给定整数N，返回斐波那契数列的第N项。给定整数N，代表台阶数，一次可以跨2个或者1个台阶，返回有多少种走法假设农场中成熟的母牛每年只会生1头小母牛，并且永远不会死。第一年农场有1只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛3年之后成熟又可以生小母牛。给定整数N，求出N年后牛的数量。

以上问题均可以使用递归去理解；

F(N)=F(N-1)+F(N-2);S(N)=S(N-1)+S(N-2);C(N)=C(N-1)+C(N-3);

第一个菲波那切数列就不解释了：1 1 2 3 5 8 13 …

第二个台阶问题：如果台阶有N级，那么登上第N级的办法有两种，N-2跨2级台阶，或者N-1跨1级台阶；

第三个牛问题：理解比较费事！原作者是这么说的：N-1年的牛毫无损失的活到N年，同时所有成熟的牛都会生一头新的牛。那么成熟的牛到底有多少呢？N-3年的牛到N年肯定都是成熟的牛，期间出生的牛肯定都没有成熟。 图解： java算法描述:

第一个：

public static int f2(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return 1; } int res = 1; int pre = 1; int tmp = 0; for (int i = 3; i <= n; i++) { tmp = res; res = res + pre; pre = tmp; } return res; }

第二个：

public static int s2(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return n; } int res = 2; int pre = 1; int tmp = 0; for (int i = 3; i <= n; i++) { tmp = res; res = res + pre; pre = tmp; } return res; }

第三个：

public static int c2(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2 || n == 3) { return n; } int res = 3; int pre = 2; int prepre = 1; int tmp1 = 0; int tmp2 = 0; for (int i = 4; i <= n; i++) { tmp1 = res; tmp2 = pre; res = res + prepre; pre = tmp1; prepre = tmp2; } return res; }

思想就是递归。