6
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

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

執筆者について

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

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

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で答え出して良いならこれでもよかったんじゃないかなと思った。

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

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
6
Help us understand the problem. What are the problem?