强敌！费波那契数的哥哥登场，Ruby 30 天刷题修行篇第五话

大家好，我是 A Fei，相信大家应该都听过费波那契数（Fibonacci）的大名，又称费式数列，是蛮经典的数学题目，有很多关於它的变形题，今天我们也是要来挑战它的其中一种。

这里不免俗地要科普一下什麽是费式数列，根据本草纲目，啊不对，是维基百科记载，以文字来说，费氏数列是由 0 和 1 开始，後一个数字由前两个数字相加得来，特别注意的是，0 不是第一项数字，而是第零项。写起来长这样：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

让我们直接进入主题：
（特此注明：题目来源是Codewars）

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, ...]

Well, you may have guessed it by now, but to be clear: you need to create a fibonacci function that given a signature array/list, returns the first n elements - signature included of the so seeded sequence.

Signature will always contain 3 numbers; n will always be a non-negative number; if n == 0, then return an empty array (except in C return NULL) and be ready for anything else which is not clearly specified ;)

题目难度：6 kyu
是否有在时限内解题：是

分析一下题目，不同於一般的费氏数列，这题的 Tribonacci 数列，後一个数字是由前 3 个数字相加所得。题目要我们实作一个方法，带入起始的 signature，它是一个包含 3 个数字的阵列，以及带入 n，代表输出的阵列长度，如果 n 为 0，则回传一个空阵列。

我的想法是将输入的条件分成 3 类：

1.n == 0，即回传一个空阵列；

2.n > 0 && n < 3，即 n 不等於 0 但小於 signature 长度的情况下，把 signature 中的元素取出再 push 进新阵列 result，比如 signature = [0, 1, 2] 而 n = 2，即回传 [0, 1]，这里我用了 0.upto() 方法，达到回圈的效果。

3.n >= 3，首先0.upto(2) {|i| result.push(signature[i]) }将 signature 中，代表前三项数字的 3 个元素 push 进 result，然後数列第四项以後的数字，使用result[i] + result[i+1] + result[i+2]方式计算，其含意就是把数列中，最尾巴的 3 个数字相加，再将结果 push 进 result。

例如 signature = [0, 1, 2] 而 n = 4，0.upto(2) {|i| result.push(signature[i]) }会先将 signature 内的元素完全 push 进 result，此时 result = [0, 1, 2]，0.upto(n - 4) {|i| result.push(result[i] + result[i+1] + result[i+2]) }会将 result 後三个数字相加，也就是 3 push 到最後面，以此类推。有趣的是 0.upto() 如果里面是负数的话，则不会执行该方法。

我的解答如下：

def tribonacci(signature,n)
  result = []
  if n == 0
    result
  elsif n > 0 && n < 3
    0.upto(n - 1) {|i| result.push(signature[i]) }
    result
  else  
    0.upto(2) {|i| result.push(signature[i]) }
    0.upto(n - 4) {|i| result.push(result[i] + result[i+1] + result[i+2]) }
    result
  end
end

对比评分最高的解答：

def tribonacci(s, n)
  for i in 3..n
    s[i] = s[i-1] + s[i-2] + s[i-3]
  end
  return s.slice(0, n)
end

只能说高手境界，3..n 是 Ruby 很有特色的语法，代表 3 到 n 的范围；for in 则是 Ruby 中类似 JavaScript 或其他语言 for 回圈的写法，没想到它们居然有这样的 combo 技；slice(0, n) 则是取出阵列索引值 0 为起点，长度 n 的部分，这样就可以一同解决我的第一、第二点状况。

好啦，今天的解题就到这边，数列、演算法这类型的问题对我新手来说太刺激啦，我要先去让我的脑袋冷却一下了，掰掰～