【Ruby】採用試験でフィボナッチ数列出たけど解けなかったので復習

執筆者について

・未経験からエンジニアに転職するため就職活動中
・問題が解けなくて悔しい

フィボナッチ数列について

n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に

F0 = 0,
F1 = 1,
Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される。これは、2つの初期条件を持つ漸化式である。

この数列 (Fn)はフィボナッチ数列（フィボナッチすうれつ、（英: Fibonacci sequence）と呼ばれ、

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, と続く。最初の二項は 0, 1 であり、以後どの項もその直前の2つの項の和となっている。

出典：wikipedia - フィボナッチ数列

上記に書いてある通り、前の項とその前の項を足してできた和が答えになる数列

問題（例）

1, 1, 2, 3, 5, 8, 13, 21 , 34, 55, 89, 144, 233, 377, 610,
のように第n+2項が、 第n+1項と、第n項の和になるよう数列をプログラミングで書く

解答の考え方(解説してもらった)

まずは例外である1項と2項をif文で1にする。

if n == 1 || n == 2
  1
end

3項目以降は

x=項数とおいて
a = x-2の答え
b = x-1の答え
と置いて
多重代入とtimesメソッドを用いて計算をさせまくる

a, b = 0, 1
n.times { a, b = b, a + b }
a

fiv(4)の場合
（4.times { a, b = b, a + b }の場合）

1回目の計算
{a , b = 1, 0 + 1 }
a = 1になる
b = 2になる

2回目の計算
{a , b = 2, 1 + 2}
a = 2
b = 3

3回目の計算
{a , b = 3, 2 + 3}
a = 3
b = 5

4回目の計算
{a , b = 5, 3 + 5}
a = 5
b = 8

aの値が答えになるので戻り値にaを記載する

a = 0
b = 1にする理由は0項目の答えと1項目の答えだから

def fiv(n)
    if n == 1 || n == 2
        1
    else
        a, b = 0, 1
        n.times { a, b = b, a + b }
        a
    end
end

※PHPで解説もらったのをrubyに変換

記事書きながら思った解答

def fiv(x)
  if x == 1 || x == 2
     1
  else
     fiv(x-2) + fiv(x-1)
  end
end

多重代入とか知らなかったから解けないんじゃね？知らないかったしと思ったけれども
最初に1項目と2項目をifで答え出して良いならこれでもよかったんじゃないかなと思った。

これならテスト中でもかけた気がした。