[Дзен-трансгуманист]

Задача № 1

Составить функцию, которая продолжала бы числовую последовательность (арифметическую).

Мое решение через полином Лагранжа.

function throwError (fname, error) { throw new Error(fname + ": " + error); }

function lagrangePoly (points) {

  if (points.length % 2) { throwError("lagrangePoly", "bad number of elements"); }

  var result = [];
  var degree = points.length / 2;
  var i, j, t, cn, c, c0, c1;

  for (i=0, t=[]; i<points.length; i++) {

    if (!isFinite(points[i])) { throwError("lagrangePoly", "non-finite value encountered"); }
    if (!(i % 2)) { t.push(points[i]); }
  }

  t.sort(function (a, b) { return a - b; });

  for (i=0; i<degree-1; i++) { if (t[i] == t[i+1]) { return false; } }

  for (i=0, c1=[]; i<degree; i++) {

    c1.push(points[i*2 + 1]);

    for (j=1, t=1; j<degree; j++) { t *= points[i*2]; c1.push(-t); }
  }

  c = [c1];

  for (cn=degree; cn>1; cn--) {

    c0 = c1;
    c1 = [];

    for (i=0; i<cn-1; i++) {

      t = c0[i * cn + 1] - c0[(i+1) * cn + 1];

      for (j=0; j<cn; j++) {

        if (j == 1) { continue; }

        c1.push(-(c0[i * cn + j] - c0[(i+1) * cn + j]) / t);
      }
    }

    c.push(c1);
  }

  for (cn=degree-1; cn>-1; cn--) {

    result[cn] = c[cn][0];

    for (i=1; i<degree-cn; i++) { result[cn] += c[cn][i] * result[cn+i]; }
  }

  return result;
}

function polyFunction (poly) {

  var _poly = [].concat(poly);

  return function (x) {

    var i, e, y;

    for (i=0, e=1, y=0; i<_poly.length; i++) {

      y += e * _poly[i];
      e *= x;
    }

    return y;
  }
}

function continueSequence (sequence) {

  var points = [], polyfn, i;

  for (i=0; i<sequence.length; i++) { points.push(i, sequence[i]); }

  polyfn = polyFunction(lagrangePoly(points));

  return function () { return polyfn(i++); }
}

function maxFraction (value, digits) {

  if (!isFinite(value) || !isFinite(digits)) { throwError("maxFraction", "bad argument(s)"); }

  var fixed = (+value).toFixed(digits);
  var i = fixed.length - 1;

  loop: while (true) {

    switch (fixed.charAt(i)) {

    case "0": i--; continue;
    case ".": i--; break loop;
    }

    break;
  }

  return fixed.slice(0, i+1);
}

function test (sequence, iterations) {

  var generator = continueSequence(sequence);
  var result = sequence.join(", ") + "...\n";

  while (iterations--) { result += maxFraction(generator(), 6) + (iterations? ", ": "...\n\n"); }

  return result;
}

var result = "";

result += test([ 0, 1, 4, 7, 10], 15);
result += test([-2, 1, 4, 7, 10], 15);
result += test([ 0, 1, 3, 6, 10], 15);

result += test([0, 1, 4, 9], 15);
result += test([0, 1, 8, 27], 15);

result += test([9, 8, 7, 6, 5, 4, 3, 2, 1], 15);
result += test([9, 8, 7, 6, 5, 4, 3, 2, 2, 2, 10], 15);

alert(result);