Виконання символьних операцій з многочленами (стр. 1 из 3)
Вступ
В даній роботі реалізована задача виконання символьних операцій з многочленами. Був здійснений математичний опис задачі, розроблені алгоритми її реалізації та здійснена сама реалізація на одній з версій алгоритмічної мови Pascal. Правильність роботи програми перевірена на контрольному прикладі. Здійснювалося також тестування програми на екстремальних вхідних даних (піднесення многочлена до нульового степеня, множення на нуль, ділення многочлена на самого себе і т. д.).
При виконанні роботи використовувався структурний метод програмування, що дало змогу зробити програму короткою, легко модифікованою. Оскільки всі розроблені процедури поміщені в модуль, відкомпільований у tpu‑файл, їх легко використати при написанні програм, які реалізують близькі за темою задачі.
Вибрана алгоритмічна мова TurboPascal повністю забезпечує структурний стиль програмування, оскільки це структурована мова високого рівня, на якій можна написати програму практично необмеженого розміру і довільного призначення.
1. Постановка задачі
В представленій роботі реалізується така задача.
Створити тип даних, які б найкраще відповідали означенню многочлена, описати і створити змінні, які б відповідали нулю та одиниці кільця многочленів, передбачити ввід та вивід многочленів згідно із загальноприйнятими стандартами.
Забезпечити реалізацію таких операцій з многочленами:
* додавання n многочленів
* множення n многочленів
* піднесення многочлена до довільного степеня
* знаходження многочлена від многочлена
* ділення многочленів
* знаходження похідної довільного порядку від многочлена
* знаходження невизначеного інтегралу довільного порядку від многочлена
Операції визначені у розділі 1 представленої роботи.
Інтерфейс користувача створити у вигляді меню.
При створенні програмного забезпечення дотримуватися структурного стилю програмування. Створене програмне забезпечення перевірити на контрольному прикладі. Опис контрольного прикладу приведений у розділі 3 представленої роботи.
2. Математичний опис задачі
Многочленом (поліномом) над полем A називається вираз виду
anxn+an-1xn-1+ … +a0 (1)
де ai – елементи поля A, n – натуральне число. n‑максимальне число таке, що коефіцієнт при xn відмінний від 0. n називається степенем многочлена. В даній роботі розглядаються многочлени над полем дійсних чисел.
Загалом многочлени можна трактувати як масиви чисел (елементів поля)
Довільний елемент поля (скаляр) може трактуватися як многочлен нульового степеня.
На множині многочленів введено відношення рівності та операції додавання і множення.
Два многочлени будуть вважатися рівними, якщо рівні їх коефіцієнти ai при однакових степенях невідомого.
Многочлени над довільним полем утворюють кільце. Роль нуля відіграє многочлен (0,0,0,…), роль одиниці – многочлен (1,0,0,…). У представленому у даній роботі програмному забезпеченні вони фігурують під іменами відповідно zero, od.
Операцію множення зручно представити як композицію трьох операцій:
множення на скаляр t
(a0, a1, a2…an,0,0…) Þ(t*a0, t*a1, t*a2…t*an,0,0…) (3)
і множення на многочлен xm (підвищення степеня многочлена на m)
(a0, a1, a2…an,0,0…) Þ(0,0..am, am+1, an+m,0,0.) (4)
та раніше введеною операцією суми.
На кільці многочленів легко ввести ряд операцій, породжених основними: операцію піднесення многочлена до квадрата, куба і довільного ступеня k, де k – натуральне число, операцію знаходження многочлена від многочлена
f(y)=anyn+an-1yn-1+ … +a0
де в ролі y виступає многочлен y(x)= bmym+am-1ym-1+ … +b0.
Крім того, в представленій роботі розглядаються операції знаходження похідної від многочлена
f’ (x)=(anxn+an-1xn-1+ … +a0)’=nanxn-1+(n‑1) an-1 xn-2+ … +a1 (5)
та знаходження невизначеного інтеграла від многочлена
xn+1+ … +a0x+C, (6)
де С – довільна константа. Взяття похідної (диференціювання) і знаходження невизначеного інтеграла (інтегрування) – взаємно обернені операції.
Так визначені операції додавання і множення многочленів легко узагальнити для довільного числа операндів, операції піднесення до степеня, диференціювання та інтегрування – для довільного степеня многочлена, похідної та інтегралу довільного порядку.
В представленій роботі розглядається також операція ділення многочленів. Многочлени над полем дійсних чисел утворюють кільце, а не поле, тому загалом говорити про ділення многочлена на многочлен нема сенсу. Натомість можна ввести операцію ділення з остачею: для двох многочленів f(x) та g(x) знаходження таких многочленів u(x) та v(x), що f(x)=g(x) u(x)+v(x), причому степінь остачі v(x) менший від ступеня дільника g(x). Загалом степені f(x) i g(x) можуть бути довільні, але задача є нетривіальною тільки тоді, коли степінь дільника менший від степеня діленого. Саме ділення здійснюється згідно з широковідомим алгоритмом, аналогічним до ділення чисел у стовпчик.
3.Опис контрольного прикладу
Правильність роботи представленого комплексу програм буде перевірятися на контрольному прикладі. Контрольний приклад виконається коректно, якщо результати, одержані за допомогою програми, співпадуть з результатами, одержаними методами алгебри многочленів, представленим далі.
Додавання многочленiв
Доданки
4.00x 2+ 3.00x
2.00x 4-x 3+ 3.00x 2+ 4.50x+ 5.00
4.00x 3-x 2+0.40x
 |
Результат
2.00x 4+ 3.00x 3+ 6.00x 2+ 7.90x+ 5.00
 |
Множення многочленiв
Множники
2.00x 3-1.00x 2+ 2.00x+ 1.00
1.00x 2+ 1.00
-1.00x 2+ 0.50x+ 0.50
 |
Результат
-2.00x 7+ 2.00x 6–3.50x 5+ 1.50x 4+ 1.50x+ 0.50
 |
піднесення многочлена до степеня
многочлен x 3–2x 2+ 2x‑1
Піднесений до степеня 3
 |
x9-6x 8+18x7-35x 6+48x5-48x4+35x3-18x2+ 6x‑1
 |
Многочлен від многочлена
Внутрішній многочлен y=x 2+ x+ 1
Зовнішній многочлен y 2+ 1.00y+ 1.00
 |
Результат
x 4+ 2x 3+ 4x 2+ 3x+ 3
| |
Ділення многочленiв
Ділене x 5+ 2x 4‑x 3+ 2x 2+ x+ 5.00
Дільник x 2+ x+ 1
 |
Частка x 3+ x 2–3x+ 4
Остача 1.00
знаходження похідної від многочлена
многочлен f(x)=x 4‑x 3+ 2x 2+ 3x+ 1
Похідна 2‑го порядку
f’’ (x)=12x 2–6x+ 4
 |
знаходження невизначеного інтеграла від многочлена
многочлен
f(x)=12x 2–6x+ 4
Інтеграл 2‑го порядку
x 4‑x 3+ 2x 2+C1x+C0
 |
4.Опис програмного забезпечення
Представлене програмне забезпечення розроблене на алгоритмічній мові TurboPascal 7.0. Мова обрана з огляду на її високу структурованість.
Програмне забезпечення записане у двох файлах: файлі kurs.pas, текст якого приведений у додатку 1, та у бібліотеці підпрограм – файлі bibl.pas, який окремо відкомпільований як модуль bibl.tpu. Його текст приведений у додатку 2.
В бібліотеці підпрограм в розділі INTERFACE описані тип poli, що відповідає означенню многочлена (степеня не більше 100), тип mpoli – масиву многочленів, глобальні змінні zero та od, які відіграють роль відповідно нуля та одиниці кільця многочленів.
Там же описані наступні процедури і функції
* function stepin (a:poli):integer; (знаходження степеня многочлена)
* procedure riv (a:poli; var b:poli); (присвоєння одному многочлену значення іншого)
* procedure vvid (n:integer; var a:poli); (ввід многочлена)
* function poper (a:poli; m:integer):integer; (знаходження коефіцієнта многочлена, попереднього по відношенню до заданого)
* procedure vyvid (a:poli); (вивід многочлена згідно із загальноприйнятими стандартами)
* function maxi (n, m:integer):integer; (знаходження числа, більшого з двох)
* function mini (n, m:integer):integer; (знаходження числа, меншого з двох)
* procedure suma (a, b:poli; var c:poli); (знаходження суми двох многочленів)
* procedure nsuma (a:maspoli; n:integer; var c:poli); (знаходження суми n многочленів)