Fibonacci

こんなのがデフォルトで入ってる。

def run
  # Code here!
end

STDIN.gets.to_i.times { run }

↓サンプルは通ったけど、もっと良いアルゴリズム出さないと遅すぎて計算できんぞ、とRejectくらった。

def fib(n)
  if n<=1
    return n
  else
    return fib(n-1)+fib(n-2)
  end
end

def run
  # Code here!
  STDIN.gets.to_i.times { |n| p fib(n) }
end

↓うまくいった〜。

def fib_by(n)
  a=[0,1]
  
  n.times do |n|
    if n >= a.size
      a << a[-1] + a[-2]
    end
    p a[n]
  end
end

def run
  fib_by(STDIN.gets.to_i)
end

---

The Fibonacci sequence is a sequence in which each term is the sum of the two previous terms, like so:

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
…

We want to write a function that prints the first X numbers of the sequence.

The first line of the input will be an integer N (1 <= N <= 100).

Each of the following N lines represents a single test case, containing an integer X (1 <= X <= 90).
 
For each test case, print the first X numbers of the Fibonacci sequence, one per line. No blank line between test cases.

Sample Input/Output

1
3

0
1
1