Algorithm #04 - "Fibonacci number"

filoscoderยท2019๋…„ 11์›” 25์ผ
0

Toy Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
4/7
post-thumbnail

๐Ÿ‡บ๐Ÿ‡ธ Write a function that accepts a number (n), and returns the nth Fibonacci number.
A Fibonacci sequence is a list of numbers that begins with 0 and 1, and each subsequent number is the sum of the previous two.

For example, the first five Fibonacci numbers are:

0 1 1 2 3

If n were 4, your function should return 3; for 5, it should return 5.

  • Advance 1: Use a recursive solution to this problem;
  • Advance 2: implement an iterative solution.

๐Ÿ‡ฆ๐Ÿ‡ท Escriba una funciรณn que acepte un nรบmero (n) y devuelve el nรบmero correspondiente de la secuencia de Fibonacci.
La secuencia de Fibonacci es una lista de nรบmeros que empiezan con 0 y 1 y cada nรบmero sucesivo es la suma de dos anteriores.

Por ejemplo, los primeros cinco nรบmeros de Fibonacci son los siguientes.

0 1 1 2 3

Si n es 4, su funciรณn debe regresar 3, si es 5, debe retornar 5.

  • Avanzado 1: Use una soluciรณn recursiva para este problema.
  • Avanzado 2: Implemente una solucion iterativa.

๐Ÿ‡ฐ๐Ÿ‡ท ์ˆซ์ž n์„ ์ธ์ž๋กœ ๋ฐ›๊ณ  n๋ฒˆ์งธ์˜ ํ”ผ๋ณด๋‚˜์น˜ ์ˆซ์ž๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์“ฐ์„ธ์š”.
ํ”ผ๋ณด๋‚˜์น˜ ์‹œํ€€์Šค๋Š” 0๊ณผ 1๋กœ ์‹œ์ž‘ํ•˜๋Š” ์ˆซ์ž์˜ ๋ชฉ๋ก์ด๋ฉฐ, ๊ฐ ํ›„์† ์ˆซ์ž๋Š” ์ด์ „ ๋‘ ๊ฐœ์˜ ํ•ฉ์ด๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์ฒ˜์Œ 5๊ฐœ์˜ ํ”ผ๋ณด๋‚˜์ฐŒ ์ˆซ์ž๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

0 1 1 2 3

n์ด 4๋ผ๋ฉด ๋‹น์‹ ์˜ ํ•จ์ˆ˜๋Š” 3์„ ๋ฐ˜ํ™˜, 5๋ผ๋ฉด 5๋ฅผ ๋ฐ˜ํ™˜ํ•ด์•ผ ํ•œ๋‹ค.

  • Advance 1: ์ด ๋ฌธ์ œ์— ๋Œ€ํ•œ ์žฌ๊ท€์  ์†”๋ฃจ์…˜์„ ์‚ฌ์šฉํ•˜์‹ญ์‹œ์˜ค.
  • Advance 2: ๋ฐ˜๋ณต๋ฌธ์„ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•˜์‹ญ์‹œ์˜ค.

Example:

// Test
nthFibonacci(2); // => 1
nthFibonacci(3); // => 2
nthFibonacci(4); // => 3
// etc...

# START [ here ] ๐Ÿ

var nthFibonacci = function(n) {
  // Your CODE
}

// Test
nthFibonacci(2); // => 1
nthFibonacci(3); // => 2
nthFibonacci(4); // => 3

# Javascript solution ๐Ÿ†

  • Run it on your browser console window (F12) ๐Ÿ–ฅ
  • Please feel free to add your preference language solution ๐Ÿ‘ฉโ€๐Ÿ‘ฉโ€๐Ÿ‘งโ€๐Ÿ‘ฆ
  • Do your best to complete the problem ๐ŸŽญ
  • if you can't beat this the solution is below ๐Ÿ˜ฑ

Solution ๐Ÿ‘‡

.
.
.
.
.
.
.
.
.
.
.

SOLUTION #1

var nthFibonacci = function (n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  
  return nthFibonacci(n - 1) + nthFibonacci(n - 2);
};

SOLUTION #2 (recursive)

var nthFibonacci = function(n) {
  // TODO: implement me!
  let temp = [];

  if (n === 0 || n === 1) {
    return n;
  } else if (n > 1) {
    for (var i = 0; i < n; i++) {
      if (i === 0) {
        temp.push(0);
      } else if (i === 1) {
        temp.push(1);
      } else {
        temp.push(temp[i - 1] + temp[i - 2]);
      }
    }
  }

  return temp[n - 1] + temp[n - 2];
};
profile
Never gets bored of making mistakes and wonder why is that

0๊ฐœ์˜ ๋Œ“๊ธ€