一道PHP面試題,感覺自己寫的不是很優(yōu)雅,想看看大家怎么寫的

//PHP不會JS編寫,這種屬于算法題
function countSheep(X = 1,N = 2){

var $five = [X,0,0,0,0];
while( N-- ){
  $five.unshift($five[1]+$five[3]);//將第四年和第二年的羊生下的羊羔放入數(shù)組
}
var count = $five[0]+$five[1]+$five[2]+$five[3]+$five[4];//計算0-4歲的羊的只數(shù)

}
//X表示初始羊的個數(shù),N表示第n年后羊的數(shù)量

一個遞推就可以了，php我不熟，Ruby的代碼如下：

// 初始化0歲的羊有1只，其它歲的羊有0只
y0 = [1]
y1 = [0]
y2 = [0]
y3 = [0]
y4 = [0]
y5 = [0]

# 暫定n = 20年
n = 20
(1..n).each do |i|
  // 2歲羊和5歲羊產(chǎn)仔tmp只
  tmp = y2[i-1].to_i + y5[i-1].to_i

  // 羊依次漲1歲
  y5[i] = y4[i-1].to_i
  y4[i] = y3[i-1].to_i
  y3[i] = y2[i-1].to_i
  y2[i] = y1[i-1].to_i
  y1[i] = y0[i-1].to_i
  
  // 0歲羊
  y0[i] = tmp
end

p y0[n] + y1[n] + y2[n] + y3[n] + y4[n] + y5[n]

如果羊M歲才死，那么就需要開個數(shù)組，做兩層循環(huán)來地推。

數(shù)學(xué)思維

//年數(shù)
$n = 30;
//已知1，第2年2只，第4年4只， 第6年開始死亡。。 從第6年開始用程序計算
$count = [4, 2, 1];
for ($i = 6; $i <= $n; $i += 2) {
    //上一季羊的數(shù)量除2得到媽媽數(shù)，上上季羊除2得到上上季媽媽數(shù)，兩者之差為上一紀(jì)要淘汰的數(shù)量，剩下的乘2便得出本季媽媽和女兒的總數(shù)
    array_unshift($count,($count[0] - ($count[0] / 2 - $count[1] / 2)) * 2);
}
//每兩年為一季，每季羊數(shù)量
sort($count);
var_dump($count);

0 => int 1
1 => int 2
2 => int 4
3 => int 6
4 => int 10
5 => int 16
6 => int 26
7 => int 42
8 => int 68
9 => int 110
10 => int 178
11 => int 288
12 => int 466
13 => int 754
14 => int 1220
15 => int 1974

直觀的遞歸解法

function born($n) {
  if ($n < 0) return 0;
  if ($n == 0) return 1;
  return born($n-2)
       + born($n-4);
}
function sheep($n) {
  if ($n < 0) return 0;
  return sheep($n-1) // 去年的羊
       + born($n)    // 加上今年生的
       - born($n-5); // 減去今年5歲羊死的
}

第一種：

function born($n){
    $all=[0];
    for($i=0;$i<$n;$i++){
      $c=count($all);
      for($j=0;$j<$c;$j++){
          $all[$j]=$age=$all[$j]+1;
          if($age==2||$age==4){
            $all[]=0;
          }
      }
    }
    return $all;
}
//返回的數(shù)據(jù)中，把大于等于5的去掉就是了。

第二種：(在 @雪之祈舞 的回答上作了一點修改)

function sheep($n){
    $y=[
        0=>1,
        1=>0,
        2=>0,
        3=>0,
        4=>0,
        5=>0,
    ];
    for($i=0;$i<$n;$i++){
        for($j=5;$j>0;$j--){
            $y[$j]=$y[$j-1];
        }
        $born=$y[2]+$y[4];
        $y[0]=$born;
    }
    return $y;
}
//unset($y[5]) 再把各項加起來就可以了。

兩種方法得到的結(jié)果是一樣的，但第一種方法不斷往數(shù)組里添加剛出生的羊，數(shù)組長度越來越大，我測試了一下，大于 50 的時候就會出現(xiàn)內(nèi)存不足的情況了。
而第二種方法則完全不必?fù)?dān)憂。

記錄每一只羊的狀態(tài)
function sheep($n){

$sheep[0]=0;
$count[0]=1;
for($i=1; $i<$n; $i++){
    $count=0;
    for($j=0; $j<$count[i]; $j++){
        if($sheep[i]!=-1){
            $sheep[i]++;
            if($sheep[i]==2 || $sheep[i]==2 ) $sheep.append(0);
            if($sheep[i]>=5) $sheep[i]=-1;
            $count++;
        }
    }

    $count[i+1]=$count;
}
return $count[$n];

}

記錄各個年齡的羊數(shù)
function sheep($n){

$y=[0=>1,1=>0,2=>0,3=>0,4=>0,5=>0];
for($i=1; $i<$n; $i++){
    for($j=5;$j>0; $j--){
        $y[$j]=$y[$j-1];
    }
    $new=$y[2]+$[4];
}
return $y;

}

題主希望優(yōu)雅寫法，所以代碼如下：

/**
 * [countSheep 數(shù)羊]
 * @param $n [年份]
 * @return [羊的數(shù)量]
 */
function countSheep($n)
{
    static $count = 0; // 初始化羊的數(shù)量

    for ($i=0;$i<=5 && $i<=$n;$i++) { // 保證一只羊的壽命小于等于5，不足5時小于等于$n
        if ($i==0)
            $count++;
        elseif ($i==2 || $i==4)
            countSheep($n-$i); // 遞歸調(diào)用，傳入新的年份
        elseif ($i==5)
            $count--;
    }

    return $count;
}

<?php

class increase {
    // 小羊從0歲開始，那么2歲就是第3年，4歲是第5年，死亡是在第6年
    function __construct() {
        $this->terminal = 6;
        $this->give_birth = array(2,4);
        $this->sheeps = array(0);
    }

    function run($year) {
        for ($i = 1; $i <= $year; $i++) {
            foreach ($this->sheeps as $key=>$age) {
                if (in_array($age, $this->give_birth)) {
                    $this->multiply($key);
                }
                if ($age == $this->terminal) {
                    $this->die($key);
                }
                $this->sheeps[$key] += 1;
            }
        }
        return $this->sheeps;
    }

    function multiply($key) {
        $this->sheeps[] = 0; //繁殖了一只羊
    }

    function die($sheep) {
        unset($this->sheeps[$sheep]); //一只羊的死亡
    }

}

$survival = new increase();
$exists = $survival->run(7);
echo count($exists);

function sheep($n, $sum = 1)
{
    $arr = [
        0 => 0,
        1 => 0,
        2 => 1,
        3 => 0,
        4 => 1,
        5 => 0,
    ];
    for ($i = 1; $i <= $n; $i++) {
        $currentIndex = $i % 6; // 取余數(shù)
        if ($arr[$currentIndex] == 1) {
            $sum++;
            $sum = sheep($n - $i, $sum);
        } elseif ($currentIndex == 5) {
            $sum--;
        }
    }
    return $sum;
}

$plus = [2,4];//新羊出生
$die = 5;//舊羊死亡

$n = 50;

$sheeps = [];
$sheeps[1] = 0;
for($i = 1; $i <= $n; $i++)
{
    foreach($sheeps as $index => $value)
    {
        $sheeps[$index]++;
        if($sheeps[$index] == $die)
        {
            unset($sheeps[$index]);
            continue;
        }
        if(in_array($sheeps[$index],$plus))
        {
            $sheeps[] = 0;
        }
    }
}
echo(count($sheeps));//n=50,242786