CodingSpace

ToyProblem#2_fibonacci 본문

코드스테이츠/ToyProblem

ToyProblem#2_fibonacci

개발자_조이킴 2021. 10. 7. 00:18

피보나치 수열은 다양한 방식으로 구현할 수 있다.

피보나치 수열은 다음과 같다:

 

0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

① 먼저, easy한 방법!

 

function fibo(num) {
  
  if(num === 0) return 0
  if(num === 1) return 1

  return fibo(num-2) + fibo(num-1)
}

 

② 점화식을 활용한 방법!

 

피보나치 수열의 점화식을 유도는 아래 사이트 참고하자↓

https://suhak.tistory.com/81

 

피보나치(Fibonacci) 수열의 일반항 구하기

문제 계단을 한 칸씩 오르거나 두 칸씩 오른다. 칸의 개수가 20인 계단을 오르는 방법의 수를 구해보자. 풀이 칸의 개수가 $n$일 때 오르는 방법의 수를 `a_{n}`이라고 하자. `a_{1}=1`,`a_{2}=2`,`a_{3}=3`임

suhak.tistory.com

 

피보나치 일반항

 

function fibo(num) {

  let alpha = (1+Math.sqrt(5)) / 2
  let beta = (1-Math.sqrt(5)) / 2
  let gama = 1 / Math.sqrt(5)

  return Math.floor(gama * (Math.pow(alpha, n) - Math.pow(beta, n)))
}

 

Comments