Главная
Биогафии
Как перемножить многочлены. Умножение одночленов и многочленов

Как перемножить многочлены. Умножение одночленов и многочленов

Правило вычисления произведения многочленов.

Для того чтобы рассмотреть произведение многочленов, для начала вспомним, как умножить одночлен на многочлен.

Произведение одночлена и многочлена находится следующим образом:

  • составляется произведение одночлена и многочлена.
  • раскрываются скобки.
  • группируются числа с числами, одинаковые переменные друг с другом.
  • перемножаются числа и складываются степени соответствующих одинаковых переменных.

Рассмотрим теперь умножение двух многочленов на примере:

Пример 1

Умножим многочлен $x-y+z$ на многочлен $\ {xy}^5+y^6-{xz}^5$.

Вначале запишем произведение многочленов:

\[\left(x-y+z\right)({xy}^5+y^6-{xz}^5)\]

Сделаем следующую замену. Пусть $x-y+z=t$, получим:

Получили произведение одночлена на многочлен. Найдем его по выше изложенному правилу.

Раскроем скобки:

Сделаем обратную замену:

\[{\left(x-y+z\right)xy}^5+{\left(x-y+z\right)y}^6-{\left(x-y+z\right)xz}^5\]

В данном выражении мы видим присутствие трех произведений одночленов на многочлен. Найдем их по отдельности по выше изложенному правилу:

\[{\left(x-y+z\right)xy}^5=x{xy}^5-y{xy}^5+z{xy}^5={x^2y}^5-{xy}^6+z{xy}^5\] \[{\left(x-y+z\right)y}^6=xy^6-yy^6+zy^6=xy^6-y^7+zy^6\] \[{\left(x-y+z\right)xz}^5=x{xz}^5-y{xz}^5+z{xz}^5=x^2z^5-xyz^5+{xz}^6\]

Перепишем наше выражение:

\[\left({x^2y}^5-{xy}^6+z{xy}^5\right)+\left(xy^6-y^7+zy^6\right)-(x^2z^5-xyz^5+{xz}^6)\]

Раскроем скобки. Напомним, что если перед скобками стоит знак плюс, то знаки в скобках остаются неизменными, а если перед скобками стоит знак минус, то знаки в скобках изменятся на противоположные. Получим

\[{x^2y}^5-{xy}^6+z{xy}^5+xy^6-y^7+zy^6-x^2z^5+xyz^5-{xz}^6\]

Получили многочлен. Осталось только привести его к стандартному виду. Итого, в ответе, получим:

\[{x^2y}^5+xy^5z-y^7+zy^6-x^2z^5+xyz^5-{xz}^6\]

Присмотревшись к полученному результату, мы получим следующее правило умножения многочлена на многочлен:

Правило: Для того, чтобы умножить многочлен на многочлен, необходимо каждый член первого многочлена умножить на каждый член второго многочлен, сложить полученные произведения и полученный многочлен привести к стандартному виду.

Пример 2

Выполнить умножение $2x+y$ и $x^2+2y+3$.

Запишем произведение:

\[\left(2x+y\right)(x^2+2y+3)\]

\[\left(2x+y\right)\left(x^2+2y+3\right)=2x^3+4xy+6x+x^2y+2y^2+3y\]

Видим, что полученный многочлен имеет стандартный вид, значит умножение закончено.

Примеры задач на произведение многочленов

Пример 3

Выполнить умножение многочлена на многочлен:

а) $(2z+1)\ и\ (z^2-7z-3)$

б) $(1-4x^2)\ и\ (5y^2-3x-2)$

Решение:

а) $(2z+1)\ и\ (z^2-7z-3)$

Составим произведение:

\[(2z+1)\cdot (z^2-7z-3)\]

Раскроем скобки по правилу произведения многочленов:

б) $(1-4x^2)\ и\ (5y^2-3x-2)$

Составим произведение:

\[(1-4x^2)\cdot (5y^2-3x-2)\]

Раскроем скобки по правилу произведения многочленов:

Видим, что полученный многочлен имеет стандартный вид, следовательно:

Ответ: $5y^2-3x-2-20x^2y^2+12x^3+8x^2$.

в) $(2n-5n^3)\ и\ (3n^2-n^3+n)$

Составим произведение:

\[(2n-5n^3)\cdot (3n^2-n^3+n)\]

Раскроем скобки по правилу произведения многочленов:

Приведем данный многочлен к стандартному виду:

г) $(a^2+a+1)\ и\ (a^2-24a+6)$

Составим произведение:

\[(a^2+a+1)\cdot (a^2-24a+6)\]

Раскроем скобки по правилу произведения многочленов:

Приведем данный многочлен к стандартному виду.

Одним из действий с многочленами является умножение многочлена на многочлен. В данной статье рассмотрим правило такого умножения и применим его при решении задач.

Правило умножения многочлена на многочлен

Зададим два многочлена a + b и c + d и выполним их умножение.

В первую очередь запишем произведение исходных многочленов: поставим между ними знак умножения, предварительно заключив многочлены в скобки. Получим: (a + b) · (c + d) . Теперь обозначим множитель (c + d) как x , тогда выражение получит вид: (a + b) · x , что по сути является произведением многочлена и одночлена. Осуществим умножение: (a + b) · x = a · x + b · x , а затем обратно заменим х на (c + d) : a · (c + d) + b · (c + d) . И вновь применив правило умножения многочлена на одночлен, преобразуем выражение в: a · c + a · d + b · c + b · d . Резюмируя: произведению заданных многочленов a + b и c + d соответствует равенство (a + b) · (c + d) = a · c + a · d + b · c + b · d .

Рассуждения, которые мы привели выше, дают возможность сделать важные выводы:

  1. Результат умножения многочлена на многочлен - многочлен. Данное утверждение справедливо для любых перемножаемых многочленов.
  2. Произведение многочленов есть сумма произведений каждого члена одного многочлена на каждый член другого. Откуда можно сделать заключение, что при умножении многочленов, содержащих m и n членов соответственно, указанная сумма произведений членов состоит из m · n слагаемых.

Теперь можем сформулировать правило умножения многочленов:

Определение 1

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

Примеры умножения многочлена на многочлен

В практическом решении задач нахождение произведения многочленов раскладывается на несколько последовательных действий:

  • запись произведения умножаемых многочленов (многочлены заключаются в скобки и между ними записывается знак умножения);
  • выстраивание суммы произведений каждого члена первого многочлена на каждый член второго. С этой целью первый член первого многочлена умножается на каждый член второго многочлена, затем второй член первого многочлена перемножается с каждым членом второго многочлена и так далее;
  • если это возможно, полученная сумма записывается в виде многочлена стандартного вида.
Пример 1

Заданы многочлены: 2 − 3 · x и x 2 − 7 · x + 1

Решение

Запишем произведение исходных многочленов. Получим: (2 − 3 · x) · (x 2 − 7 · x + 1) .

Следующим шагом составим сумму произведений каждого члена многочлена 2 − 3 · x на каждый член многочлена x 2 − 7 · x + 1 . Рассмотрим подробно: умножаем первый член первого многочлена (число 2) на каждый член второго многочлена, получим: 2 · x 2 , 2 · (− 7 · x) и 2 · 1 . Затем умножаем второй член первого многочлена на каждый член второго многочлена и получаем: − 3 · x · x 2 , − 3 · x · (− 7 · x) и − 3 · x · 1 . Все полученные выражения собираем в сумму: 2 · x 2 + 2 · (− 7 · x) + 2 · 1 − 3 · x · x 2 − 3 · x · (− 7 · x) − 3 · x · 1 .

Проверим, не пропустили ли мы произведение каких-либо членов: для этого пересчитаем количество членов в записанной сумме, получим 6 . Это верно, поскольку исходные многочлены состоят из 2 и 3 членов, что в общем дает 6 .

Последним действием преобразуем записанную сумму в многочлен стандартного вида: 2 · x 2 + 2 · (− 7 · x) + 2 · 1 − 3 · x · x 2 − 3 · x · (− 7 · x) − 3 · x · 1 = = 2 · x 2 − 14 · x + 2 − 3 · x 3 + 21 · x 2 − 3 · x = = (2 · x 2 + 21 · x 2) + (− 14 · x − 3 · x) + 2 − 3 · x 3 = 23 · x 2 − 17 · x + 2 − 3 · x 3

Кратко без пояснений решение будет выглядеть так:

(2 − 3 · x) · (x 2 − 7 · x + 1) = 2 · x 2 + 2 · (− 7 · x) + 2 · 1 − 3 · x · x 2 − 3 · x · (− 7 · x) − 3 · x · 1 = = 2 · x 2 − 14 · x + 2 − 3 · x 3 + 21 · x 2 − 3 · x = = (2 · x 2 + 21 · x 2) + (− 14 · x − 3 · x) + 2 − 3 · x 3 = 23 · x 2 − 17 · x + 2 − 3 · x 3

Ответ: (2 − 3 · x) · (x 2 − 7 · x + 1) = 23 · x 2 − 17 · x + 2 − 3 · x 3 .

Уточним, что, когда исходные многочлены заданы в нестандартном виде, перед тем, как найти их произведение, желательно привести их к стандартному виду. Результат, конечно, будет тот же, но решение станет удобнее и короче.

Пример 2

Заданы многочлены 1 7 · x 2 · (- 3) · y + 3 · x - 2 7 · x · y · x и x · y − 1 . Необходимо найти их произведение.

Решение

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

1 7 · x 2 · (- 3) · y + 3 · x - 2 7 · x · y · x = - 3 7 · x 2 + 3 · x - 2 7 · x 2 · y = = - 3 7 · x 2 · y - 2 7 · x 2 · y + 3 · x = - 5 7 · x 2 · y + 3 · x

Теперь найдем искомое произведение:

5 7 · x 2 · y + 3 · x · x · y - 1 = = - 5 7 · x 2 · y · x · y - 5 7 · x 2 · y · (- 1) + 3 · x · x · y + 3 · x · (- 1) = = - 5 7 · x 3 · y 2 + 5 7 · x 2 · y + 3 · x 2 · y - 3 · x = - 5 7 · x 3 · y 2 + 3 5 7 · x 2 · y - 3 · x

Ответ: - 5 7 · x 2 · y + 3 · x · x · y - 1 = - 5 7 · x 3 · y 2 + 3 5 7 · x 2 · y - 3 · x

Напоследок проясним ситуацию, в которой есть необходимость перемножить три и более многочленов. В этом случае нахождение произведения сводится к последовательному перемножению многочленов по два: т.е. сначала перемножаются первые два многочлена; полученный результат умножается на третий многочлен; итог этого умножения – на четвертый многочлен и так далее.

Пример 3

Заданы многочлены: x 2 + x · y − 1 , x + y и 2 · y − 3 . Необходимо найти их произведение.

Решение

Сделаем запись произведения: (x 2 + x · y − 1) · (x + y) · (2 · y − 3) .

Перемножим первые два многочлена, получим: (x 2 + x · y − 1) · (x + y) = x 2 · x + x 2 · y + x · y · x + x · y · y − 1 · x − 1 · y = = x 3 + 2 · x 2 · y + x · y 2 − x − y .

Первоначальная запись произведения принимает вид: (x 2 + x · y − 1) · (x + y) · (2 · y − 3) = (x 3 + 2 · x 2 · y + x · y 2 − x − y) · (2 · y − 3) .

Найдем результат этого умножения:

(x 3 + 2 · x 2 · y + x · y 2 − x − y) · (2 · y − 3) = = x 3 · 2 · y + x 3 · (− 3) + 2 · x 2 · y · 2 · y + 2 · x 2 · y · (− 3) + x · y 2 · 2 · y + + x · y 2 · (− 3) − x · 2 · y − x · (− 3) − y · 2 · y − y · (− 3) = = 2 · x 3 · y − 3 · x 3 + 4 · x 2 · y 2 − 6 · x 2 · y + 2 · x · y 3 - − 3 · x · y 2 − 2 · x · y + 3 · x − 2 · y 2 + 3 · y

Ответ:

(x 2 + x · y − 1) · (x + y) · (2 · y − 3) = 2 · x 3 · y − 3 · x 3 + 4 · x 2 · y 2 − 6 · x 2 · y + + 2 · x · y 3 − 3 · x · y 2 − 2 · x · y + 3 · x − 2 · y 2 + 3 · y

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ - это алгоритм, вычисляющий значения многочлена степени n =2 k в некоторых n точках за время O (n ⋅logn ) («наивный» метод выполняет ту же задачу за время O (n 2 )). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.

Определения и способы применения

Для начала давайте определимся, что такое многочлен:
P (x )=a 0 +x a 1 +x 2 a 2 +x 3 a 3 +... +x n -1 a n -1

Комплексные числа

Если Вы знакомы с комплексными числами, то можете пропустить этот пункт, в противном случае, вот краткое определение:
x =a +i b , где i 2 =-1
Здесь a называется вещественной (Real ) частью, а b - мнимой (Imaginary ). В этих числах, как нетрудно заметить, можно извлекать корень из отрицательных (да и вообще любых) чисел - это очень удобно при работе с многочленам - как следует из основной теоремы алгебры, у каждого многочлена степени n имеется ровно n комплексных корней (с учётом кратности).
Также их очень удобно представлять в виде точек на плоскости:

Еще одним замечательным свойством комплексных чисел является то, что их можно представить в виде x =(cosα+i sinα)r , где α - полярный угол «числа» (называется аргументом ), а r - расстояние от нуля до него (модуль ). А при умножении двух чисел:
a =(cosα+i ⋅sinα)r a
b =(cosβ+i ⋅sinβ)r b
a b =(cosα+i ⋅sinα)(cosβ+i ⋅sinβ)r a r b
a b =(cosα⋅cosβ-sinα⋅sinβ+i (sinα⋅cosβ+cosβ⋅sinα))r a r b
a b =(cos(α+β)+i ⋅sin(α+β))r a r b
Их модули перемножаются, а аргументы складываются.

Комплексные корни из 1

Теперь давайте поймём, как выглядят комплексные корни n -ой степени из 1 . Пусть x n =1 , тогда его модуль, очевидно, равен единице, а n ⋅argx =2 πk , где k - целое. Это обозначает, что после n умножений числа на самого себя (т.е. возведения в n -ю степень) его аргумент станет «кратен» 2 π (360 градусам).
Вспомним формулу числа, если известен аргумент и модуль, получаем:
α=2 π⋅x /n , где 0 x
ω i =cosα+i ⋅sinα
Т.е. если порисовать, то мы получим просто точки на окружности через равные промежутки:

Прошу заметить три вещи, которыми мы будем активно пользоваться (без них ничего не получится):
ω a ⋅ω b =ω (a +b )modn
ω 0 +ω 1 +ω 2 +... +ω n -1 =0
ω 0 n /2 =ω 2 n /2 =ω 4 n /2 =... =1 (при чётном n )
Из-за этих свойств именно в этих точках мы и будем считать значение многочлена. Разумеется, результаты необязательно будут вещественными, поэтому в программе потребуется работать с комплексными числами.

Почему сумма корней - ноль

Доказательство очень простое: пусть φ=ω 0 +ω 1 +... . Домножим обе части на ω 1 (!= 1). Т.к. ω i ⋅ω 1 =ω i +1 , то φ⋅ω 1 =ω 1 +ω 2 +... +ω n -1 +ω 0 . От перестановки слагаемых сумма не меняется, поэтому φ=φ⋅ω 1 , соответственно φ⋅(ω 1 -1 )=0 . Т.к. ω 1 != 1, то φ=0 .

Как работает

Будем считать, что наш многочлен имеет степень n =2 k . Если нет, дополним старшие коэффициенты нулями до ближайшей степени двойки.
Основная идея БПФ очень проста:
Пусть:
A (x )=a 0 +x a 2 +x 2 a 4 +... +x n /2 -1 a n -2 (четные коэффициэнты P )
B (x )=a 1 +x a 3 +x 2 a 5 +... +x n /2 -1 a n -1 (нечётные коэффициенты P ).
Тогда P (x )=A (x 2 )+x ⋅B (x 2 ).
Теперь применим принцип «разделяй и властвуй»: чтобы посчитать значения P в n точках (ω 0 ,ω 1 ,... ), посчитаем значения A и B рекурсивно в n /2 точках (ω 0 ,ω 2 ,... ). Теперь значение P (ω i ) восстановить достаточно просто:
P (ω i )=A (ω 2 i )+ω i ⋅B (ω 2 i )
Если обозначить за ξ i =ω 2 i точки, в которых мы считаем значения многочлена степени n /2 , формула преобразится:
P (ω i )=A (ξ i )+ω i ⋅B (ξ i )
Её уже можно загонять в программу, не забыв что i принимает значения от 0 до n -1 , а ξ i определено лишь от 0 до n /2 -1 . Вывод - надо будет взять i по модулю n /2 .
Время работы выражается рекуррентной формулой T (n )=O (n )+2 T (n /2 ). Это довольно известное соотношение и оно раскрывается в O (n ⋅log 2 n ) (грубо говоря, глубина рекурсии - log 2 n уровней, на каждом уровне суммарно по всем вызовам выполняется O (n ) операций).

Напишем что-нибудь

Вот пример неэффективной рекурсивной реализации БПФ:
Slow FFT
#include #include using namespace std; typedef complex cd; // STL-ное комплексное число. Нам нужен double, ведь мы работает с sin и cos typedef vector vcd; vcd fft(const vcd &as) { // Возвращает вектор значений в корнях из 1 int n = as.size(); // Когда-то же надо прекратить рекурсию? if (n == 1) return vcd(1, as); vcd w(n); // Считаем корни for (int i = 0; i < n; i++) { double alpha = 2 * M_PI * i / n; w[i] = cd(cos(alpha), sin(alpha)); } // Считаем коэффициенты A и B vcd A(n / 2), B(n / 2); for (int i = 0; i < n / 2; i++) { A[i] = as; B[i] = as; } vcd Av = fft(A); vcd Bv = fft(B); vcd res(n); for (int i = 0; i < n; i++) res[i] = Av + w[i] * Bv; return res; }
Можете добавить ввод-вывод и проверить правильность своей реализации. Для многочлена P (x )=4 +3 x +2 x 2 +x 3 +0 ⋅x 4 +0 ⋅x 5 +0 ⋅x 6 +0 ⋅x 7 значения должны получиться такими:
P (w 0 )=(1 0 .0 0 0 ,0 .0 0 0 )
P (w 1 )=(5 .4 1 4 ,4 .8 2 8 )
P (w 2 )=(2 .0 0 0 ,2 .0 0 0 )
P (w 3 )=(2 .5 8 6 ,0 .8 2 8 )
P (w 4 )=(2 .0 0 0 ,0 .0 0 0 )
P (w 5 )=(2 .5 8 6 ,-0 .8 2 8 )
P (w 6 )=(2 .0 0 0 ,-2 .0 0 0 )
P (w 7 )=(5 .4 1 4 ,-4 .8 2 8 )
Если это так - можете засекать время рекурсивного и наивного метода на больших тестах.
У меня на многочлене степени 2 12 эта реализация работает 62 мс, наивная - 1800 мс. Разница налицо.

Избавляемся от рекурсии

Для того, чтобы сделать процедуру нерекурсивной, придётся подумать. Легче всего, как мне кажется, провести аналогию с MergeSort (сортировка слиянием) и нарисовать картинку, на которой показаны все рекурсивные вызовы:


Как мы видим, можно сделать один массив, заполнить его изначально значениями fft(a 0 ), fft(a 4 ), fft(a 2 ), ... . Как несложно понять, номера a i - это «развёрнутые» в двоичном представлении числа 0 ,1 ,2 ,3 ,... . Например, 1 1 0 =0 0 1 2 ,4 1 0 =1 0 0 2 или 6 =1 1 0 2 ,3 =0 1 1 2 . Понять это можно следующим образом: при спуске на нижний уровень рекурсии у нас определяется еще один младший бит (с конца). А при «нормальной» нумерации бит определяется с начала. Поэтому нужно «развернуть» число. Это можно сделать «в лоб» за O (n ⋅log 2 n ), а можно динамическим программированием за O (n ) по следующему алгоритму:
  1. Пробежимся циклом от 0 до n -1
  2. Будем хранить и динамически пересчитывать номер старшего единичного бита числа. Он меняется, только когда текущее число - степень двойки: увеличивается на 1.
  3. Когда мы знаем старший бит числа, перевернуть всё число не составляет труда: «отрезаем» старший бит (XOR), переворачиваем остаток (уже посчитанное значение) и добавляем «отрезанную» единицу
Теперь придумаем алгоритм, позволяющий нам из «ступеньки» получить ступеньку повыше. Хранить все значения с предыдущего шага мы будем в одном массиве. Как хорошо видно на рисунке, надо обрабатывать данные блоками по k , причём вначале k =1 , а потом с каждым шагом увеличивается вдвое. Мы обрабатываем два блока длиной k и получаем на выходе один блок длиной 2 k . Давайте на примере разберём, как это делалось рекурсивно, вспомним формулу из начала статьи и повторим:

Аргументами процедуры для слияния двух блоков будут два vector"а (естесственно, по ссылке, исходный и результат), номер стартового элемента первого блока (второй идёт сразу после) и длина блоков. Можно было бы конечно сделать и iterator"ами - для большей STL"ности, но мы ведь всё равно будем переносить эту процедуру внутрь основной для краткости.
Объединение блоков
void fft_merge(const vcd &src, vcd &dest, int start, int len) { int p1 = start; // Позиция в первом блоке int en1 = start + len; // Конец первого блока int p2 = start + len; // Позиция во втором блоке int en2 = star + len * 2; // Конец второго блока int pdest = start; // Текущая позиция в результатирующем массиве int nlen = len * 2; // Длина нового блока for (int i = 0; i < nlen; i++) { double alpha = 2 * M_PI * i / nlen; cd w = cd(cos(alpha), sin(alpha)); // Текущий корень dest = src + w * src; if (++p1 >= en1) p1 = start; if (++p2 >= en2) p2 = start + len; } }
И основная процедура преобразования:
<< k) < n) k++; vi rev(n); rev = 0; int high1 = -1; for (int i = 1; i < n; i++) { if ((i & (i - 1)) == 0) // Проверка на степень двойки. Если i ей является, то i-1 будет состоять из кучи единиц. high1++; rev[i] = rev; // Переворачиваем остаток rev[i] |= (1 << (k - high1 - 1)); // Добавляем старший бит } vcd cur(n); for (int i = 0; i < n; i++) cur[i] = as]; for (int len = 1; len < n; len <<= 1) { vcd ncur(n); for (int i = 0; i < n; i += len * 2) fft_merge(cur, ncur, i, len); cur.swap(ncur); } return cur; }

Оптимизация

На многочлене степени 2 1 6 рекурсия работает 640 мс, без рекурсии - 500. Улучшение есть, но программу можно сделать еще быстрее. Воспользуемся тем свойством, что ω i =-ω i +n /2 . Значит, можно не считать два раза корень и a i ⋅ω j - синус, косинус и умножение комплексных чисел очень затратные операции.
fft_merge()
for (int i = 0; i < len; i++) { double alpha = 2 * M_PI * i / nlen; cd w = cd(cos(alpha), sin(alpha)); // Текущий корень cd val = w * src; dest = src + val; dest = src - val; pdest++; if (++p1 >= en1) p1 = start; if (++p2 >= en2) p2 = start + len; }
Перехо с такой оптимизацией называется «преобразованием бабочки». Программа стала работать 260 мс. Для закрепления успеха давайте предподсчитаем все корни из 1 и запишем их в массив:
fft_merge()
int rstep = roots.size() / nlen; // Шаг в массиве с корнями for (int i = 0; i < len; i++) { cd w = roots; cd val = w * src;
fft()
roots = vcd(n); for (int i = 0; i < n; i++) { double alpha = 2 * M_PI * i / n; roots[i] = cd(cos(alpha), sin(alpha)); }
Теперь скорость работы - 78 мс. Оптимизация в 8 раз по сравнению с первой реализацией!

Оптимизация по коду

На данный момент весь код преобразования занимает порядка 55 строк. Не сотню, но это достаточно много - можно короче. Дляначала избавимся от кучи лишних переменных и операций в fft_merge :
void fft_merge(const vcd &src, vcd &dest, int start, int len) { int p1 = start; //int en1 = start + len; // Не используется, см. конец цикла int p2 = start + len; //int en2 = start + len * 2; // Аналогично int pdest = start; //int nlen = len * 2; // Используется только в следующей строчке //int rstep = roots.size() / nlen; int rstep = roots.size() / (len * 2); for (int i = 0; i < len; i++) { //cd w = roots; // Также используется только в следующей строчке //cd val = w * src; cd val = roots * src; dest = src + val; dest = src - val; pdest++, p1++, p2++; //if (++p1 >= en1) p1 = start; // Так как у нас теперь цикл не до 2len, а только до len, переполнения быть не может //if (++p2 >= en2) p2 = start + len; // Убираем } }
Теперь можно переместить цикл из fft_merge в основную процедуру (также можно убрать p2 , поскольку p2=p1+len - у меня это также дало небольшой выигрыш по времени. Что любопытно, если убрать p1=pdest , то у меня лично выигрыш по времени убивается):
fft()
for (int len = 1; len < n; len <<= 1) { vcd ncur(n); int rstep = roots.size() / (len * 2); for (int pdest = 0; pdest < n;) { int p1 = pdest; for (int i = 0; i < len; i++) { cd val = roots * cur; ncur = cur + val; ncur = cur - val; pdest++, p1++; } pdest += len; } cur.swap(ncur); }
Как видите, само преобразование занимает не так много - 17 строк. Всё остальное - предподсчёт корней и разворот чисел. Если Вы готовы сэкономить код в обмен на время работы (O (n ⋅log 2 n ) вместо O (n )), можете заменить 13 строк разворота чисел на следующие шесть:
В начале процедуры fft()
vcd cur(n); for (int i = 0; i < n; i++) { int ri = 0; for (int i2 = 0; i2 < k; i2++) // Перебираем биты от младших к старшим ri = (ri << 1) | !!(i & (1 << i2)); // И приписываем в конец числа cur[i] = as; }
В результате теперь код выглядит так:
vcd fft(const vcd &as) { int n = as.size(); int k = 0; // Длина n в битах while ((1 << k) < n) k++; vector rev(n); rev = 0; int high1 = -1; for (int i = 1; i < n; i++) { if ((i & (i - 1)) == 0) // Проверка на степень двойки. Если i ей является, то i-1 будет состоять из кучи единиц. high1++; rev[i] = rev; // Переворачиваем остаток rev[i] |= (1 << (k - high1 - 1)); // Добавляем старший бит } vcd roots(n); for (int i = 0; i < n; i++) { double alpha = 2 * M_PI * i / n; roots[i] = cd(cos(alpha), sin(alpha)); } vcd cur(n); for (int i = 0; i < n; i++) cur[i] = as]; for (int len = 1; len < n; len <<= 1) { vcd ncur(n); int rstep = roots.size() / (len * 2); for (int pdest = 0; pdest < n;) { int p1 = pdest; for (int i = 0; i < len; i++) { cd val = roots * cur; ncur = cur + val; ncur = cur - val; pdest++, p1++; } pdest += len; } cur.swap(ncur); } return cur; }

Обратное преобразование

Получить значения многочлена в точках - это, конечно, хорошо, но преобразование Фурье умеет больше - по этим значениям построить сам многочлен, причём за то же самое время! Оказывается, что если применить преобразование Фурье к массиву значений, как к коэффициентам многочлена, потом разделить результат на n и перевернуть отрезок с 1 до n -1 (нумерация с 0 ), то мы получим коэффициенты исходного многочлена.
Код тут предельно простой - всё уже написано. Думаю, Вы справитесь.

Доказательство

Пусть мы применяем обратное преобразование к многочлену P (x ) с коэффициентами v i (исходный многочлен имел коэффициенты a i ):
v i =a 0 +ω i a 1 +ω 2 i a 2 +ω 3 i a +...
Посмотрим на результат преобразования:
b i =v 0 +ω i v 1 +ω 2 i v 2 +ω 3 i v 3 +...
Подставим значения v j (помним, что ω a ω b =ω a +b m o d n :

Теперь давайте докажем один замечательный факт: при x ≠0 , ω 0 +ω x +ω 2 x +... +ω (n -1 )x =0 .
Доказывается аналогично тому, что сумма корней - ноль: обозначим за φ сумму, домножим обе части на ω x и посмотрим, что получилось.
Теперь применим этот факт к вычислению значения b i . Заметим, что все строки, кроме одной, в которой содержится a n -i , обнулятся.

Таким образом:

b i =a n -i ⋅(ω 0 +ω 0 +ω 0 +ω 0 +... )

b i =a n -i ⋅n

Что и требовалось доказать.

Применение

Вообще говоря, о применении я уже чуть-чуть говорил в начале статьи. В частности, теперь перемножение многочленов можно выполнять следующим образом:
Быстрое перемножение многочленов
vcd a, b; // Многочлены // Чтение многочленов vcd a_vals = fft(a); vcd b_vals = fft(b); vcd c_vals(a_vals.size()); for (int i = 0; i < a_vals.size(); i++) c_vals[i] = a_vals[i] * b_vals[i]; vcd c = fft_rev(c_vals); // Вывод ответа
Легко заметить, что время работы этой программы - O (n ⋅log 2 n ) и самые трудоёмкие операции - преобразования Фурье. Также можно заметить, что если нам требуется вычислить более сложное выражение с двумя многочленами, то по-прежнему можно выполнять лишь три приобразования - сложение и вычитание также будут работать за линейное время. К сожалению, с делением не всё так просто, поскольку многочлен может случайно принять значение 0 в какой-нибудь из точек. UPD2: не забудьте, что степень произведения двух многочленов степени n будет равна 2n , поэтому при вводе следует добавить «лишние» нулевые старшие коэффициенты.
Если представить число в десятичной (или более) системе счисления, как многочлен с коэффициентами - цифрами, то умножение длинных чисел также можно выполнять очень быстро.
И, напоследок, задача, которую я разберу в следующем посте: у вас есть две строки одинаковой длины порядка 1 0 5 из букв A, T, G, C. Требуется найти такой циклический сдвиг одной из строк, чтобы совпало максимальное количество символов. Очевидно наивное решение за O (n 2 ), но есть решение при помощи БПФ.
Удачи!

UPD: Выложил код целиком на











Назад Вперёд

Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.

Цели урока: (Презентация. Слайд 2)

Образовательные:

  • вывести правило умножения многочлена на многочлен;
  • формировать умение применять это правило.

Развивающие:

  • развитие внимания;
  • формирование умения анализировать и обобщать знания по теме;
  • развитие навыков устного счёта.

Воспитательные:

  • воспитание аккуратности;
  • воспитание устойчивого интереса к предмету.

Тип урока: Урок изучения и первичного закрепления новых знаний.

Ход урока

I. Устная работа (Презентация. Слайд 3)

Выполните умножение.

а) а (х – у);

б) 2p (3 – q);

в) –2х (х – 4);

г) 4y(у 3 + 0,25);

д) – 0,5 c 2 (c 3 + 2);

е) –5х (3х 2 – 4);

ж) 2a 4 (а 3 – 0,5);

з) –q 7 (q 3 – q 5).

II. Объяснение нового материала (Презентация. Слайд 4)

Объяснение проводится в несколько этапов согласно материалу учебника.

1. Вывести правило умножения многочлена на многочлен и наглядно представить его на слайде (или доске):

2. Сформулировать полученное правило, попросить нескольких учащихся повторить его.

3. Разобрать примеры применения правила.

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

Пример 1. (Презентация. Слайд 5) Умножить многочлен (3a – 2b) на многочлен (2a + 3b).

Решение: (3a – 2b)(2a + 3b) = 3a * 2a + 3a * 3b + (– 2b) * 2a + (– 2b) * 3b = 6a 2 + 9ab – 4 ab – 6b 2 = 6a 2 + 5ab – 6b 2 .

Пример 2. (Презентация. Слайд 6) Упростите выражение: (2х – 3)(5 – х) – 3х(4 – х).

Решение: (2х – 3)(5 – х) – 3х(4 – х) = 10х – 2х 2 – 15 + 3х – 12х + 3х 2 = х 2 + х – 15.

Пример 3. (Презентация. Слайд 7) Докажем, что при любом натуральном значении п значение выражения (п + 1)(п + 2) – (3п – 1)(п + 3) + 5п(п + 2) + п +7 кратно 3.

Решение: (п + 1)(п + 2) – (3п – 1)(п + 3) + 5п(п + 2) + п +7 = п 2 + 2п + п + 2 – 3п 2 – 9п + п + 3 + 5п 2 + 10п + п +7 = 3п 2 + 6п + 12 = 3 (п 2 + 2п + 4).

III. Формирование умений и навыков (Презентация. Слайд 8)

За урок следует опросить как можно больше учащихся, чтобы убедиться, что они усвоили правило умножения многочлена на многочлен. Поэтому для выполнения каждого задания к доске можно вызывать сразу трёх учащихся.

1. № 677, № 678.

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

2. № 680.

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

в) 12a 4 – a 2 b 2 – b 4 ;

е) 56p 3 – 51p 2 + 10p.

3. № 682 (а, в).

а) (х + 10) 2 = (х + 10) (х + 10) = х 2 + 10х + 10х + 100 = х 2 + 20х + 100;

в) (3а – 1) 2 = (3а – 1) (3а – 1) = 9а 2 – 3а – 3а – 1 = 9а 2 – 6а + 1.

IV. Итоги урока (Презентация. Слайд 9)

– Как умножить одночлен на многочлен?

– Сформулируйте правило умножения многочлена на многочлен.

– Какие знаки будут иметь слагаемые, полученные при умножении многочленов:

а) (х + у) (а – b);

б) (n – m) (p – q)?

V. Домашнее задание: (Презентация. Слайд 10)

№ 679; № 681; № 682 (б, г).

Используемые учебники и учебные пособия: (Презентация. Слайд 11)

  1. Учебник “Алгебра 7”. Ю.Н.Макарычев, Н.Г.Миндюк, К.И.Нешков, С.Б.Суворова под редакцией С.А.Теляковского. Москва “Просвещение”.2010г.
  2. Рурукин А.Н., Лупенко Г.В., Масленникова И.А. Поурочные разработки по алгебре: 7 класс.

Использованное оформление.


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

Навигация по странице.

Правило

Чтобы подойти к правилу умножения многочлена на многочлен, рассмотрим пример. Возьмем два многочлена a+b и c+d и выполним их умножение.

Сначала составим их произведение, для этого заключим каждый из многочленов в скобки, и поставим между ними знак умножения, имеем (a+b)·(c+d) . Теперь обозначим (c+d) как x , после этой замены записанное произведение примет вид (a+b)·x . Выполним умножение так, как проводится умножение многочлена на одночлен : (a+b)·x=a·x+b·x . На этом этапе проведем обратную замену x на c+d , что нас приведет к выражению a·(c+d)+b·(c+d) , которое с помощью правила умножения одночлена на многочлен преобразуется к виду a·c+a·d+b·c+b·d . Таким образом, умножению исходных многочленов a+b и c+d соответствует равенство (a+b)·(c+d)=a·c+a·d+b·c+b·d .

Из проведенных рассуждений можно сделать два важных вывода. Во-первых, результатом умножения многочлена на многочлен является многочлен. Это утверждение справедливо для любых умножаемых многочленов, а не только для тех, которые мы взяли в примере. Во-вторых, произведение многочленов равно сумме произведений каждого члена одного многочлена на каждый член другого. Отсюда следует, что при умножении многочленов, содержащих m и n членов соответственно, указанная сумма произведений членов будет состоять из m·n слагаемых.

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

Примеры умножения многочлена на многочлен

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

  • Так сначала записывается произведение умножаемых многочленов. При этом умножаемые многочлены заключаются в скобки и между ними ставится знак «· ».
  • Дальше строится сумма произведений каждого члена первого многочлена на каждый член второго. Для этого берется первый член первого многочлена и умножается на каждый член второго многочлена. После этого берется второй член первого многочлена и тоже умножается на каждый член второго многочлена. И так далее.
  • Наконец, при возможности остается полученную сумму преобразовать в многочлен стандартного вида .

Разберемся с этим на конкретном примере.

Пример.

Выполните умножение многочленов 2−3·x и x 2 −7·x+1 .

Решение.

Записываем произведение: (2−3·x)·(x 2 −7·x+1) .

Теперь составляем сумму произведений каждого члена многочлена 2−3·x на каждый член многочлена x 2 −7·x+1 . Для этого берем первый член первого многочлена, то есть, 2 , и умножаем его на каждый член второго многочлена, имеем 2·x 2 , 2·(−7·x) и 2·1 . Теперь берем второй член первого многочлена −3·x и умножаем его на каждый член второго многочлена, имеем −3·x·x 2 , −3·x·(−7·x) и −3·x·1 . Из всех полученных выражений составляем сумму: 2·x 2 +2·(−7·x)+2·1− 3·x·x 2 −3·x·(−7·x)−3·x·1 .

Чтобы убедиться, что мы все сделали правильно и не забыли про произведение каких-нибудь членов, посчитаем количество членов в полученной сумме. Там их 6 . Так и должно быть, так как исходные многочлены состоят из 2 и 3 членов, а 2·3=6 .

Осталось полученную сумму преобразовать в многочлен стандартного вида:
2·x 2 +2·(−7·x)+2·1− 3·x·x 2 −3·x·(−7·x)−3·x·1= 23·x 2 −17·x+2−3·x 3 .

Таким образом, умножение исходных многочленов дает многочлен 23·x 2 −17·x+2−3·x 3 .

Удобно решение записывать в виде цепочки равенств, которая отражает все выполняемые действия. Для нашего примера краткое решение выглядит так:
(2−3·x)·(x 2 −7·x+1)= 2·x 2 +2·(−7·x)+2·1− 3·x·x 2 −3·x·(−7·x)−3·x·1= 2·x 2 −14·x+2−3·x 3 +21·x 2 −3·x= (2·x 2 +21·x 2)+(−14·x−3·x)+2−3·x 3 = 23·x 2 −17·x+2−3·x 3 .

Ответ:

(2−3·x)·(x 2 −7·x+1)=23·x 2 −17·x+2−3·x 3 .

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

Пример.

Выполните умножение многочленов и x·y−1 .

Решение.

Многочлен дан не в стандартном виде. Прежде чем выполнять умножение, приведем многочлен его к стандартному виду:

Теперь можно выполнять умножение многочленов:

Ответ:

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

Пример.

Найдите произведение трех многочленов x 2 +x·y−1 , x+y и 2·y−3 .

Список литературы.

  • Алгебра: учеб. для 7 кл. общеобразоват. учреждений / [Ю. Н. Макарычев, Н. Г. Миндюк, К. И. Нешков, С. Б. Суворова]; под ред. С. А. Теляковского. - 17-е изд. - М. : Просвещение, 2008. - 240 с. : ил. - ISBN 978-5-09-019315-3.
  • Мордкович А. Г. Алгебра. 7 класс. В 2 ч. Ч. 1. Учебник для учащихся общеобразовательных учреждений / А. Г. Мордкович. - 17-е изд., доп. - М.: Мнемозина, 2013. - 175 с.: ил. ISBN 978-5-346-02432-3.
  • Алгебра и начала математического анализа. 10 класс: учеб. для общеобразоват. учреждений: базовый и профил. уровни / [Ю. М. Колягин, М. В. Ткачева, Н. Е. Федорова, М. И. Шабунин]; под ред. А. Б. Жижченко. - 3-е изд. - М.: Просвещение, 2010.- 368 с. : ил. - ISBN 978-5-09-022771-1.
  • Гусев В. А., Мордкович А. Г. Математика (пособие для поступающих в техникумы): Учеб. пособие.- М.; Высш. шк., 1984.-351 с., ил.
Разделы