Як перетворити на багаточлен з рішенням. Перетворення одночленів та багаточленів

ВІДДІЛЕННЯ IV.

РОЗКЛАДАННЯ ВИРАЗІВ НА ПРОСТІ МНОЖИКИ.

§ 1.Перетворення многочленів на твір за допомогою формул скороченого множення та поділу.

Якщо всі члени багаточлена містять загальний множник, то можна розділити весь многочлен на цей множник і позначити множення того ж множника на отримане приватне приватне. Від цього цей вираз не змінить свого кількісного значення, але набуде форми твору. Наприклад, двочлен аb+ас можна уявити у вигляді а (b+с ).

Таке перетворення форми називається винесенням загального множника за дужки. Виробляючи цю дію, слід дбати виносити.за дужку все, що можна, так щоб у членах приватного, що укладається в дужки, не залишалося більше жодного спільного множника.

Іноді під час винесення за дужку надають загальному миожителю знак мінус. У такому разі члени приватного в дужках пишуться зі знаками, протилежними до тих, які мали перед собою члени даного багаточлена. Негативний знакзагального множника відноситься при цьому до всього твору. напр., двочлен - аb+ас може бути представлений у вигляді (- а )(b-с ), а натомість пишуть - а (b-с ), причому мінус відноситься вже не до одного множника а але до всього твору.

Коли члени багаточлону не мають спільного множника, то іноді вдалим угрупованням членів у кілька груп, що містять по кілька членів у кожній грусші, знаходять у цих групах загальний і до того ж багаточленний множник. Нерідко для такого угруповання виявляється достатнім укласти кількох членів у дужки зі знаком +, або зі знаком -.

Напр., маючи тричленний вираз а (b +з )+b+с ми укладаємо два останні члени в дужки з плюсом і знаходимо вираз а (b +з )+(b+с ), яке можна розглядати як двочлен і яке перетворюється на добуток ( а +1 )(b+с ).

Подібно до цього у виразі а (b-с )-b+с укладаємо два останні члени в дужки з мінусом, чому вираз набуде вигляду а (b-с )-(b-с ), а потім перетворюється на твір ( а - 1 )(b-с ).

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

Напр., маючи багаточлен а 3 +а 2 b +2аb 2 +2b 3 , з'єднуємо перші два члени в одну групу і останні два в іншу і виносимо в першій групі за дужки а 2 і на другий 2b 2 ; отримаємо а 2 (а+b )+ 2b 2 (а+b ) або ( а+b )(а 2 +2b 2 ). Того ж результату можна досягти, виносячи в першому і третьому членах множник а , а в другому та четвертому множник b .

Подібно до цього, з'єднуючи в багаточлені 3а 3 - 3а 2 b-аb 2 +b 3 перший член з третім і другий з четвертим і виносячи в першій групі множник а , а в другому множник- b, отриманні а (3а 2 -b 2 )-b (3а 2 -b 2 ) або ( а-b )(3а 2 -b 2 ). Той же результат виявився б при винесенні з двох двох членів за дужки 3а 2 , а з останніх двох -b 2 .

Потрібно зауважити, що подібні перетворення відрізняються великою різноманітністю, особливо при поєднанні їх з іншими алгебраїчними діями. Тому не можна дати для цих перетворень загальних і цілком визначених правил; навик у них набувається лише ґрунтовною та методичною вправою.

Іноді, перш ніж групувати члени мкогочлена для винесення в ньому багаточленного множника, потрібно розкласти деякі з членів в алгебраїчну суму нових членів, подібних до розкладається. У такому випадку частини розкладених членів відносяться при групуванні до різних груп. Застосуємо спосіб розкладання до перетворення тричленних виразів.

Щоб перетворити тричлен х 2 +5х+6 , розкладаємо член 5 х у суму членів 2 х і 3 х . Таким чином отримаємо:

х 2 +5х+6 = х 2 +2х+ 3 х +6 = х (х +2 )+3 (х +2 )==(х +2 )(х +3 ).

Для перетворення тричлена х 2 +2х -15 , Розкладаємо член + 2х у суму членів + 5х і - 3х Знайдемо:

х 2 +2х -15 = х 2 +5х - 3х -15 = х (х +5 )-3 (х +5 )==(х -3 )(х +5 ).

Існує загальне правило, що вказує, коли можливе перетворення тричленів подібного виду на твір, і як робити таке перетворення. Для виведення та усвідомлення цього правила потрібно лише розкласти чотири види тричлена. х 2 ± ( а+b )х +аb і х 2 ± ( а-b )х -аb , Взявши кожен з них окремо і почавши перетворення з розкриття дужок. Тоді виявиться, що на твір перетворюються ті тричлени, у яких перший коефіцієнт при х 2 є одиниця, другий коефіцієнт при х який завгодно, а третій коефіцієнт або член, що не містить х є алгебраїчне твір тих самих кількостей, на алгебраїчну суму яких розкладається другий коефіцієнт. Так, у тричлені х 2 +5х+6 коефіцієнт 5 є сума чисел 3 і 2 , а 6 є твір тих же чисел, в тричлені х 2 +2х -15 коефіцієнт - 2 є сума кількостей - 5 та + 3 , а - 15 є твір тих же кількостей. Щоб зробити перетворення тричлена, коли воно возіожно, потрібно за знаками і числовими величинами третього і другого коефіцієнта підшукати спосіб розкладання третього коефіцієнта у провадження двох кількостей, а другого в суму тих же кількостей. Розглянемо приклади:

Нехай, напр., дано тричлі х 2 -11х+24 . Оскільки коефіцієнт 24 Позитивний, то шукані виробники його повинні мати однакові знаки. Судячи з того, що другий коефіцієнт - 11 від'ємний, бачимо, що ці виробники коефіцієнта 24 або складові коефіцієнта - 11 обидва від'ємні. Нарешті, розкладаючи 24 на два негативні множники і порівнюючи суму їх з - 11 , переконаємося в тому, що для перетворення тричлену в твор потрібно розкласти середній член - 11 х на члени - 3 х і - 8 х.

Покладемо ще, що дано тричлен х 2 - 7х-30 . Тут коефіцієнт - 30 негативний; тому виробники його мають різні знаки. Коефіцієнт -7 негативний; отже, при складанні його додаванням бере перевіс негативний доданок, що має таким чином велику числову величину. Тому член - 7х потрібно розкласти на члени - 10х і +3х.

У твір перетворюються також нерідко тричлени, у яких перший коефіцієнт не є одиниця. Для таких перетворень не вказуватимемо тепер загального правила, Висновок якого вимагає більш складних міркувань.

Розвиваючи вище розглянутий спосіб перетворення тричленів на твір, можна розкладати багаточлени вищих ступеніву тих випадках, коли вони представляють твори найпростіших двочленів першого ступеня. Для спрощення подібних перетворень корисно з'ясувати наступне зауваження: припустимо, що якийсь багаточлен містить множником деякий двочлен х + а . Так як двочлен цей, при заміні х через - а , звертається в нуль, то багаточлен, що містить х+а множником, повинен також звертатися в нуль при цій заміні. Подібно до цього якщо багаточлен містить множником двочлен х-а , що обертається в нуль при заміні х через а, то і сам многочлен звертається в нуль при тій же заміні. Справедливий і зворотний висновок: якщо багаточлен, що містить різні ступені х , звертається в нуль при заміні х через - а або через а , то він напевно ділиться в першому випадку на х+а , а у другому на х-а , тому що звернення многочлена в нуль при одній із зазначених підстановок може бути пояснено тільки тим, що до складу багаточлена входить двочленний множник. Вищезазначені зауваження дають простий засіб для відкриття в многочлені двочленного множника, а потім цей множник може бути винесений за дужки за допомогою розкладання середніх членів багаточлена в суми алгебри.

Візьмемо, наприклад, багаточлен х 3 +6х 2 +11х+6 . Він звертається в нуль при заміні х через - 1 і тому ділиться на х +1. Знаючи цей множник наперед, ми полегшуємо собі розкладання членів у суми тим, що певно підбираємо до кожного члена, починаючи з вищого, частина наступного члена так, щоб пара групованих членів містила множником х +1 . Тому перетворення ведеться наступним чином:

х 3 +6х 2 +11х+6 = х 3 +х 2 +5х 2 +5х+6х+6 = х 2 (х +1 )+ 5х (х +1 )+ 6 (х +1 )= (х +1 )(х 2 +5х +6 ) =
= (х +1 )(х +2 )(х +3 )

Іімо цьому зауважуємо, що багаточлен х 3 -4х 2 -11х+30 звертається в нуль при заміні х через 2 і отже ділиться на х- 2 . Тому виконуємо перетворення так:

х 3 -4х 2 -11х+30 = х 3 -2х 2 -2х 2 +4х-15х+30 = х 2 (х -2 ) -2х(х-2)-15 (х -2 )=
=(х -2 )(х 2 -2х -15 )=(х -2 )(х +3 )(х -5 ).

Початковий підбір множника полегшується тим, що багаточлен потрібно підставляти тільки кількості, числова величинаяких входить множником до останнього члена багаточлена. Це виявляється при розгляді багаточлена, що виражає загальний виглядтвори ( х +а )(х +b )(х +c ) . Останній членцього багаточлена є abc.

Багаточленом називають суму одночленів. Якщо всі члени багаточлена записати в стандартному вигляді (див. п. 51) і виконати приведення таких членів, то вийде багаточлен стандартного виду.

Будь-яке ціле вираження можна перетворити на многочлен стандартного виду - у цьому полягає мета перетворень (спрощень) цілих виразів.

Розглянемо приклади, у яких цілий вираз слід призвести до стандартного виду многочлена.

Рішення. Спочатку наведемо до стандартного вигляду члени багаточлена. Отримаємо Після приведення подібних членів отримаємо багаточлен стандартного вигляду

Рішення. Якщо перед дужками стоїть знак плюс, то дужки можна опустити, зберігши знаки всіх доданків, укладених у дужки. Скориставшись цим правилом розкриття дужок, отримаємо:

Рішення. Якщо перед дужками стоїть зіак «мінус», то дужки можна опустити, змінивши знаки всіх доданків ув'язнених у дужки. Скориставшись цим правилом паскриття дужок, отримаємо:

Рішення. Добуток одночлена та багаточлена згідно з розподільчим законом дорівнює сумі творів цього одночлена та кожного члена багаточлена. Отримуємо

Рішення. Маємо

Рішення. Маємо

Залишилося навести таких членів (вони підкреслені). Отримаємо:

53. Формули скороченого множення.

У деяких випадках приведення цілого виразу до стандартного виду багаточлена здійснюється з використанням тотожностей:

Ці тотожності називають формулами скороченого множення,

Розглянемо приклади, у яких необхідно перетворити заданий вираз у миогочлеи стандартного виду.

приклад 1. .

Рішення. Скориставшись формулою (1), отримаємо:

Приклад 2. .

Рішення.

Приклад 3. .

Рішення. Скориставшись формулою (3), отримаємо:

приклад 4.

Рішення. Скориставшись формулою (4), отримаємо:

54. Розкладання багаточленів на множники.

Іноді можна перетворити багаточлен на твір кількох співмножників - багаточленів або одпочленів. Таке тотожне перетворенняназивається розкладанням многочлена на множники. І тут кажуть, що многочлен ділиться кожен із цих множників.

Розглянемо деякі способи розкладання багаточленів на множники,

1) Винесення загального множника за дужку. Це перетворення є безпосереднім наслідком розподільчого закону (для наочності потрібно лише переписати цей закон «праворуч наліво»):

Приклад 1. Розкласти на множники багаточленів

Рішення. .

Зазвичай при винесенні загального множника за дужки кожну змінну, що входить у всі члени многочлена, виносять з найменшим показником, який вона має у цьому багаточлені. Якщо всі коефіцієнти многочлена - цілі числа, то як коефіцієнт загального множника беруть найбільший за модулем спільний дільниквсіх коефіцієнтів многочлена.

2) Використання формул скороченого множення. Формули (1) - (7) з п. 53, будучи прочитаними «праворуч наліво, у багатьох випадках виявляються корисними для розкладання багаточленів на множники.

Приклад 2. Розкласти на множники.

Рішення. Маємо. Застосувавши формулу (1) (різницю квадратів), отримаємо . Застосувавши

тепер формули (4) і (5) (сума кубів, різницю кубів), отримаємо:

Приклад 3. .

Рішення. Спочатку винесемо за дужку загальний множник. Для цього знайдемо найбільший спільний дільник коефіцієнтів 4, 16, 16 та найменші показникиступенів, з якими змінні а та b входять до складових даний багаточлен одночлени. Отримаємо:

3) Спосіб угруповання. Він заснований на тому, що переміщувальний та сполучний законидодавання дозволяють групувати члени багаточлена у різний спосіб. Іноді вдається таке угруповання, що після винесення за дужки загальних множників у кожній групі в дужках залишається один і той самий багаточлен, який у свою чергу як загальний множник може бути винесений за дужки. Розглянемо приклади розкладання многочлена на множники.

приклад 4. .

Рішення. Зробимо угруповання наступним чином:

У першій групі винесемо за дужку загальний множник у другій – загальний множник 5. Отримаємо Тепер багаточлен як загальний множник винесемо за дужку: Таким чином, отримуємо:

Приклад 5.

Рішення. .

Приклад 6.

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

Приклад 7.

Рішення. Додамо та віднімемо одночлен Отримаємо

55. Багаточлени від однієї змінної.

Багаточлен, де a, b - числа змінна, називається многочленом першого ступеня; багаточлен де а, b, с - числа змінна, називається многочленом другого ступеня або квадратним тричленом; многочлен де а, b, з, d - числа змінна називається многочленом третього ступеня.

Взагалі якщо о, змінна, то багаточлен

називається лсмогочленол ступеня (щодо х); , m-члени многочлена, коефіцієнти, старший член многочлена, а - коефіцієнт при старшому члені, вільний член многочлена. Зазвичай многочлен записують по спадних ступенях змінної, т. е. ступеня змінної поступово зменшуються, зокрема, першому місці стоїть старший член, останньому - вільний член. Ступінь многочлена – це ступінь старшого члена.

Наприклад, багаточлен п'ятого ступеня, у якому старший член, 1 - вільний член багаточлена.

Коренем багаточлена називають таке значення при якому багаточлен перетворюється на нуль. Наприклад, число 2 є коренем багаточлена, оскільки

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

Інструкція

1. Розкрийте всі дужки виразу. Для цього скористайтесь формулами, скажімо, (а+b)^2=a^2+2ab+b^2. Якщо ви не знаєте формул або їх складно застосувати до цього виразу, розкривайте дужки ступінчасто. Для цього множте 1-й член першого виразу на весь член другого виразу, після цього 2-й член першого виразу на весь другий член і т.д. У результаті всі елементи обох дужок будуть перемножені між собою.

2. Якщо перед вами три вирази в дужках, спочатку перемножте перші дві, залишаючи третій вираз не зворушеним. Спростивши результат, що у результаті реформування перших дужок, перемножте його з третім виразом.

3. Спостерігайте за дотриманням знаків перед множниками-одночленами. Якщо ви перемножуєте два члени з одним знаком (скажімо, обидва правильні або обидва негативні), одночлен буде зі знаком «+». Якщо один член має перед собою «-», не забудьте перенести його на твір.

4. Наведіть усі одночлени до стандартного вигляду. Тобто переставте місцями множники всередині та спростіть. Скажімо, вираз 2х*(3,5х) дорівнюватиме (2*3,5)*х*х=7х^2.

5. Коли всі одночлени будуть стандартизовані, спробуйте спростити багаточлен. Для цього згрупуйте члени, які мають ідентичну частину зі змінними, скажімо, (2х+5х-6х)+(1-2). Спростивши вираз, ви отримаєте х-1.

6. Зверніть увагу на наявність параметрів у виразі. Зрідка полегшення многочлена потрібно виготовляти так, наче параметр є числом.

7. Щоб перетворити на многочлен вираз, що містить корінь, виведіть під ним такий вираз, який буде зведений у квадрат. Скажімо, скористайтеся формулою a^2+2ab+b^2 =(а+b)^2, після цього приберіть знак кореня спільно з парним ступенем. Якщо позбутися знака кореня неможливо, перетворити вираз у многочлен стандартного вигляду не вдасться.

Короткість, як кажуть, сестра дару. Кожному хочеться блиснути задарма, але його сестра – штука важка. Феноменальні думки чомусь самі собою одягаються в складнопідрядні пропозиціїз більшістю дієпричетних циклів. Втім у ваших силах спростити свої пропозиції і зробити їх виразними та доступними кожним.

Інструкція

1. Щоб полегшити адресату (чи слухач чи читач) життя, постарайтеся замінювати причетні і дієпричетні цикли короткими підрядними пропозиціями, тільки якщо вищевказаних циклів занадто багато в одному реченні. "Кіт, що прийшов додому, щойно з'їв мишу, голосно муркочучи, пестився до власника, намагаючись зазирнути йому в очі, вірячи випросити рибу, принесену з магазину" - таке не піде. Розбийте подібну конструкцію на кілька частин, не поспішайте і не намагайтеся сказати все одним реченням, і буде вам щастя.

2. Якщо ви задумали талановитий вислів, але в ньому виявилося дуже багато додаткових пропозицій(тим більше з одним союзом), то краще розбити висловлювання на кілька окремих пропозицій або опустити якийсь елемент. "Ми вирішили, що він розповість Марині Василівні, що Катя скаже Віті, що ..." - Можна продовжувати безмежно. Своєчасно зупиніться і згадайте про ту людину, хто це читатиме або вислуховуватиме.

3. Втім, підводні камені криються не тільки в структурі пропозиції. Зверніть увагу на лексику. Іншомовні слова, довгі терміни, слова, почерпнуті з художньої літератури 19 століття – все це лише ускладнить сприйняття. Потрібно уточнити для себе, для якої аудиторії ви складаєте текст: технарі, фінально, усвідомлюють і важкі терміни, і специфічні слова; але якщо ви ті самі слова запропонуєте вчительці літератури, навряд чи вона вас зрозуміє.

4. Дар – велика річ. Якщо ви геніальні (а людей без здібностей не буває), перед вами відкривається безліч доріг. Але дар полягає не в труднощі, а простоті, як не дивно. Будьте простіше, і ваші дари будуть виразні та доступні кожному.

Відео на тему

Навіть найважче рівняння перестає виглядати лякаючим, якщо привести його до вигляду, з яким ви вже стикалися. Особливо простим методом, Той, що рятує у будь-якій обстановки, є приведення багаточленів до стандартного вигляду. Це початкова точка, З якої ви можете рухатися далі до рішення.

Вам знадобиться

• аркуш паперу
• кольорові ручки

Інструкція

1. Запам'ятайте стандартну форму многочлена, щоб знати, що ви повинні отримати в результаті. Важливість має навіть порядок запису: першими повинні стояти члени більшим ступенем. Крім того, прийнято спочатку записувати незнайомі, позначені літерами, що стоять на початку алфавіту.

2. Запишіть початковий багаточлен і приступайте до пошуку подібних доданків. Це члени цього рівняння, що мають ідентичну буквену частину або (і) цифрову. Для більшої наочності наголошуйте виявлені пари. Зверніть увагу, що подібність не означає ідентичність, - головне, щоб один член пари містив у собі другий. Так, подібними будуть члени ху, хy2z і хуz - вони мають загальну частину у вигляді твору х і у. Це ж стосується і статечних виразів.

3. Позначайте різні подібні члени по-різному. Для цього класніше підкреслюйте одинарними, подвійними та потрійними лініями, використовуйте колір та інші форми ліній.

4. Виявивши всі подібні члени, починайте їх комбінування. Для цього у виявлених парах винесіть подібні члени за дужки. Не забувайте, що в стандартній формі багаточлен не має подібних членів.

5. Перевірте, чи не залишилося у вас ідентичних елементів запису. У ряді випадків у вас можуть знову з'явитися подібні члени. Повторіть операцію з їх комбінуванням.

6. Прослідкуйте за виконанням другого дані, потрібного для запису многочлена у стандартній формі: весь його учасник має бути зображений у вигляді одночлена у стандартному вигляді: на першому місці – числовий множник, на другому – змінна або змінні, що йдуть у вже зазначеному порядку. При цьому пріоритет має буквена послідовність, що задається алфавітом. Зниження ступенів враховується у другу чергу. Так, стандартним виглядомодночлена є запис 7xy2, у той час як y27x, x7y2, y2x7, 7y2x, xy27 не відповідають вимогам.

Відео на тему

Математична наука осягає різні конструкції, послідовності чисел, відносин між ними, складання рівнянь та їх вирішення. Це формальна мова, Яким можна чітко описати наближені до ідеальних характеристики справжніх об'єктів, осяганих інших областях науки. Однією з таких конструкцій є багаточлен.

Інструкція

1. Багаточлен чи поліном (від грецьк. «полі» – багато і лат. «номен» – ім'я) – клас елементарних функційкласичної алгебри та алгебраїчної геометрії. Це функція однієї змінної, яка має вигляд F(x) = c_0 + c_1*x + … + c_n*x^n, де c_i – фіксовані показники, x – змінна.

2. Багаточлени використовують у багатьох розділах, зокрема розгляді нуля, негативних і комплексних чисел, теорії груп, кілець, вузлів, множин тощо. Застосування поліноміальних обчислень значно полегшує вираження властивостей різних об'єктів.

3. Основні визначення многочлена: Кожне доданок полінома називається одночленом чи мономом. Многочлен, що з 2-х одночленів, називають двочленом чи біномом. Коефіцієнти полінома – матеріальні чи комплексні числа. Якщо старший показник дорівнює 1, багаточлен називають унітарним (наведеним). Ступені змінної у кожному одночлені – цілі невід'ємні числа, максимальний ступіньвизначає ступінь многочлена, яке повним ступенем називається ціле число, рівну сумівсіх ступенів. Одночлен, відповідний нульового ступеня, називається вільним членом. Багаточлен, всі одночлени якого мають ідентичну повний ступінь, називається однорідним.

4. Деякі часто використовувані багаточлени названі на прізвище вченого, який їх визначив, а також описав функції, які вони задають. Скажімо, Біном Ньютона - це формула для розкладання полінома 2-х змінних на окремі складові для обчислення ступенів. Це знамениті з шкільної програмизаписи квадратів суми та різниці (a + b)^2 – a^2 + 2*a*b + b^2, (a – b)^2 = a^2 – 2*a*b + b^2 та різниця квадратів (a 2 - b 2) = (a - b) * (a + b).

5. Якщо допустити у записі многочлена негативні ступеня, то вийде многочлен чи ряд Лорана; многочлен Чебишева застосовується теоретично наближень; багаточлен Ерміта – теоретично ймовірностей; Лагранжа – для чисельного інтегруваннята інтерполяції; Тейлора – при апроксимації функції тощо.

Зверніть увагу!
Біном Ньютона часто згадують у книгах («Майстер і Маргарита») та фільмах («Сталкер»), коли герої вирішують математичні задачі. Цей термінна слуху, тому вважається найвідомішим багаточленом.

Реформування висловів найчастіше проводиться з метою їх полегшення. Для цього застосовуються особливі співвідношення, а також правила скорочення та приведення подібних.

Вам знадобиться

• - Дії з дробами;
• - Формули скороченого множення;
• - Калькулятор.

Інструкція

1. Найпростішим реформуванням є приведення подібних. Якщо є кілька доданків, які є одночленами з ідентичними співмножниками, показник при них можна скласти, з урахуванням знаків, що стоять перед цими показниками. Скажімо, вираз 2 n-4n+6n-n=3 n.

2. Якщо ж ідентичні співмножники мають різні ступені, подібним чином звести подібні не припустимо. Групуйте лише ті показники, які мають при собі співмножники з ідентичними ступенями. Скажімо, спростіть вираз 4 k?-6 k+5 k?-5 k?+k-2 k?=3 k?-k?-5 k.

3. Якщо є така можливість, використовуйте формули скороченого множення. До особливо відомим відносяться куб і квадрат суми або різниці двох чисел. Вони є окремий випадокбінома Ньютона. До формул скороченого множення також відносять різницю квадратів 2-х чисел. Скажімо, щоб визначити значення виразу 625-1150+529=(25-23)?=4. Або 1296-576 = (36 +24) (36-24) = 720.

4. Коли необхідно перетворити вираз, Яке являє собою природний дріб, виділіть із чисельника та знаменника загальний множник і скоротите на нього чисельник та знаменник. Скажімо, скоротите дріб 3 (a+b)/(12 (a?-b?)). Для цього перетворіть її на вигляд 3 (a+b)/(3 4 (a-b) (a+b)). Скоротіть це виразна 3 (a+b), отримайте 1/(4(a-b)).

5. Перетворюючи тригонометричні вирази, використовуйте вестиме тригонометричні тотожності. До них відноситься основна тотожність sin?(x)+cos?(x)=1, а також формули тангенсу та його співвідношення з котангенсом sin(x)/cos(x)=tg(x), 1/ tg(x)= ctg(x). Формули суми різниці аргументів, і навіть кратного аргументу. Скажімо, перетворіть вираз(cos?(x)-sin?(x)) cos?(x) tg(x)= cos(2x) cos?(x) sin(x)/cos(x)= cos(2x) cos(x) sin(x)= cos(2x) cos(x) sin(x) 2/2= cos(2x) sin(2x)/2=cos(2x) sin(2x) 2/4= sin(4x)/4 . Таке виразрозрахувати набагато легше.

Процедура реформування формул використовується у будь-якій науці, що використовує формальну мову математики. Формули складаються із особливих символів, пов'язаних між собою за певними правилами.

Вам знадобиться

• Знання правил математичних тотожних реформ, таблиця математичних тотожностей.

Інструкція

1. Досліджуйте вираз на наявність дробів. Чисельник і знаменник дробу можна помножити чи розділити одне й те саме вираз, позбувшись знаменника. У разі реформування рівняння, перевірте, чи немає у знаменниках змінних. Якщо є - додайте умову, що вираз знаменника не дорівнює нулю. З цього дані виділіть неприпустимі значеннязмінних, тобто обмеження у сфері визначення.

2. Застосуйте правила дій зі ступенями для ідентичних підстав. У результаті зменшиться кількість доданків.

3. Перенесіть доданки, що містять змінну, в одну частину рівняння, які не містять – в іншу. До будь-якої частини рівняння використовуйте математичні тотожності для полегшення.

4. Згрупуйте однорідні доданки. Для цього винесіть загальну змінну за дужки, усередині яких запишіть суму показників з урахуванням символів. Ступінь тієї ж самої змінної розглядається як інша змінна.

5. Перевірте, чи немає у формулі зразків тотожних реформ багаточленів. Скажімо, чи немає в правій чи лівій частині формули різниці квадратів, суми кубів, квадрата різниці, квадрата суми та ін. Якщо є, то замість виявленого зразка підставте його спрощений аналог і знову спробуйте провести угруповання доданків.

6. У разі реформування тригонометричних рівнянь, нерівностей або легко виразів виявіть у них зразки тригонометричних тотожностейі застосуйте спосіб заміни частини виразу тотожним спрощеним виразом. Таке реформування дозволяє позбутися зайвих синусів чи косинусів.

7. Для реформування кутів у загальному вигляді чи радіанної формі скористайтеся формулами приведення. Пізніше реформування обчисліть значення подвійного кутаабо половинного кута в залежності від числа пі.

19. Візьмемо формулу

ми її читали так: «різниця числа a та b». Ми можемо у цій формулі число a замінити нулем; тоді вона звернеться до

0 – b або просто –b.

Від нуля відняти b означає, відповідно до того, що ми знаємо про віднімання відносних чисел, До нуля приписати число b, взяте зі зворотним знаком. Тому вираз –b має розуміти, як число, обернене за знаком числу b. Якщо, наприклад, b = +5, то -b = -5; якщо b = –4, то –b = +4 тощо. п. Якщо ми напишемо вираз +a, його треба розуміти, як число, рівну числу a. Якщо a = +5 то +a = +5; якщо a = -4, то + a = 4 і т.п.

Тому формулу

ми можемо розуміти, без відмінності результату, або в значенні

або в сенсі

Таким чином ми завжди можемо замінювати віднімання додаванням і будь-яку різницю розуміти, як суму двох чисел:
a – b є сума чисел a та (–b)
x – y є сума чисел x та (–y)
–a – b є сума чисел (–a) та (–b) тощо.

Ті формули, де, з погляду арифметики, мають місце кілька додавань і віднімань, напр.,

a – b + c + d – e – f,

ми можемо тепер, з погляду алгебри, розуміти тільки як суму, а саме:

a – b + c + d – e – f = (+a) + (–b) + (+c) + (+d) + (–e) + (–f).

Тому прийнято подібні висловлюванняназивати ім'ям « алгебраїчна сума».

20. Візьмемо якусь алгебраїчну суму

a – b – c або –3bc² + 2ab – 4a²b тощо.

Прийнято називати ці вирази ім'ям багаточлен, причому це слово замінює собою слово "сума" або назву "алгебраїчна сума". Ми знаємо, що

a – b – c = (+a) + (–b) + (–c)
–abc – 3bc² + 2ab – 4a²b = (–abc) + (–3bc²) + (+2ab) + (–4a²b) тощо.

Окремо кожен доданок називають ім'ям член багаточлена.

Перший багаточлен,

складається з трьох членів: (+a), (–b) та (+c).

Другий багаточлен,

-abc - 3bc² + 2ab - 4a²b,

складається з чотирьох членів: (–abc), (–3bc²), (+2ab) та (–4a²b).

Доданки можна переставляти в будь-якому порядку:

–abc – 3bc² + 2ab – 4a²b = (–abc) + (–3bc²) + (+2ab) + (–4a²b) =
= (+2ab) + (–3bc²) + (–4a²b) + (–abc) = 2ab – 3bc² – 4a²b – abc.

Цю властивість суми тепер можна виразити інакше: члени багаточлена можна переставляти у будь-якому порядку. Це й зроблено вище для многочлена –abc – 3bc² + 2ab – 4a²b, причому отже попереду тепер виявився член (+2ab). Це дозволило дещо спростити вираз: попереду знак + не можна писати. Звичайно, треба подібні перестановки робити відразу, не укладаючи попередньо (як вище) кожен доданок у дужки.

Ще приклад:

1 – 3a + 2a² – a³ + 3a 4 = 3a 4 – a³ + 2a² – 3a + 1.

Перший член цього многочлена був спочатку (+1) - знак + передбачався перед одиницею; коли ми переносимо цей член на інше, крім першого, місце (вище ми перенесли його на останнє місце), то вже цей знак + пропускати не можна.

Ми можемо помітити, що в попередньому прикладі ми перестановкою членів багаточлена досягли деякого порядку: на першому місці стоїть член з літерою a в 4-му ступені, на наступному – член з літерою a у 3-му ступені, потім йде член з літерою a в Другого ступеня, потім - a в 1-го ступеня і, нарешті, член, де букви a зовсім немає.

Подібне розташування членів багаточлена виражають словами «багаточлен розташований за низхідними ступенями літери a».

Ось ще приклади такого розташування:

3x 5 – 2ax 3 + b (за низхідними ступенями літери x)
a 4 – a 3 b + a 2 b 2 – ab 3 + b 4 (за низхідними ступенями літери a)
3ab 5 – 4a 3 b 3 + 5a 4 b 2 – 2a 6 (за низхідними ступенями літери b)
4x 4 – 3x 3 + 2x 3 (за низхідними ступенями літери x).

Вживають часто і зворотне «за висхідними ступенями» розташування, при якому ступінь обраної літери поступово підвищується, причому в 1-му члені або цієї літери немає, або вона має тут найменший ступіньпорівняно з іншими членами. Про другий із попередніх прикладів ми могли б сказати, що тут багаточлен розташований за висхідними ступенями літери b. Ось приклади:
3 – 2a + 3a 2 – 4a 3 (за висхідними ступенями літери a);
-x + x 2 - 3x 3 - 4x 4 (за висхідними ступенями літери х);
ax 2 – bx 3 + cx 5 – dx 6 (за висхідними ступенями літери x);
a 3 – 2ab + b 2 (за висхідними ступенями літери b або за низхідними ступенями літери a);
3x 5 – 4yx 4 – 5y 3 x 2 – 6y 4 x (за низхідними ступенями літери x або за висхідними ступенями літери y).

21. Багаточлен про двох членів називається двочленом(напр., 3a + 2b), про трьох членах – тричлен (напр., 2a² – 3ab + 4b²) і т. д. Можливо говорити про суму з одного доданку (інше доданок дорівнює нулю), або про багаточлен про одного члена. Тоді вже, звичайно, назва «багаточлен» недоречна і використовується назва «одночлен». Кожен член будь-якого багаточлена, взятий окремо, є одночленом. Ось приклади найпростіших одночленів:

2; -3a; a²; 4x³; -5x4; ab; ab²; -3abc; і т.д.

Майже всі одночлени з вище написаних є творами двох або більше множників, причому більшість з них мають і числовий множник і буквені. Напр., в одночлені –3abc є числовий множник –3 та літерні множники a, b та c; в одночлені 4x³ є числовий множник +4 (знак + мається на увазі) і літерний множник x³ і т. д. Якби ми написали одночлен з кількома числовими множниками (а також і з літерними), на кшталт наступного

,

то зручніше, переставивши множників те щоб числові множники виявилися поруч, тобто.

,

ці числові множники перемножити – отримаємо

-4a²bc² (точки, знаки множення пропускаємо).

Прийнято також, у більшості випадків, числовий множник писати попереду. Пишуть:

4a, а не a 4
–3a²b, а не a²(–3)b

Числовий множник одночлена називається коефіцієнтом.

Якщо в одночлен не написаний числовий множник, наприклад, ab, то можна завжди його розуміти. Справді

a = (+1) ∙ a; ab = (+1) ab;
-a = (-1) ∙ a; a³ = (–1) ∙ a³ тощо.

Отже, у одночленів a², ab, ab² мається на увазі, у кожного коефіцієнт 1 (точніше: +1). Якщо напишемо одночлени –ab, –a², –ab² тощо, то вони мають на увазі коефіцієнт –1.

22. Більше складні прикладибагаточленів та одночленів.

(a + b)² + 3(a – b)² … ця формула виражає суму двох доданків: першим є квадрат суми чисел a та b, а другим – добуток числа 3 на квадрат різниці тих самих чисел. Тому цю формулу слід визнати двочленом: перший член є (a + b)² і другий 3(a – b)². Якщо взяти вираз (a + b)² окремо, то через попередній, його треба вважати одночленом, причому його коефіцієнт = +1.

a(b – 1) – b(a – 1) – (a – 1)(b – 1) … має визнати за тричлен (сума трьох доданків): перший член є a(b – 1) та його коефіцієнт = +1 , другий член -b(a - 1), його коефіцієнт = -1, третій член - (a - 1) (b - 1), його коефіцієнт = - 1.

Іноді штучно зменшують кількість членів многочлена. Так тричлен

можна, наприклад, розглядати за двочлен, причому a + b, наприклад, вважають за один член (за один доданок). Щоб це ясніше відзначити, користуються дужками:

Тоді член (a + b) має на увазі коефіцієнт +1

[Справді (a + b) = (+1) (a + b)].

Добрий вечір.
Ця посада присвячена швидкого перетворенняФур'є. Будуть розглянуті пряме та зворотне перетворення (у комплексних числах). У наступній частині я планую розглянути їх застосування в деяких завданнях олімпіадного програмування (зокрема, одне завдання про «схожість» рядків), а також розповісти про реалізацію перетворення на цілих числах.
БПФ - це алгоритм, що обчислює значення багаточлена ступеня n=2 kв деяких nточках за час O(n⋅log n) («наївний» метод виконує те саме завдання за час O(n 2 )). За той же час можна виконати та зворотне перетворення. Так як складати, віднімати і множити масиви чисел набагато легше, ніж багаточлени (особливо множити), БПФ часто застосовується для прискорення обчислень з багаточленами довгими числами.

Визначення та способи застосування

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

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

Комплексне коріння з 1

Чому сума коренів - нуль

Як працює

Напишемо щось

Slow FFT

#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; 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++; vectorrev(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+bmodn :

Тепер давайте доведемо один чудовий факт: при 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:Виклав код повністю на