黑马程序员技术交流社区

标题: JAVA算法练习-No.1 [打印本页]
作者: 25343215    时间: 2013-12-18 10:53
标题: JAVA算法练习-No.1
本帖最后由 25343215 于 2013-12-18 17:09 编辑

       题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问在20个月里的兔子总数为多少？ (请用递归实现)
       在企业面试中，算法常常都是重要考点！所以在学习Java过程中，要抽出时间多做做多看看算法题目。
       在代码中请提供题目de分析!

           我已经在第12楼公布我做的答案，及代码分析。欢迎一起学习！
作者: Y_Y    时间: 2013-12-18 11:21
public class exp2{
        public static void main(String args[]){
                int i=0;
                for(i=1;i<=20;i++)
                        System.out.println(f(i));
        }
        public static int f(int x)
        {
                if(x==1 || x==2)
                        return 2;
                else
                        return f(x-1)+f(x-2);
        }
}
作者: 25343215    时间: 2013-12-18 11:28
Y_Y 发表于 2013-12-18 11:21
public class exp2{
        public static void main(String args[]){
                int i=0;

递归分析呢？
作者: ily521125    时间: 2013-12-18 12:50
  1. class Demo
  2. {
  3. public static void main(String[] args)
  4. {
  5. System.out.println("第1个月兔子的对数：1");
  6. System.out.println("第2个月兔子的对数：1");
  7. int f1=1,f2=1,f,M=20,s=0;
  8. for (int i=3;i<=M ;i++ )
  9. {
  10. f=f2;
  11. f2=f1+f2;
  12. f1=f;
  13. s+=f2;
  14. System.out.println("第"+i+"个月的兔子的对数:"+f2);
  15. }
  16. System.out.println("20个月兔子的总数为:"+s);
  17. }
  18. }
复制代码

作者: 歌神鸡比    时间: 2013-12-18 14:58
这个我不会啊
作者: 25343215    时间: 2013-12-18 15:03
ily521125 发表于 2013-12-18 12:50

{:soso_e179:}
作者: 25343215    时间: 2013-12-18 15:05
歌神鸡比 发表于 2013-12-18 14:58
这个我不会啊

一步步学喽。方丈高楼，平地起。
作者: 風諾    时间: 2013-12-18 15:20
本帖最后由 風諾 于 2013-12-18 15:24 编辑

斐波那契数列吗？
为啥我分析出来这样？感觉不是啊。
         * 第n个月兔子总数f(n)与当月成熟兔子和小兔子数关系用公式表示：
         * f(n) = 当月成熟兔子数 + 当月小兔子数
         * f(1) = 1 + 0
         * f(2) = 1 + 0
         * f(3) = 1 + 1                3月：第一对兔子生小兔子
         * f(4) = 1 + 2                4月：第一对兔子生小兔子
         * f(5) = 1 + 3                5月：第一对兔子生小兔子
         * f(6) = 2 + 4                6月：3月新出生的小兔子成熟，开始生小兔子
         * f(7) = 3 + 6                7月：4月新出生的小兔子成熟，开始生小兔子
         * f(8) = 4 + 9                8月：5月新出生的小兔子成熟
         * f(9) = 6 + 13        9月：6月新出生的小兔子成熟
         * f(10)= 9 + 19        ...
         * f(11)= 13+ 28
作者: 25343215    时间: 2013-12-18 15:29
風諾 发表于 2013-12-18 15:20
斐波那契数列吗？
为啥我分析出来这样？感觉不是啊。
         * 第n个月兔子总数f(n)与当月成熟兔子和小兔 ...

最开始我也是和你这样分析的。但答案是：兔子的规律为数列2,2,4,6,10,16,....  

作者: 風諾    时间: 2013-12-18 15:55
25343215 发表于 2013-12-18 15:29
最开始我也是和你这样分析的。但答案是：兔子的规律为数列2,2,4,6,10,16,....  

...

没感觉那里分析错了啊
可不可以讲讲
作者: hurryup    时间: 2013-12-18 16:05
我也是理解为每隔三个月就有一对兔子长大并且有生了一对小兔子，这种情况怎么设计呢?求解!
作者: 25343215    时间: 2013-12-18 17:08
  1. package cn.itcast;
  2. /**
  3. * 【程序1】  
  4. * 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，
  5. * 小兔子长到第3个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？  
  6. *
  7. * 分析：        第一个月        1 对
  8. *                         第二个月  1 对
  9. *                         第三个月  2 对
  10. *                         第四个月  3 对
  11. *                         第五个月  5 对
  12. *                         第六个月  8 对
  13. *                         第七个月  13 对
  14. *                 规律：       
  15. *                         从第三个月开始，都是后两个月相加
  16. *                         f(n)=f(n-1)+ f(n-2)
  17. *                        
  18. *                 出口：1月份、2月份 ，为已知的值 1对
  19. *                
  20. * @author Administrator
  21. *
  22. */
  23. public class Test {
  24.         public static void main(String[] args) {

  26.                 for (int i = 1; i <=20; i++) {
  27.                         System.out.println("第"+i+"个月兔子数为："+f(i)+"个");
  28.                 }
  29.         }

  31.         public static int f(int n){
  32.                 if(n==1||n==2){
  33.                         return 2;
  34.                 }else{
  35.                         return f(n-1)+f(n-2);
  36.                 }
  37.         }
  38. }
复制代码


结果：
第1个月兔子数为：2个
第2个月兔子数为：2个
第3个月兔子数为：4个
第4个月兔子数为：6个
第5个月兔子数为：10个
第6个月兔子数为：16个
第7个月兔子数为：26个
第8个月兔子数为：42个
第9个月兔子数为：68个
第10个月兔子数为：110个
第11个月兔子数为：178个
第12个月兔子数为：288个
第13个月兔子数为：466个
第14个月兔子数为：754个
第15个月兔子数为：1220个
第16个月兔子数为：1974个
第17个月兔子数为：3194个
第18个月兔子数为：5168个
第19个月兔子数为：8362个
第20个月兔子数为：13530个
作者: 25343215    时间: 2013-12-18 17:10
風諾 发表于 2013-12-18 15:55
没感觉那里分析错了啊
可不可以讲讲

12楼。我把我的想法，写上面了。
作者: 25343215    时间: 2013-12-18 17:11
hurryup 发表于 2013-12-18 16:05
我也是理解为每隔三个月就有一对兔子长大并且有生了一对小兔子，这种情况怎么设计呢?求解! ...

12楼。我把我的想法，写上面了。欢迎一起学习
作者: 風諾    时间: 2013-12-18 17:43
hurryup 发表于 2013-12-18 16:05
我也是理解为每隔三个月就有一对兔子长大并且有生了一对小兔子，这种情况怎么设计呢?求解! ...

我觉得貌似一开始题目写的是小兔子第四个月开始生兔子，现在看好像变了
要是按照原来的这样貌似可以的：
  1. public static int getNumber(int month) {
  2.                 int sum = 0;
  3.                 switch (month) {
  4.                         case 0:
  5.                         case 1:
  6.                         case 2:
  7.                                 sum = 1;
  8.                                 break;
  9.                                
  10.                         default:
  11.                                 sum = getNumber(month - 1) + getNumber(month - 3);
  12.                                 break;
  13.                 }
  14.                 return sum;
  15.         }
复制代码
作者: 25343215    时间: 2013-12-18 17:49
風諾 发表于 2013-12-18 17:43
我觉得貌似一开始题目写的是小兔子第四个月开始生兔子，现在看好像变了
要是按照原来的这样貌似可以的：
...

嗯。。4变3了。

我开始做4也没做出来。然后问了一下，应该是每三月。才行。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2