e-olymp 1075. Умножение многочленов

Задача с сайта e-olymp.com.
Засчитанное решение. (C++)
Засчитанное решение. (Java)

Условие задачи

Вводится в символьной форме два многочлена от [latex]x[/latex] с целыми коэффициентами. Вывести их произведение в порядке убывания степеней — также в символьной форме. Степень исходных многочленов не более [latex]10[/latex], коэффициенты исходных многочленов по модулю не более [latex]{ 10 }^{ 4 }[/latex].

Входные данные

В двух строках находятся многочлены.

Выходные данные

В единственной строке выводится многочлен.

Тесты

Входные данные Выходные данные
1 0
0
0
2 x+1
x-1
x^2-1
3 -5
x^2+x+x-2x^3
10x^3-5x^2-10x
3 x^10+2x^9+3x^8
-1
-x^10-2x^9-3x^8
4 x^10+2x^9+3x^8
0
0
5 x^10+5x^2
x^3-4x
x^13-4x^11+5x^5-20x^3

Решение с использованием класса string

Код программы

Нажмите, чтобы выполнить его на ideone.com.

Описание

Сначала в функции main объявляются две строки a и b. В них водятся исходные два многочлена. Но в форме строк, особенно учитывая, что подобные слагаемые не всегда приведены, умножать многочлены не удобно. Потому объявляются три вектора: a_decomposed, b_decomposed и c_decomposed. Первые два имеют размер [latex]11[/latex], поскольку в условии сказано, что многочлены могут быть от нулевой до десятой степени включительно. В них элемент с индексом [latex]i[/latex] равняется коэффициенту при слагаемом многочлена, в котором [latex]x[/latex] имеет степень [latex]i[/latex]. Они заполняются при помощи функции decompose. В ней при помощи функции analyze отдельно анализируется каждое слагаемое многочлена, и результат заносится в вектор. c_decomposed хранит коэффициенты многочлена, полученного умножением двух исходных. Значения его элементов вычисляются при помощи функции multiplicate. После в ходе работы функции compose многочлен в требуемой форме записывается в строку c. Далее, если её первым символом является [latex]+[/latex], он удаляется из строки. Наконец, если c — непустая строка, она выводится. Иначе выводится [latex]0[/latex].

Решение с использованием c-string

Код программы

Нажмите, чтобы выполнить его на ideone.com.

Описание

Алгоритм решения тот же. Следует отметить: поскольку объекты типа char* «не знают» свою длину, и в силу других причин, в некоторых местах программы используются «магические числа». Однако они не взяты случайно, а продиктованы условием задачи (к примеру, тем, что максимальная степень исходных многочленов — [latex]10[/latex] и т.п.). Только подходящее значение переменной max_number_of_symbols было найдено эмпирически.

Решение на Java

Код программы

Нажмите, чтобы выполнить его на ideone.com.

Related Images:

e-olymp 1073. Статическая сложность

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

Входные данные

В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex],  [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.

Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].

(Примечание: то, что представляет из себя программа, можно прочитать по ссылке выше.)

Выходные данные

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Решение

Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:

  1. Обнулять массив [latex]coefficients[/latex].
  2. Заполнять его новыми данными с помощью функции  void getCoefficients(int* coefficients);
  3. Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
  4. Выводить требуемую информацию.

Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:

  • [latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
  • [latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
  • [latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.

Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену  соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».

Тесты

Ввод Вывод
1 2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

2 3
BEGIN
END

BEGIN
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
END END END OP 3
END END END OP 3
END END END OP 3
END

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END
Program #1
Runtime = 0

Program #2
Runtime = n^9+4*n^6+4*n^3+3

Program #3
Runtime = 35*n^2+11*n+43

Код

 

Ссылки

Засчитанное решение на e-olymp.

Рабочий код на ideaone.

Related Images:

MLoop 16

Постановка задачи

MLoop16.

Вычислите с точностью [latex]\epsilon[/latex] значение функции [latex]f\left( x \right) = \frac{\sin 2x}{x}[/latex]. При вычислениях допустимо использовать только арифметические операции.

Алгоритм решения

Разложим [latex]g \left( x \right) = \sin x[/latex] по формуле Тейлора с опорной точкой [latex]x_0 = 0[/latex] и остаточным членом в форме Лагранжа:
[latex]g \left( x \right) = P_n \left( x_0 ; x \right) + R_n \left( x_0 ; x \right)[/latex],
[latex]P_n \left( x_0 ; x \right) = g \left( x_0 \right) + \sum_{k = 1}^{n} \frac{g^{\left( k \right)} \left( x_0 \right) }{k!} \left( x — x_0 \right) ^k[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{g^{\left( n + 1 \right)} \left( \xi \right)}{\left( n + 1 \right) !}\left( x — x_0 \right) ^{n + 1} , x_0 < \xi < x[/latex].

Найдем производные [latex]g \left( x \right)[/latex]:
[latex]g’ \left( x \right) = \cos x = \sin \left( x + \frac{\pi}{2} \right)[/latex],
[latex]g» \left( x \right) = \cos \left( x + \frac{\pi}{2} \right) = \sin \left( x + 2 \frac{\pi}{2} \right)[/latex],
[latex]g»’ \left( x \right) = \cos \left( x + 2 \frac{\pi}{2} \right) = \sin \left( x + 3 \frac{\pi}{2} \right)[/latex],
[latex]\cdots[/latex]
[latex]g^{\left( k \right)} \left( x \right) = \cos \left( x + \left( k — 1 \right) \frac{\pi}{2} \right) = \sin \left( x + k \frac{\pi}{2} \right)[/latex].

Вычислим значение функции и ее производных в точке [latex]x_0[/latex]:
[latex]g \left( x_0 \right) = \sin x_0 = \sin 0 = 0[/latex],
[latex]g’ \left( x_0 \right) = \sin \left( x_0 + \frac{\pi}{2} \right) = \sin \frac{\pi}{2} = 1[/latex],
[latex]g» \left( x_0 \right) = \sin \left( x_0 + 2 \frac{\pi}{2} \right) = \sin \pi = 0[/latex],
[latex]g»’ \left( x_0 \right) = \sin \left( x_0 + 3 \frac{\pi}{2} \right) = \sin \frac{3 \pi}{2} = -1[/latex],
[latex]\cdots[/latex]
[latex]g ^{ \left( 2k — 1 \right) } \left( x_0 \right) = \sin \left( x_0 + \left( 2k — 1 \right) \frac{\pi}{2} \right) = \sin \left( \pi k + \frac{\pi}{2} \right) = \left( -1 \right) ^{k — 1}[/latex],
[latex]g ^{ \left( 2k \right) } \left( x_0 \right) = \sin \left( x_0 + 2k \frac{\pi}{2} \right) = \sin \pi k = 0[/latex].

Тогда
[latex]P_n \left( x_0 ; x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! }[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]g \left( x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]f \left( x \right) = \frac{ g \left( 2x \right) }{ x } = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! }[/latex].

Осталось найти такое [latex]n \in \mathbb{N}[/latex], чтобы выполнялось неравенство
[latex]\left| \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! } \right| \le \left| \frac{ \left( 2x \right) ^ {n + 1} }{ x \left( n + 1 \right) ! } \right| < \epsilon[/latex].

Для ускорения вычислений зададим реккурентную формулу для слагаемых суммы
[latex]\sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Представим каждое слагаемое суммы в виде
[latex]\alpha_k = \alpha_{k — 1} \cdot b_k = \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Выразим [latex]b_k[/latex]:
[latex]b_k = \frac{ \alpha_k }{ \alpha_{ k — 1 } } = \frac{ \left( -1 \right) ^ {k — 1} \cdot \left( 2x \right) ^ {2k — 1} \cdot x \left( 2 \left( k — 1 \right) — 1 \right) ! }{ x \left( 2k — 1 \right) ! \cdot \left( -1 \right) ^ { \left( k — 1 \right) — 1 } \cdot \left( 2x \right) ^ {2 \left( k — 1 \right) — 1} } = — \frac{4x^2}{\left( 2k — 2 \right) \left( 2k — 1 \right)}[/latex].
Тогда
[latex]\alpha_k = \begin{cases} 2 & k = 1, \\ \alpha_{k-1} \cdot b_k & k > 1. \end{cases}[/latex]

Тесты

Входные данные Выходные данные
[latex]x[/latex] [latex]\epsilon[/latex] [latex]f\left( x \right) = \frac{\sin 2x}{x} + \lambda, \lambda\in\left( -\epsilon;\epsilon \right)[/latex]
[latex]\frac{5\pi}{2}[/latex]  [latex]0[/latex]  [latex]\frac{2}{5\pi}[/latex]
 [latex]\pi[/latex]  [latex]0.01[/latex]  [latex]0[/latex]
 [latex]0[/latex]  [latex]0.1[/latex]  [latex]\emptyset[/latex]

Реализация

ideone: ссылка

Related Images:

Ю4.19

Задача. Многочлен [latex]{P}_{n}(x)[/latex] задан массивом своих коэффициентов [latex]A(n+1)[/latex]. Найти массив коэффициентов производной этого многочлена.

[latex]n[/latex] [latex]{a}_{2}[/latex] [latex]{a}_{1}[/latex] [latex]{a}_{0}[/latex] [latex]{b}_{2}[/latex] [latex]{b}_{1}[/latex] [latex]{b}_{0}[/latex]
2 0 0 0 0 0 0
2 17 2 3 34 2 0
2 0 -4 1 0 -4 0

Давайте вначале распишем сам многочлен [latex]{P}_{n}(x)[/latex]:
[latex]{P}_{n}(x)={a}_{n}{x}^{n} + {a}_{n-1}{x}^{n-1} + … + {a}_{0}{x}^{0}[/latex].

А его производная соответственно равна:
[latex]{P}_{n}^{(1)}(x)=n{a}_{n}{x}^{n-1} + (n-1){a}_{n-1}{x}^{n-2} + … + 0*{a}_{0}{x}^{-1}[/latex]

Давайте посмотрим как изменился массив [latex]A(n+1)[/latex]:

[latex]{P}_{n}(x)[/latex] [latex]{a}_{n}[/latex] [latex]{a}_{n-1}[/latex] [latex]{a}_{0}[/latex]
[latex]{P}_{n}^{(1)}(x)[/latex] [latex]n*{a}_{n}[/latex] [latex](n-1)*{a}_{n-1}[/latex] [latex]0*{a}_{0}[/latex]

Иными словами каждый элемент умножается на свой же номер в массиве, так что мы можем при считывании сразу же умножать полученные элементы на их номера. Осталось только написать программу.

Код программы: http://ideone.com/JHXOTa.

Related Images: