兔子算法求编程代码参考!该如何处理
兔子算法求编程代码参考!
假设有一对兔子 刚出生是1 表示1月份 然后过一个月长大 2月份 3月份繁殖 现在又两对了。在4月份时 第一对兔子又繁殖就是2+1 第二对兔子长大 现在是3对。5月份时 第一对兔子又繁殖 3+1 第二对兔子繁殖 4+1 现在是5对 以此类推(兔子不死) 求1年后 有多少对?n年呢?
------解决方案--------------------
第几月 兔子 个数
1 1
2 1
3 2
4 3
5 5
第N年的兔子 其实 是第n-1年+上n-2年的兔子生的兔子
所以 就是f(n)=f(n-1)+f(n-2)
考虑到可能是面试,就没有用递归,这么写 复杂度会小点,当然 Dictionary也可以用int[]
假设有一对兔子 刚出生是1 表示1月份 然后过一个月长大 2月份 3月份繁殖 现在又两对了。在4月份时 第一对兔子又繁殖就是2+1 第二对兔子长大 现在是3对。5月份时 第一对兔子又繁殖 3+1 第二对兔子繁殖 4+1 现在是5对 以此类推(兔子不死) 求1年后 有多少对?n年呢?
------解决方案--------------------
第几月 兔子 个数
1 1
2 1
3 2
4 3
5 5
第N年的兔子 其实 是第n-1年+上n-2年的兔子生的兔子
所以 就是f(n)=f(n-1)+f(n-2)
考虑到可能是面试,就没有用递归,这么写 复杂度会小点,当然 Dictionary也可以用int[]
- C# code
static Dictionary<int, int> dic = new Dictionary<int, int>(); private static int Test(int n) { if(!dic.ContainsKey(1)) { dic.Add(1, 1); } if (!dic.ContainsKey(2)) { dic.Add(2, 1); } for (int i = 3; i <= n; i++) { if (!dic.ContainsKey(i)) { dic[i] = dic[i - 1] + dic[i - 2]; } } return dic[n]; }