Преобразование произведения многочленов в многочлен стандартного вида. Какие преобразования целых выражений возможны? Почему сумма корней - ноль
«Совершенствование вычислительных навыков» - Состав числа. Повторение действий. Умножение. Сложение. Правила раскрытия скобок. Cложение отрицательных чисел. Вычитание. Сложение обыкновенных дробей. Сложение чисел с разными знаками. Совершенствование вычислительных навыков. Вычитание однозначного числа. Опорная схема. Действие в столбик. Умножение одночлена на многочлен.
«Разность квадратов чисел» - Возведите в квадрат. Формула сокращенного умножения. Разность квадратов двух выражений. Работа с таблицей. Разность квадратов. Геометрический смысл формулы. Как можно прочитать формулу. Выполните умножение. Влияет ли порядок записи скобок на результат. Формула (а+b)(a-b)=a2-b2. Произведение разности двух выражений и их суммы.
«Умножение многочлена на многочлен» - Правило умножения многочлена на многочлен. Игра «Открой картинку». Открой картинку. Каждый член первого многочлена поочерёдно умножать на каждый член второго многочлена. Рассмотрим произведение самых простых многочленов, а именно двучленов. У одного многочлена m членов, а у другого n членов. План урока.
«Разложение многочлена на множители» - Предварительное преобразование. Провести классификацию данных многочленов по способу разложения на множители. Вынесение общего множителя за скобки. Применение формул сокращенного умножения. Метод выделения полного квадрата. Тестор. Ответы: Схема урока: Конфуций. Формулы сокращенного умножения. Способ группировки.
«Преобразование целого выражения в многочлен» - Какие из выражений являются целыми: Примерами целых выражений служат такие выражения: Цели урока: Упражнять учащихся в приведении подобных слагаемых. Многочлены и, в частности, одночлены являются целыми выражениями. Развивать вычислительные навыки учащихся. Ввести понятие целого выражения. Преобразование целых выражений.
«Урок Формулы сокращённого умножения» - Цель урока: Повторить и обобщить практические навыки и умения по теме «Формулы сокращённого умножения». Тема урока: ФОРМУЛЫ СОКРАЩЁННОГО УМНОЖЕНИЯ. Подготовиться к предстоящей контрольной работе. Задача: Стороны первого квадрата на 1 см больше сторон второго квадрата, а площадь первого квадрата на 9см2 больше площади второго квадрата.
Всего в теме 24 презентации
Многочленом называется сумма одночленов, то есть произведений цифр и переменных. Работать с ним удобнее, так как чаще всего преобразование выражения в многочлен позволяет значительно упростить его.
Инструкция
Раскройте все скобки выражения. Для этого воспользуйтесь формулами, например, (а+b)^2=a^2+2ab+b^2. Если вы не знаете формул, или их трудно применить к данному выражению, раскрывайте скобки последовательно. Для этого умножайте первый член первого выражения на каждый член второго выражения, затем второй член первого выражения на каждый член второго и т.д. В результате все элементы обоих скобок будут перемножены между собой.
Если перед вами три выражения в скобках, сначала перемножьте первые две, оставляя третье выражение не тронутым. Упростив результат, получившийся в результате преобразования первых скобок, перемножьте его с третьим выражением.
Внимательно следите за соблюдением знаков перед множителями-одночленами. Если вы перемножаете два члена с одним знаком (например, оба положительны или оба отрицательны), одночлен будет со знаком «+». Если же один член имеет перед собой «-», не забудьте перенести его на произведение.
Приведите все одночлены к стандартному виду. То есть переставьте местами множители внутри и упростите. Например, выражение 2х*(3,5х) будет равно (2*3,5)*х*х=7х^2.
Когда все одночлены будут стандартизированы, попробуйте упростить многочлен. Для этого сгруппируйте члены, у которых одинакова часть с переменными, например, (2х+5х-6х)+(1-2). Упростив выражение, вы получите х-1.
Обратите внимание на наличие параметров в выражении. Иногда упрощение многочлена необходимо производить так, будто параметр является числом.
Чтобы преобразовать в многочлен выражение, содержащее корень, выведите под ним такое выражение, которое будет возведено в квадрат. Например, воспользуйтесь формулой a^2+2ab+b^2 =(а+b)^2, затем уберите знак корня вместе с четной степенью. Если избавиться от знака корня невозможно, преобразовать выражение в многочлен стандартного вида не удастся.
Цель урока: систематизировать знания и умения учащихся применять формулы квадрата разности, суммы и разности квадратов для преобразования многочленов.
Задачи урока:
- общеобразовательная: отработка навыков и умений по преобразованию многочленов с помощью формул сокращенного умножения посредством решения письменных и устных упражнений;
- развивающая: развивать познавательный интерес, продолжать формирование математической речи, вырабатывать умение анализировать и сравнивать;
- воспитательная: воспитывать умение выслушивать других и умение общаться.
Мотивационная задача: создать ситуацию успеха на уроке через похвалу, стимулирование слабых и сильных ответов.
Организационные формы общения: коллективная, групповая, индивидуальная.
Ход урока
1-й этап. Организационный момент.
2-й этап. Мотивационная беседа с учащимися с последующей постановкой цели и темы.
Учитель: Ребята, последние несколько уроков мы с вами посвятили изучению трех формул сокращенного умножения. Какие это формулы?
Впереди у нас еще четыре формулы.
Но сегодня я предлагаю вам поработать с этими формулами и еще раз выяснить, насколько хорошо вы разобрались в данной теме.
А начать работу я хотела бы со строк мудрого Конфуция:
Три пути ведут к знанию:
Путь размышления – это путь самый благородный,
Путь подражания – это путь самый легкий и
Путь опыта – это путь самый горький.
Подумайте и решите для себя, ребята, по какому пути вы пойдете сегодня на уроке – это будет ваш личный выбор.
3-й этап. Актуализация опорных знаний.
Учитель: чтобы работа велась успешнее, давайте вспомним и повторим формулы квадрата суммы, разности двух чисел, разности квадратов.
Попрошу выйти к доске двоих учащихся.
Попрошу выйти к доске двух учащихся.
Задание первому ученику: доказать равенство Диофанта
(а + b)(с + d) = (ac + ab)+(bc – ad).
Задание второму ученику: оформить опорную таблицу (магнитная доска).
Собрать из отдельных фрагментов три формулы:
(a + b) 2 = a + 2ab + b
(a – b) 2 = a – 2ab + b
a 2 – b 2 = (a – b)(a + b)
Фронтальная работа с учащимися.
Учитель: А мы, ребята, в это время давайте повторим правила сложения и вычитания рациональных чисел, т. к. это нам понадобится в дальнейшем на уроке.
Карточка:
-/10+5/ -5;
-/(-a +b)/ + b;
-/20*3/: (-12).
Учитель: Ребята, давайте проверим формулы на магнитной доске.
А теперь, применяя данные формулы, выполните устно следующие задания.
Замените * одночленами так, чтобы полученное равенство было тождеством:
- (* + b) 2 = 4c 2 + * + b 2 ;
- (k – *) 2 = * – * + c 2 ;
- (* + 7c) (7c – *) = 49c 2 – 81a 2
- Вычислить:
106 2 – 6 2
71 2 – 61 2 - А в следующем задании нужно проверить, правильно ли выделен полный
квадрат:
а 2 + 2а + 2 = (а + 1) 2 + 2
Учитель : Ребята давайте вернемся к доказательству равенства Диофанта и проверим его.
Предлагаю вам записать себе в тетрадь это равенство и проверить его для первых четырех последовательных чисел _(1.2.3.4).
4-й этап. Работа по теме урока.
Учитель: Ребята, чем воспользовался ученик, доказывающий равенство Диофанта?
А где еще находят применение формулы сокращенного умножения?
Давайте решим следующую задачу у доски.
Сторона квадрата равна а см. Длина прямоугольника на 2 см больше стороны квадрата, а ширина на 2 см меньше стороны квадрата. Найдите площадь прямоугольника и сравните ее с площадью квадрата.
5-й этап. Физкультминутка.
6-й этап. Работа в группах “Звездная карта”.
Учитель: Итак, ребята, раз сегодня мы упомянули ли о Диофанте (доказали его равенство), вспомните, чем он занимался в основном? (Уравнениями).
Хорошо! Я предлагаю сейчас вам тоже решить в группах по 5 уравнений, в которых можно будет применить формулы сокращенного умножения, а также просветить себя в области астрономии, то есть узнать, как выглядят созвездия Цефея и Кассиопеи.
Послушайте задание.
Перед вами, ребята, фрагмент карты звездного неба. Решите уравнения и соедините последовательно звезды, которым соответствуют найденные ответы.
Работа ведется в группах, поэтому возможна взаимопомощь и взаимоконтроль.
Карточки на столе. Против каждого уравнения указан уровень сложности (1, 2, 3, 4). Каждый из нас выбирает свой уровень, решает уравнение и заносит в карточку ответ.
Затем рисуется созвездие.
|
|
Проверка по образцу.
7-й этап. Резерв (тест)
Провести классификацию данных многочленов по способу разложения их на множители.
Вариант 1.
ЗАДАНИЕ. Соединить линиями многочлены с соответствующими им способами разложения на множители.
Взаимопроверка.
8-й этап. Итоги урока.
Учитель: Ребята, вы сегодня достаточно плодотворно поработали. Благодарю вас.
Но мне хотелось, чтобы вы еще раз, вспомнив этапы нашего урока, ответили на мой вопрос: где вы применяли формулы сокращенного умножения, в каком случае работа ваша намного упрощалась?
Впереди у вас еще 4 формулы. Но это будет позже, а сейчас получите домашнее задание (номера из учебника).
И в заключении, вернитесь к нашему эпиграфу. Скажите, какой для вас путь был более успешным?
Конечно, путь опыта, проб и ошибок – это самый трудный путь, но и самый верный и достойный.
Поэтому я желаю вам идти достойно и получать лишь хорошие и отличные оценки.
Оценки за урок.
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ - это алгоритм, вычисляющий значения многочлена степени 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Можете добавить ввод-вывод и проверить правильность своей реализации. Для многочлена 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 ) по следующему алгоритму:
- Пробежимся циклом от 0 до n -1
- Будем хранить и динамически пересчитывать номер старшего единичного бита числа. Он меняется, только когда текущее число - степень двойки: увеличивается на 1.
- Когда мы знаем старший бит числа, перевернуть всё число не составляет труда: «отрезаем» старший бит (XOR), переворачиваем остаток (уже посчитанное значение) и добавляем «отрезанную» единицу
Аргументами процедуры для слияния двух блоков будут два 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
Обратное преобразование
Получить значения многочлена в точках - это, конечно, хорошо, но преобразование Фурье умеет больше - по этим значениям построить сам многочлен, причём за то же самое время! Оказывается, что если применить преобразование Фурье к массиву значений, как к коэффициентам многочлена, потом разделить результат на 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: Выложил код целиком на
Загрузка...
