iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
自我挑戰組

從真「新」鎮出發!30天的刷題修行篇,讓寫程式成為新必殺技系列 第 5

強敵!費波那契數的哥哥登場,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 的部分,這樣就可以一同解決我的第一、第二點狀況。

好啦,今天的解題就到這邊,數列、演算法這類型的問題對我新手來說太刺激啦,我要先去讓我的腦袋冷卻一下了,掰掰~


上一篇
字串的動次踏次,Ruby 30 天刷題修行篇第四話
下一篇
初探編碼的世界,Ruby 30 天刷題修行篇第六話
系列文
從真「新」鎮出發!30天的刷題修行篇,讓寫程式成為新必殺技16

尚未有邦友留言

立即登入留言