一道PHP面试题,感觉自己写的不是很优雅,想看看大家怎么写的

Question

小羊能活5岁，它在2岁，4岁的时候都会生一只小羊，5岁的时候就死亡了。
问：现在有一只刚出生的小羊(0岁),n年后有多少只羊？

Answer 1

第一种：

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;
}
//返回的数据中，把大于等于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]) 再把各项加起来就可以了。

两种方法得到的结果是一样的，但第一种方法不断往数组里添加刚出生的羊，数组长度越来越大，我测试了一下，大于 50 的时候就会出现内存不足的情况了。
而第二种方法则完全不必担忧。

Answer 2

一个递推就可以了，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岁羊产仔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岁才死，那么就需要开个数组，做两层循环来地推。

Answer 3

$y=[0=>1,1=>0,2=>0,3=>0,4=>0,5=>0];
$n =20;
for($i=0;$i<=$n;$i++)
{
    $temp = ($y[2]+$y[4])*2;
    $y[5]=$y[4];
    $y[4]=$y[3];
    $y[3]=$y[2];
    $y[2]=$y[1];
    $y[1]=$y[0];
    $y[0]=$temp;
}
print_r($y);
print_r(array_sum($y));

Answer 4

$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

Answer 5

<?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);

Answer 6

题主希望优雅写法，所以代码如下：

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

    for ($i=0;$i<=5 && $i<=$n;$i++) { // 保证一只羊的寿命小于等于5，不足5时小于等于$n
        if ($i==0)
            $count++;
        elseif ($i==2 || $i==4)
            countSheep($n-$i); // 递归调用，传入新的年份
        elseif ($i==5)
            $count--;
    }

    return $count;
}

Answer 7

数学思维

//年数
$n = 30;
//已知1，第2年2只，第4年4只， 第6年开始死亡。。 从第6年开始用程序计算
$count = [4, 2, 1];
for ($i = 6; $i <= $n; $i += 2) {
    //上一季羊的数量除2得到妈妈数，上上季羊除2得到上上季妈妈数，两者之差为上一纪要淘汰的数量，剩下的乘2便得出本季妈妈和女儿的总数
    array_unshift($count,($count[0] - ($count[0] / 2 - $count[1] / 2)) * 2);
}
//每两年为一季，每季羊数量
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

Answer 8

有问题 改进中

Answer 9

直观的递归解法

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岁羊死的
}

Answer 10

记录每一只羊的状态
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];

}

记录各个年龄的羊数
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;

}

Answer 11

//PHP不会JS编写,这种属于算法题
function countSheep(X = 1,N = 2){

var $five = [X,0,0,0,0];
while( N-- ){
  $five.unshift($five[1]+$five[3]);//将第四年和第二年的羊生下的羊羔放入数组
}
var count = $five[0]+$five[1]+$five[2]+$five[3]+$five[4];//计算0-4岁的羊的只数

}
//X表示初始羊的个数,N表示第n年后羊的数量

Answer 12

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; // 取余数
        if ($arr[$currentIndex] == 1) {
            $sum++;
            $sum = sheep($n - $i, $sum);
        } elseif ($currentIndex == 5) {
            $sum--;
        }
    }
    return $sum;
}

Answer 13

这样没什么问题吧

function born($year){
    $sheep[]=array("age"=>0);
    while($year>0){
        foreach ($sheep as $k => $v) {
            if($v['age']==5){
                unset($sheep[$k]);
            }elseif($v['age']==2||$v['age']==4){
                $sheep[]=array("age"=>0);
            }
            $sheep[$k]['age']++;
        }
        $year--;
    }
    return count($sheep);
}

Answer 14

golang语言写的：

var sum = 0

func GetSheep(n int) {

    max := 0
    if n >= 5 {
        max = 5
    } else {
        max = n
    }

    //在羊活的这5年（最大）期间，羊再次生羊，一样的传入羊剩余的年份
    for i := 0; i <= max; i++ {
        if i == 2 || i == 4 {
            GetSheep(n - i)
        }
    }

    //这只羊活的剩余年份小于5，说明这只羊能存活，记录下来
    if n <= 5 {
        sum++
    }

}

func main() {
    //这只羊活的剩余年份
    GetSheep(20)
    fmt.Println(sum)
}

Answer 15

    $n = 4;
    $sheeps= [1,0,0,0,0,0];
    for($i = 1;$i<=$n;$i++){
        $sheeps = [
                $sheeps[1] + $sheeps[3], // 0岁的羊
                $sheeps[0], // 1岁的羊
                $sheeps[1], // 2岁的羊
                $sheeps[2], // 3岁的羊
                $sheeps[3], // 4岁的羊
                0    // 5岁的羊
        ];
    }
    echo array_sum($sheeps);

Answer 16

好像没人发这个。递归的方式，适合小数据量计算。

function getNum($n){
    if (in_array($n,[0,1,2,4]))
        return $n;
    elseif($n == 3)
        return 2;
    return ($n >= 5 ? 0 : 1) + getNum($n - 4) + getNum($n - 2);
}

第1年：1
第2年：2
第3年：2
第4年：4
第5年：3
第6年：6
第7年：5
第8年：10
第9年：8
第10年：16
第11年：13
第12年：26
第13年：21
第14年：42
第15年：34
第16年：68
第17年：55
第18年：110
第19年：89
第20年：178

Answer 17

function fn($x){
    $arr=[0=>0,1=>1,2=>2,3=>2,4=>4];
    if($x<=4)return $arr[$x];
    return fn($x-2)+fn($x-4);
}
echo fn(10);