Fibonacci sequence

今天做了一道很初级的算法题,就是算Fibonacci sequence(斐波那契数列)。其实就是一个递归算法。
通常情况下这个数列的公式为:

F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

这里我先将题目粘贴出来:

Well met with Fibonacci bigger brother, AKA Tribonacci.
As the name may already reveal, it works basically like a Fibonacci, but summing the last 3 (instead of 2) numbers of the sequence to generate the next. And, worse part of it, regrettably I won’t get to hear non-native Italian speakers trying to pronounce it :(
So, if we are to start our Tribonacci sequence with [1,1,1] as a starting input (AKA signature), we have this sequence:
[1,1,1,3,5,9,17,31,…]
But what if we started with [0,0,1] as a signature? As starting with [0,1] instead of [1,1] basically shifts the common Fibonacci sequence by once place, you may be tempted to think that we would get the same sequence shifted by 2 places, but that is not the case and we would get:
[0,0,1,1,2,4,7,13,24,…]

其实就是先给定头三个数值,然后去列出从第1位到第n位的内容。但当我n为0时,内容为一个空数组。根据给出的两个事例,我们可以看到从第四位数字开始其实就是前三位数字之和。那么公式就是 “F(n)=F(n-1)+F(n-2)+F(n-3)(n>3,n∈N*)”,当 n<=3 就截取给出的数组对应的位数为止。

依照上面题目所说的,我写出了下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function tribonacci($signature, $n) {
$data = array();
if($n == 0){
return $data;
}else{
if($n <= 3){
$data = array_slice($signature,0,$n);
}else{
$data = $signature;
for($i = 3; $i <$n; $i++){
$data[$i] = $data[$i-3] + $data[$i-2] + $data[$i-1];
}
}
return $data;
}
}

虽然这个代码能够通过,但是不简洁甚至丑陋。

下面是看到另一个人写的:

1
2
3
4
5
6
function tribonacci(array $signature, int $n): array {
for ($i = $n - 3; $i > 0; $i--) {
$signature[] = array_sum(array_slice($signature, -3));
}
return array_slice($signature, 0, $n);
}

分析:

首先可以看到它明确定义了两个传入进来的内容的类型数组和数字,然后它的循环只需要去只有在n大于3的时候进行,小于等于三直接将传进来的数组尽心截取返回。n大于3,可以看到循环体里面做的操作,截取数组最后面的三个值,然后计算截取中的数组值的和。

值得学习的地方:

  1. 没有定义新的数组
  2. 只使用了PHP自身所带的函数
  3. 代码简介明了,没有过多的判断