PHP面试题目

29个成员

关于生牛牛的问题

发表于 2015-12-18 1323 次查看

一只母牛,第二年底生一只母牛和一只公牛,第三年底生一只母牛 ,第五年开始母牛会死。公牛也只能活四年。请问一个农场开始只有一只刚出生的母牛,N年后一共有多少只牛。

请写一个函数输出结果

12回复
  • 2楼 朕扮皇 2015-12-19

    <?php
     //母牛生出来的数目
    function getmu($num){
        if($num==1) return 1;
        $a=0;
        $b=1;
        $mu = 0;
        for($i=2;$i<=$num;$i++){
            $t=$a+$b;
            $a=$b;
            $b=$t;
            $mu += $t;
        }
        return $mu+1;
    }
    //公牛生出来的数目
    function getgong($num){
        if($num==1) return 0;
        if($num==2) return 1;
        $a=0;
        $b=1;
        $gong = 0;
        for($i=3;$i<=$num;$i++){
            $t=$a+$b;
            $a=$b;
            $b=$t;
            $gong += $t;
        }
        return $gong+1;
    }

    //母牛公牛死去的数目
    function lose($num){
        if($num<=4) return 0;
        if($num==5) return 2;
        $a=0;
        $b=1;
        $mu = 0;
        for($i=6;$i<=$num;$i++){
            $t=$a+$b;
            $a=$b;
            $b=$t;
            $mu += $t;
        }
        return ($mu+1)*2;
    }

    function year($num){
        return getmu($num)+getgong($num)-lose($num);
    }
    echo year(6); 

    • 福娃大师兄 2015-12-20
      你算法错了,第五年的时候你多减了1,公牛只能活四年,第一年开始的时候只有母牛,而第2年才出现公牛,也就是说,第5年时候只有第一年的那只母牛会挂掉,而第6年,第一只公牛才会死,因为这只公牛是第2年出现的~~~
  • 3楼 福娃大师兄 2015-12-20

    楼上好复杂。。。解释下思路F代表母,M代表公,F1代表一年母,F2代表两年母,M1代表一年公,以此类推,如下:

    第一年:F1  1

    第二年:F2+F1+M1  3

    第三年:F3+F2+F1+M2+M1+F1 6

    第四年 F4+F3+F2+F1+M1+M3+M2+F1+F2+F1+M1 11

    第五年: F4+F3+F2+F1+M1+M2+M4+M3+F2+F1+M1+F1+F3+F2+F1+M1+M2+F1 18

    第六年(递归开始):F4+F3+F2+F1+M1+M2+M3+M4+F3+F2+F1+M1+M2+F1+F1+F2+F1+M1+F4+F3+F1+F2+F1+M1+M2+M3+F2+F1+M1 29

    第七年:......47

    第八年:.......

    关于这类有变数的递归问题,因为第一只母牛开始死亡出现在第5年,第1只公牛死亡出现在第6年(因为第一支公牛是第一支母牛的娃),所以规律会从第6年开始,第六年以后公母死亡或者增加都会逐渐递归形成,通过以上规律可以看出从第六年开始 29 = 11 + 18;第七年47 = 18 + 29,那么第八年肯定会是29 + 47 = 76,因此大于5年以上的递归规律就出来了 F(i) = F(i-1) + F(i-2),程序如下:

    <?php

    function cowsBorn($i) {
        switch($i) {
            case 1:return 1;break;
            case 2:return 3;break;
            case 3:return 6;break;
            case 4:return 11;break;
            case 5:return 18;break;
            default:return cowsBorn($i-1) + cowsBorn($i-2);break;
        }
    }
    echo cowsBorn(14);
    ?>

     

    • 福娃 2015-12-21
      方法虽好,但可拓展性不好,一但改变生育规则,就得重写计算规则了。
    • 福娃大师兄 2015-12-21
      你这不是废话吗,你换题了,不论你什么样的算法都要重新写,我就想知道你能用一个函数把dt写出来?你能用一个递归规律解决所有的问题?你没救了。。。所谓的扩展性指的是,如果我数量超出一定范围就失效,或者小于一定范围就失效,我还第一次听说,扩展性指的是你题都换了,我他奶奶的这个函数还有用的,你可真行,想了半天终于找了这么一个'理由',我不清楚你有没有做过递归的数学题,你自己去看看吧,先别去研究程序,换了条件的递归,公式还一样吗?不用说递归,你换了条件,连等比数列都要换,比如,第一年2,第2年5,第三年6,第四年开始以第二年为等比递推,第五年以第三年等比。。。就这么简单的规律你一旦换数字,你还是要重写,因为第一年没规律。。。
  • 4楼 福娃 2015-12-21

    网上抄的:

    1. function cowrecursion($i)  
    2. {  
    3.     if ($i == 1) //如果是第一年,则1头牛。   
    4.     {  
    5.         return 1;  
    6.     }  
    7.     elseif ($i == 2)  
    8.     {  
    9.         return 2 + cowrecursion(1); //第一母牛和儿子们+第二母牛第一年        
    10.     }  
    11.     elseif ($i == 3)  
    12.     {  
    13.         return 2 + cowrecursion(2) +  cowrecursion(1); //第一母牛和儿子们+第二母牛第二年 +第三母牛第一年  
    14.     }  
    15.     elseif ($i ==4)  
    16.     {  
    17.         return 2 + cowrecursion(3) +  cowrecursion(2);  //第一母牛和儿子们+第二母牛第三年 +第三母牛第二年  
    18.     }  
    19.     // elseif ($i == 5)  
    20.     // {          
    21.         // return cowrecursion(4) +  cowrecursion(3);    //第一母牛死了。公牛也死了。第二母牛第四年 +第三母牛第三年          
    22.     // }  
    23.     elseif ($i >= 5)  
    24.     {  
    25.         return cowrecursion($i-1) +  cowrecursion($i-2);    
    26.     }  
    27. }  
    28.   
    29.   
    30. //非递归方式实现  
    31. function cow_norecursion($i)  
    32. {  
    33.     //实现思路,用数组来存储,value的值表示年限。循环加1.  
    34.     $cows = array(1);  //第一年,1头母牛。  
    35.     $cowsmale = array();  //用于存储公牛  
    36.       
    37.     for ($j=0;$j<$i;$j++)  //循环多少年  
    38.     {  
    39.         //循环母牛   
    40.   
    41.   
    42.         $cows_copy = $cows;  
    43.         foreach ($cows as $key => $value)  
    44.         {         
    45.             switch($cows_copy[$key])  
    46.             {  
    47.                 case 1:               
    48.                     break;  
    49.                 case 2:  
    50.                     $cows_copy[] = 1;  
    51.                     $cowsmale[] = 1;  
    52.                     break;  
    53.                 case 3:  
    54.                     $cows_copy[] = 1;  
    55.                     break;  
    56.                 case 4:  
    57.                   
    58.                     break;  
    59.                 case 5:  
    60.                     unset($cows_copy[$key]);  
    61.                     break;  
    62.                   
    63.             }  
    64.           
    65.         }  
    66.       
    67.               
    68.         $cows = $cows_copy;  
    69.           
    70.         array_walk($cowsfunction(&$value$index){  
    71.                if ($value > 0) $value++;  
    72.          });  
    73.           
    74.           
    75.           
    76.         $cowsmale_copy = $cowsmale;  
    77.         //循环公牛  
    78.         foreach ($cowsmale as $d => $value)  
    79.         {             
    80.             $cowsmale_copy[$d]++;  
    81.             if ($cowsmale_copy[$d] == 5)    //到第四年就死了  
    82.             {  
    83.                 unset($cowsmale_copy[$d]);  
    84.             }             
    85.               
    86.         }     
    87.          $cowsmale = $cowsmale_copy;          
    88.     }  
    89.   
    90.     return count($cows) + count($cowsmale);   
    91. }  
    92. echo "<br />list  totol--->".cow_norecursion(26);  
    93.   
    94. echo "<br />totol  recursion--->".cowrecursion(26);  
    • 福娃大师兄 2015-12-21
      你自己为什么不推算一下呢,你带入一下试一试,这个是错的,第五年,他的错误仍然出在推算结果上面,第五年: F4 F3 F2 F1 M1 M2 M4 M3 F2 F1 M1 F1 F3 F2 F1 M1 M2 F1 也就是说是18只,这个和你楼下犯错误是一样的就是,它假设了公牛和母牛死期一致
  • 5楼 福娃 2015-12-21

    $num_gong=0; //最初公牛数
    $num_mu=1; //最初母牛数
    function niu($n){
         global $num_gong,$num_mu;
            $mu=array(0,1,1,0,-1); //五年内母牛每年是否有增加,负值为死了
         $gong=array(0,1,0,0,-1);  //五年内公牛每年是否有增加
         $j=0;
         for($i=0;$i < $n;$i++){
               $num_mu+=$mu[$j];
               $num_gong+=$gong[$j];
               if($mu[$j]==1 && $n-$i>1) niu($n-$i); //如果生了一只母的, 则$n-$i以剩余年数进行回调
               if(++$j==5) $j=0; //以母牛生命周期5年为循环
         }
    }
    niu(6);
    echo "<br>母牛数:{$num_mu} <br>公牛数:{$num_gong} <br>一共:".($num_gong+$num_mu);

    • 福娃大师兄 2015-12-21
      你自己好好再算一下,你的第5年错了...不要参考那个网上抄的算法,那个是错的,你要自己推算一下
    • 福娃大师兄 2015-12-21
      你可以参考下你楼下的,你这样打包递归还是会出现错误,循环次数越多偏差就会越大,你切入点不对,另外你还最重要的是要根据推算结果写出递归规律,而不是根据别人的算法
    • 福娃大师兄 2015-12-21
      你居然把你最先写的那个回复删了,哎~~~你这么一个问题你更改了多少次啊
发表回复
你还没有登录,请先登录注册

加入我们吧,一起学习QQ群516033298