59 lines
3.7 KiB
Markdown
59 lines
3.7 KiB
Markdown
---
|
||
id: 5900f3d21000cf542c50fee4
|
||
title: 'Завдання 101: Оптимальний многочлен'
|
||
challengeType: 5
|
||
forumTopicId: 301725
|
||
dashedName: problem-101-optimum-polynomial
|
||
---
|
||
|
||
# --description--
|
||
|
||
Якщо нам представлені перші k членів послідовності, неможливо з упевненістю назвати значення наступного члена, оскільки існує нескінченно багато поліноміальних функцій, які можуть моделювати послідовність.
|
||
|
||
Як приклад, розгляньмо послідовність кубів чисел. Вона визначається твірною функцією, $u_n = n^3: 1, 8, 27, 64, 125, 216, \ldots$
|
||
|
||
Припустимо, що нам відомі лише перші два члена цієї послідовності. Керуючись принципом "чим простіше – тим краще", припустимо лінійну залежність та передбачимо, що значення наступного члена дорівнює 15 (різниця арифметичної прогресії дорівнює 7). Навіть, якщо б нам були відомі перші три члени, згідно з тим самим принципом "простоти", слід припустити квадратичну залежність.
|
||
|
||
Визначимо $OP(k, n)$ як член $n^{th}$ оптимальний многочлен твірної функції для перших k членів послідовності. Треба чітко розуміти, що $OP(k, n)$ буде точно генерувати члени послідовності для $n ≤ k$, тоді, потенційно, першим неправильним членом (FIT) (з англ. – First incorrect term) буде $OP(k, k+1)$; у цьому випадку назвемо його поганим оптимальним многочленом (BOP) (від англ.– Bad optimum polynomial).
|
||
|
||
За основу візьмемо випадок коли відомо лише перший член послідовності, тоді раціональніше було б припустити постійність, тобто для $n ≥ 2, OP(1, n) = u_1$.
|
||
|
||
Звідси отримуємо такі оптимальні многочлени для кубічної послідовності:
|
||
|
||
$$\begin{array}{ll} OP(1, n) = 1 & 1, {\color{red}1}, 1, 1, \ldots \\\\
|
||
OP(2, n) = 7n−6 & 1, 8, {\color{red}{15}}, \ldots \\\\ OP(3, n) = 6n^2−11n+6 & 1, 8, 27, {\color{red}{58}}, \ldots \\\\
|
||
OP(4, n) = n^3 & 1, 8, 27, 64, 125, \ldots \end{array}$$
|
||
|
||
Очевидно, не існує BOP для k ≥ 4. Враховуючи суму перших неправильних членів, створених поганими оптимальними многочленами (зазначені у $\color{red}{red}$ вище), отримуємо 1 + 15 + 58 = 74. Розгляньмо твірну функцію для многочлена десятого степеня:
|
||
|
||
$$u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}$$
|
||
|
||
Знайдіть суму перших неправильних членів (FIT) для поганих оптимальних многочленів (BOP).
|
||
|
||
# --hints--
|
||
|
||
`optimumPolynomial()` має повертати `37076114526`.
|
||
|
||
```js
|
||
assert.strictEqual(optimumPolynomial(), 37076114526);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function optimumPolynomial() {
|
||
|
||
return true;
|
||
}
|
||
|
||
optimumPolynomial();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|