Make it Real Elite — Вторая неделя — Треугольник Паскаля и последовательность Фибоначчи

Треугольник Паскаля представляет собой массив биномиальных коэффициентов. Это треугольник, в котором первая и последняя позиция каждого массива равна 1, а числа между собой представляют собой сумму позиции 0 с позицией 1, позиции 1 с позицией 2 и продолжаются до конца. Вы можете определить количество «этажей», оно будет равно длине массива. Лучший способ понять треугольник Паскаля — это его изображение.

Чтобы решить треугольник Паскаля с помощью JavaScript, мы можем сделать что-то вроде этого:

var createTriangle = function(floor, arr) {
  var triangle = arr || [[1]];
  
  if(triangle.length === floor) {
    return triangle;
  }
  var prevFloor = triangle[triangle.length - 1];
  var currentFloor = [1];
  
  for(var i = 1; i < prevFloor.length; i++) {
    currentFloor[i] = prevFloor[i] + prevFloor[i - 1];
  }
 
  currentFloor.push(1);
  triangle.push(currentFloor);
  
  return createTriangle(floor, triangle)
};
console.log(createTriangle(10));

Мы собираемся использовать вызов метода createTriangle, который принимает 2 параметра, один из которых — это пол (лимит строк, которые мы хотим) и массив, который будет треугольником, который мы строим (используется в рекурсии). Затем мы устанавливаем некоторые проверки и базовый случай, потому что мы используем некоторую рекурсию. Нам нужна предыдущая строка треугольника для решения фактического, потому что нам нужно суммировать некоторые значения. Как мы видим на изображении и в теории, треугольник начинается с 1 и заканчивается 1, поэтому мы начнем текущий этаж с 1 и начнем создавать каждую новую позицию с суммы той же позиции предыдущей строки с одной раньше (он должен начинаться с позиции 1, потому что позиция arr[0] должна быть 1), и мы нажимаем 1 на последнюю позицию обр. После создания этого массива мы помещаем его в треугольник и снова вызываем метод, пока длина массива, состоящего из нескольких массивов (строк), не сравняется с полом, который мы определяем.

Решение на консоли будет таким с примером, используемым в коде:

[ [ 1 ],
  [ 1, 1 ],
  [ 1, 2, 1 ],
  [ 1, 3, 3, 1 ],
  [ 1, 4, 6, 4, 1 ],
  [ 1, 5, 10, 10, 5, 1 ],
  [ 1, 6, 15, 20, 15, 6, 1 ],
  [ 1, 7, 21, 35, 35, 21, 7, 1 ],
  [ 1, 8, 28, 56, 70, 56, 28, 8, 1 ],
  [ 1, 9, 36, 84, 126, 126, 84, 36, 9, 1 ] ]

Последовательность Фибоначчи:

Последовательность Фибоначчи — это ряд чисел, в котором следующее число находится путем сложения двух последних чисел ряда.

ПравилоXn = Xn-1 + Xn-2

var solveFibonacci = function(numb, result) {
  result = result || [1];
  
  if(result.length === numb) {
    return result;
  }
  if(result.length >= 2) {
    result.push(result[result.length - 2] + result[result.length - 1]);
  } else {
    result.push(result[result.length - 1]);
  }
  return solveFibonacci(numb, result);
};
console.log(solveFibonacci(14))

Решение n = 14 равно [1,1,2,3,5,8,13,21,34,55,89,144,233,377]

Чтобы решить эту проблему, создайте метод с двумя параметрами, один из которых n , а другой будет решением n; если результат не определен, мы установим его равным 1. Поскольку мы используем рекурсию, мы должны установить базовый случай, когда длина array равна n. затем мы проверяем, можем ли мы применить правило или просто n-1, а затем снова вызываем тот же метод.

Если вы просто хотите получить ответ, а не всю последовательность, вы можете решить ее следующим образом:

var solveFibonacci = function(n) {
  if (n < 2) {
    return n;
  } else {
    return solveFibonacci(n - 2) + solveFibonacci(n - 1);
  }
};
console.log(solveFibonacci(14))

Мемоизация:

Вы можете сделать это, используя что-то вроде Memoization; идея его использования состоит в том, чтобы сохранить результаты на объекте, прежде чем применять некоторую рекурсию и повторять много раз, чтобы найти ответ на то, что мы уже нашли, мы просто ищем объект, где хранятся предыдущие результаты .

var solveFibonacci = function(n, memoization) {
  memoization = memoization || {};
  
  if (memoization[n]) {
    return memoization[n];
  }
  
  if (n < 2) {
    return n;
  } else {
    value = solveFibonacci(n-2) + solveFibonacci(n-1);
    return memoization[n] = value;
  }
};
console.log(solveFibonacci(14))