Files

camperbot 905018ad35 chore(i18n,learn): processed translations (#45670 )

2022-04-11 19:34:39 +05:30

3.7 KiB

Raw Permalink Blame History

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5900f3d21000cf542c50fee4	Завдання 101: Оптимальний многочлен	5	301725	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.

assert.strictEqual(optimumPolynomial(), 37076114526);

--seed--

--seed-contents--

function optimumPolynomial() {

  return true;
}

optimumPolynomial();

--solutions--

// solution required

3.7 KiB Raw Permalink Blame History Unescape Escape