算法面试题,C# 算兔子的算法　要求用递归，面试题

有一网友,在百度知道寻问一道面试题,题目如下:
一对小兔子一年后长成大兔子；一对大兔子每半年生一对小兔子。大兔子的繁殖期为4年，兔子的寿命是6年。假定第一年年初投放了一对小兔子，试编程计算，第n年末总共会有多少对兔子。n由键盘输入。（用递归哦，谢谢！）
----------------------------------------------------------
于是我先写出了解题思路,如下:
/* 小兔子 大兔子 生育 *1年 1 *2年 0 1(1岁) *2.5 1(第二代) 1(1.5岁) 第一代1次 *3 1(第二代0.5岁)+1(第三代) 1(2岁) 第一代2次 *3.5 1(第三代0.5岁)+1(第四代) 1(第一代2.5岁)+1(第二代1岁) 第一代3次 *4 1(第四代0.5岁)+2(第五代) 1(第一代3岁)+1(第二代1.5岁)+1(第三代1岁) 第一代4次,第二代1次 *4.5 2(第五代0.5岁)+2(第六代) 1(第一代3.5岁)+1(第二代2岁)+1(第三代1.5)+1(第四代1岁) 第一代5次第二代2次,第三代1次 *5 1(第一代4岁)6次 *5.5 1(第一代4.5)7次 *6 1(第一代5岁)8次,已繁殖了4年 *6.5 1(第一代5.5岁) * * */
我数学不太好,这是用笨方法列出来的,找出来了其规律及逻辑要点。于是我编写出了下述代码。
using System; using System.Collections.Generic; namespace zuo_TestProject{ #region "主程序" public class TestMain{ static void Main(){ Tag: Console.Write("请输入要测试的年数："); string Sinput = Console.ReadLine(); double dyear; if(double.TryParse(Sinput,out dyear)){ Farms fs = new Farms(); int count = fs.GetNum(dyear); Console.WriteLine("\r\n{0}年以后兔子的对数为：{1}",dyear,count); } else{ Console.WriteLine("\r\n您输入的有误\r\n"); goto Tag; } } } #endregion #region "兔子养殖场" public class Rabbit //兔子 { private int rabbit_Type; //第几代 private double age; //年龄 public Rabbit(int dai){ this.rabbit_Type = dai; //根据递归次数设置是第几代兔子，同代的兔子寿命相同，生育次数也相同 } public int RabbitType{ //供外部查询是第几代兔子 get{ return this.rabbit_Type; } } public double Age{ //兔子年龄 get{ return this.age; } set{ this.age = value; } } } public class Farms //养殖场 { private int era = 1; //第1代开始 private List rlst; //用于存放兔子的列表 private double startTime; //起始时间,默认0 public Farms(){ rlst = new List(); rlst.Add(new Rabbit(this.era)); //养殖场初始只有第一代兔子 } public int GetNum(double nYear){ //返回N年之后有多少对兔子 if(nYear-this.startTime<=0.0){ //到达指定年限 return rlst.Count; //返回有多少对兔子 } Console.WriteLine("当前年份:{0}",this.startTime); List nrs = rlst.FindAll(r=>r.Age>=1.5&&r.Age<5.5); //返回满足可生育的兔子 if(nrs.Count>0){ //如果有符合生育条件的兔子 this.era++; //代数自增 } for(int i=0;ir.Age>=6.0);//等于6岁或超过6岁者,自然而然死! Console.WriteLine("========当前生亡数量:{0}",killNum); Console.WriteLine("========当前存活数量:{0}",rlst.Count); this.startTime += 0.5; //年自增 foreach(Rabbit rt in rlst){ rt.Age+=0.5; //年龄增加半年 } return GetNum(nYear); //递归调用,返回结果值 } } #endregion }

这个小题挺有意思，一开始编的时候竟然盲目的想用几个变量就解决此题，当时还一根筋的用了个数学公式，结果仔细一想不对，于是又用笨方法推理出来了整个过程，所以才编写出来了这段代码，特分享给众位朋友，其实我也想知道还有没有更简洁的写法，由于我水平有限，只能想到这个了，分享的同时，也想换大家点更优秀的代码，看看有没有更加优质的代码能写出替代的小程序。恭候大家跟贴优秀代码、优秀算法。
下面是程序运行测试的结果：
请输入要测试的年数：7 当前年份:0 =======当前生亡数量:0 =======当前存活数量:1 当前年份:0.5 =======当前生亡数量:0 =======当前存活数量:1 当前年份:1 =======当前生亡数量:0 =======当前存活数量:1 当前年份:1.5 -----谁生了：第1代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:2 当前年份:2 -----谁生了：第1代，当前寿命2 =======当前生亡数量:0 =======当前存活数量:3 当前年份:2.5 -----谁生了：第1代，当前寿命2.5 =======当前生亡数量:0 =======当前存活数量:4 当前年份:3 -----谁生了：第1代，当前寿命3 -----谁生了：第2代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:6 当前年份:3.5 -----谁生了：第1代，当前寿命3.5 -----谁生了：第2代，当前寿命2 -----谁生了：第3代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:9 当前年份:4 -----谁生了：第1代，当前寿命4 -----谁生了：第2代，当前寿命2.5 -----谁生了：第3代，当前寿命2 -----谁生了：第4代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:13 当前年份:4.5 -----谁生了：第1代，当前寿命4.5 -----谁生了：第2代，当前寿命3 -----谁生了：第3代，当前寿命2.5 -----谁生了：第4代，当前寿命2 -----谁生了：第5代，当前寿命1.5 -----谁生了：第5代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:19 当前年份:5 -----谁生了：第1代，当前寿命5 -----谁生了：第2代，当前寿命3.5 -----谁生了：第3代，当前寿命3 -----谁生了：第4代，当前寿命2.5 -----谁生了：第5代，当前寿命2 -----谁生了：第5代，当前寿命2 -----谁生了：第6代，当前寿命1.5 -----谁生了：第6代，当前寿命1.5 -----谁生了：第6代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:28 当前年份:5.5 -----谁生了：第2代，当前寿命4 -----谁生了：第3代，当前寿命3.5 -----谁生了：第4代，当前寿命3 -----谁生了：第5代，当前寿命2.5 -----谁生了：第5代，当前寿命2.5 -----谁生了：第6代，当前寿命2 -----谁生了：第6代，当前寿命2 -----谁生了：第6代，当前寿命2 -----谁生了：第7代，当前寿命1.5 -----谁生了：第7代，当前寿命1.5 -----谁生了：第7代，当前寿命1.5 -----谁生了：第7代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:40 当前年份:6 -----谁生了：第2代，当前寿命4.5 -----谁生了：第3代，当前寿命4 -----谁生了：第4代，当前寿命3.5 -----谁生了：第5代，当前寿命3 -----谁生了：第5代，当前寿命3 -----谁生了：第6代，当前寿命2.5 -----谁生了：第6代，当前寿命2.5 -----谁生了：第6代，当前寿命2.5 -----谁生了：第7代，当前寿命2 -----谁生了：第7代，当前寿命2 -----谁生了：第7代，当前寿命2 -----谁生了：第7代，当前寿命2 -----谁生了：第8代，当前寿命1.5 -----谁生了：第8代，当前寿命1.5 -----谁生了：第8代，当前寿命1.5 -----谁生了：第8代，当前寿命1.5 -----谁生了：第8代，当前寿命1.5 -----谁生了：第8代，当前寿命1.5 =======当前生亡数量:1 =======当前存活数量:57 当前年份:6.5 -----谁生了：第2代，当前寿命5 -----谁生了：第3代，当前寿命4.5 -----谁生了：第4代，当前寿命4 -----谁生了：第5代，当前寿命3.5 -----谁生了：第5代，当前寿命3.5 -----谁生了：第6代，当前寿命3 -----谁生了：第6代，当前寿命3 -----谁生了：第6代，当前寿命3 -----谁生了：第7代，当前寿命2.5 -----谁生了：第7代，当前寿命2.5 -----谁生了：第7代，当前寿命2.5 -----谁生了：第7代，当前寿命2.5 -----谁生了：第8代，当前寿命2 -----谁生了：第8代，当前寿命2 -----谁生了：第8代，当前寿命2 -----谁生了：第8代，当前寿命2 -----谁生了：第8代，当前寿命2 -----谁生了：第8代，当前寿命2 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 -----谁生了：第9代，当前寿命1.5 =======当前生亡数量:0 =======当前存活数量:84
年以后兔子的对数为：84

Tags:  如何设计递归算法 递归算法 华为面试题算什么 百度算法面试题 算法面试题

延伸阅读

• 2011-9-19-- 算法题,算法100题26
• 2011-9-18-- 算法题,算法100题54
• 2011-9-19-- 算法面试题,轻言“算法”太匆匆——也谈“兔子”面试题
• 2010-12-15-- 递归算法,谁能答对这道题?如有兴趣,请留下算法,呵呵～(续,递归算法)
• 2010-12-15-- 编码生成器,.net递归生成树的一个程序，没有父节点字段，根据编码进行递归
• 2011-1-4-- 优秀的程序员,优秀的程序员是懂指针和递归的
• 2011-6-10-- 递归算法,RIA Service中对于递归实体类型处理的问题及解决方案
• 2011-4-20-- 算法题,算法题——第1000000个数是多少？
• 2011-3-21-- 全排列非递归算法,二路归并算法非递归C实现
• 2011-2-15-- 递归算法,反转字符.递归算法