Реализация треугольника Паскаля на JavaScript


Я экзамен по осуществлению треугольник Паскаля на JavaScript Я видел, что он чем-то похож на последовательности Фибоначчи. С этим я придумал решение ниже.

function pascalTriangle(n){
  var data = [[1],[1,1]];
  var rowNum = n - 2;
  for (var i = 1; i <= rowNum; i++){
   var curr = i;
    data.push([1]);
    for (var x = 0; x< data[curr].length - 1; x++){
      var calcMid = data[curr][x] + data[curr][x + 1];
      data[curr+1].push(calcMid);
    }
    data[curr+1].push(1);
  }
  console.log(data);
}
pascalTriangle(5);

Что я сделал, заключается в том, что я сначала инициализировать 1-й и 2-й строке треугольника Паскаля, а затем сделать расчет для среднего с идеей из последовательности Фибоначчи.

Я чувствую, что решение я придумать можно улучшить.



409
0
задан 5 апреля 2018 в 02:04 Источник Поделиться
Комментарии
1 ответ

Незначительные очков стиля и альтернативное решение.

С этими типами проблем в первый порт всегда Википедию , чтобы получить столько информации, сколько вы можете прежде, чем вы начнете на создание решения.

Две вещи выделяются в раствор.


  1. Строки симметричны, правая сторона является зеркальным отражением левой.

  2. Существует формула, которая позволяет вычислить ряд, который может помочь уменьшить сложность.

Ваш код

Нет ничего совершенно плохого с кодом, ниже приведены лишь общие моменты стиля


  • Делать вывод за пределами функции.

  • Использовать const для переменных, которые не меняются.

  • Объявлять переменные с var в верхней части функции или использовать let объявлять переменные в блоке они будут использованы.

  • Вложенные циклы старайтесь избегать двойного индексирования, создав ссылку на внутренний массив вне внутреннего цикла.

  • Функция не является полным, так как он не возвращает правильные результаты pascalTriangle(0) и pascalTriangle(1) простой, если заявление об этом позабочусь.

  • Не дублировать переменные без причины. Переменная i (из цикла итерации счетчик) немедленно копируется в переменную curr и не меняется внутри цикла.

  • При написании мы ставили пробел после запятой, это делает его легче читать потом без,так показано на рисунке. То же самое с Код, ставить пробелы после запятых так, чтобы оно не все сливается воедино. Же для операторов, в которых Конвенция пространство любой стороны. например data[curr+1] должно быть data[curr + 1] и data = [[1],[1,1]]; должно быть data = [[1], [1, 1]];

  • (мелкие точки как проблема проста и сортировки раствор) можно использовать некоторые лучшие имена для некоторых переменных.

Рерайт

Переписать вашу функцию, используя вышеуказанные пункты.

function pascalTriangle1(rowCount) {
if (rowCount === 0) { return [] }
if (rowCount === 1) { return [[1]] }
const rows = [[1], [1, 1]];
var prevRow = rows[1];
for (let n = 1; n < rowCount - 1; n += 1) {
const row = [1];
let val = prevRow[0];
for (let k = 0; k < prevRow.length - 1; k += 1) {
row.push(val + (val = prevRow[k + 1]));
}
row.push(1);
rows.push(row);
prevRow = row;
}
return rows;
}

Альтернативное решение

Следующие сокращает количество вычислений примерно половину за счет использования симметрии каждого ряда.

Дальнейшие улучшения могут быть сделаны с помощью Float64Array и предварительного расчета размера треугольника, то индексация прямо на массив, во избежание дорогостоящих создания массива left и right конкатенации строк и для каждой строки. Но что бы только показать какие-либо реальные выгоды для очень больших треугольников, где ему должны провести все строки будут сомнительными.

const pascalTriangle = rowCount => {
const createRow = rowIndex => {
var k = 1, val = 1;
const n = rowIndex + 1;
const left = [val];
const right = [val];
while (k < n / 2) { // only do half the row
val = val * (n - k) / k++;
left.push(val);
right.unshift(val);
}
if (n % 2) { right.shift() } // when n is odd remove first right item
return [...left, ...right];
}
const rows = [];
if (rowCount > 0) {
let i = 1;
rows.push([1]);
while (i < rowCount) { rows.push(createRow(i++)) }
}
return rows;
}

2
ответ дан 5 апреля 2018 в 10:04 Источник Поделиться