27

Міністерство освіти і науки України

Східноукраїнський національний університет

імені Володимира Даля

Інститут хімічних технологій

(м. Рубіжне)

Інженерно-економічний факультет

Кафедра вищої математики і комп’ютерних технологій

ЗАТВЕРДЖУЮ Завідувач кафедри ВМКТ доктор хімічних наук, професор _____________ Кондратов С.О. “.....”................................... 2008 р.

ПОЯСНЮВАЛЬНА ЗАПИСКА

курсової роботи з дисципліни «Програмування»

на тему: «Ділення двох багаточленів»

Виконав студ. гр. ІД-06 ________________________ Кривцун Д.О.

^{підпис, число, місяць, рік}

Науковий керівник,

старший викладач _________________________ Хількова Л.О.

^{Оцінка керівника, підпис, число, місяць, рік}

2008

ЗАТВЕРДЖУЮ

Завідувач кафедри ВМКТ

доктор хімічних наук, професор

_____________ Кондратов С.О.

“.....”................................... 2008 р.

ЗАВДАННЯ НА ВИКОНАННЯ РОБОТИ

На тему Ділення двох багаточленів

Вид роботи (курсова, кваліфікаційна, дипломна) - курсова

Виконавець: студент гр. ІД-06 Кривцун Д.О.

Науковий керівник: старший викладач кафедри ВМКТ Хількова Л.О. ^{(Прізвище, І.Б. керівника, науковий ступінь, звання, посада)}

Тема і керівник затверджені розпорядженням по кафедрі ВМКТ № 2 від “30” січня 2008р.

Вихідні дані до курсової роботи

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

Зміст пояснювальної записки

1. Теоретичний матеріал по тематиці роботи.

2. Опис алгоритму.

3. Приклад застосування алгоритму.

4. Програмна реалізація алгоритму

4.1. блок-схема;

4.2. підпрограми;

4.3. інтерфейс користувача.

5. Приклад роботи програмного комплексу.

6. Додатки.

Строк здачі роботи на кафедру: не пізніше “25” травня 2008 р.

Завдання видано “5” лютого 2008 р.

Студент ____________________ (Кривцун Д.О.)

^{(підпис)}

Науковий керівник ____________________ (Хількова Л.О.)

^{(підпис)}

КАЛЕНДАРНИЙ ПЛАН

Виконання курсової роботи на тему: Ділення двох багаточленів

Найменування етапу роботи	Строк початку	Строк закінчен-ня	Відмітка про виконан-ня
1. Розглянути теоретичний матеріал по тематиці роботи та подготувати розділ 1 спеціальної частини пояснювальної записки з детальним описом теоретичних основ.	5.02.08	12.03.08
2. Описати стратегію, чка дозволяє алгоритмізувати поставлену задачу та подготувати розділ 2 спеціальної частини записки: опис алгоритму та розділ 3 з детальним описом використання алгоритму на конкретному прикладі.	13.03.08	26.03.08
3. Составити блок-схему алгоритму та записати її в розділі 4.1. спеціальної частини пояснювальної записки.	27.03.08	16.04.08
4. Составити необхідні подпрограми, отладити програму та подготувати розділ 4.2. спеціальної частини пояснювальної записки с детальним описом подпрограм.	17.04.08	30.04.08
5. Створити інтерфейс користувача та подготувати розділ 4.3. спеціальної частини пояснювальної записки, в якої привести скріншоти інтерфейсу.	1.05.08	14.05.08
6. Виконати тестування програми на деяких конкретних прикладах, результати тестування внести в розділ 5.	15.05.08	20.05.08

Студент ____________________ (Кривцун Д.О.)

^{(підпис)}

Науковий керівник ____________________ (Хількова Л.О.)

^{(підпис)}

РЕФЕРАТ

Сторінок 27, ілюстрацій 6, перелік посилань 3 джерела

Об'єкт роботи – ділення двох багаточленів.

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

Програмний комплекс розроблений за допомогою середовища програмування Turbo Pascal 7.0. Він дозволяє для заданих коефіцієнтів двох багаточленів різних ступенів виконати операцію їх цілочисельного ділення з остатком.

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

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

ПРОГРАМНИЙ КОМПЛЕКС, БАГАТОЧЛЕН, ДІЛЕНННЯ, ДІЛИМЕ, ДІЛЬНИК, ОСТАТОК, ЦІЛОЧИСЕЛЬНЕ ДІЛЕННЯ, СТУПІНЬ

ЗМІСТ

ВСТУП…………………………………………………………………………	6
1 ТЕОРЕТИЧНИЙ МАТЕРІАЛ…….………………………………………...	7
1.1 Алгебраїчні вирази………………………………………………………..	7
1.2 Визначення многочлена…………………………………………………..	8
1.3 Дії над многочленами……………………………………………………..	10
1.4 Розкладення багаточленів на множники…………………………………	13
1.5 Возвратні рівняння………………………………………………………...	14
1.6 Використання многочленів для інтерполяції……………………………	15
2 ОПИС АЛГОРИТМУ…………………..…………………….......................	16
2.1 Алгоритм програми……………………………………………………….	16
3 ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМУ……………………………...	17
3.1 Блок-схема…………………………………………………………………	17
3.2 Мінімальні системні вимоги……………………………………………..	18
3.3 Інтерфейс користувача……………………………………………………	18
4 ПРИКЛАД РОБОТИ ПРОГРАМНОГО КОМПЛЕКСУ………………….	21
ВИСНОВКИ……………………………………………………………………	23
ПЕРЕЛІК ПОСИЛАНЬ………………………………………………………..	24
РЕЗЮМЕ……………………………………………………………………….	25
ДОДАТОК А. ЛІСТИНГ ПРОГРАМИ………………………………………	26

ВСТУП

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

Многочлени, дійсно, гранично прості: запис алгебри

f(x) = xn + a1xn–1 + a2xn–2 + ... + an–1x + an

(

є одночасно і формулою для обчислення значень многочлена. Хоча вирази типу cosx, ⁵√x, 10^x, log₂x набагато лаконичнее, з обчислювальної точки зору вони беззмістовні: для обчислення, скажемо чисел cos17°, ⁵√2, 10^0,13 чи log₂7 потрібні спеціальні наближені формули (або таблиці, складені за допомогою тих же формул). Як правило, в таких формулах з'являються многочлени.

Адже тригонометричні, статечні і тому подібне (елементарні) функції — це найпростіші з функцій аналізу, що вивчаються і використовуваних математиками, фізиками, інженерами. Відомий математик-обчислювач Р.В.Хеммінг в своїй книзі «Чисельні методи» (М., «Наука», 1972) пише: «Оскільки з многочленами легко звертатися, велика частина класичного чисельного аналізу грунтується на наближенні многочленами».

Оскільки обчислювати многочлени доводиться часто, то важливо навчитися робити це якомога простіше. Ми розповімо про еволюцію методів обчислення значень многочленів з моменту зародження (XVIIст) та про один з методів виконання цілочисельного ділення многочленів.

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

1 Теоретичний матеріал

1.1 Алгебраїчні вирази

Вирази алгебри розділяються на раціональних і ірраціональних.

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

Приклади раціональних величин.

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

Приклади ірраціональних величин.

Раціональні вирази бувають цілі і дроби

Цілий раціональний вираз по-іншому називається многочленом (поліномом). Многочленом називається раціональний вираз, в якому над змінній величиною проводяться тільки дії складання, віднімання і множення.

Приклади многочленів.

Многочлен n – й ступені відносно х

(1.1)

Многочленом нульового ступеня є не будь-яке рівне нулю число. Число нуль також многочлен тільки невизначеному ступеню. Кожен член многочлена називається одночленом. Ступінь змінної або сума ступенів змінних що входять в одночлен називається ступенем одночлена.

Приклад одночлена

(1.2)

Одночлен – окремий випадок многочлена. Найбільша із ступенів одночленів що входять в многочлен ступенем многочлена. Інше визначення многочлена: многочлен – сума одночленів.

Многочлен вигляду

(1.3)

- многочлен від однієї змінної.

Многочлен в склад, якого входять одночлени вигляду

(1.4)

Дробовим раціональним виразом або дробом алгебри називається відношення двох многочленів.

Приклад дробу алгебри

1.2 Визначення многочлена

У математиці, многочлени або поліноми від однієї змінної, це вирази вигляду

(1.5)

де ci фіксовані коефіцієнти, а x — змінна. Многочлени складають один з найважливіших класів елементарних функцій.

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

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

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

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

(1.6)

Многочлен вигляду називається одночленом або мономом

Одночлен, відповідний мультииндексу називається вільним членом.

У разі, коли многочлен має всього два ненульові члени, його називають двочленом або біномом

У разі, коли многочлен має всього три ненульові члени, його називають тричленом.

Повним ступенем (ненульового) одночлена називається ціле число .

Ступенем многочлена називається максимальна із ступенів його одночленів, тотожний нуль не має ступеня

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

Многочлен, який можна представити у вигляді твору многочленів нижчих ступенів з коефіцієнтами з даного поля, називається таким, що приводиться (над даним полемо), інакше — що не приводиться. Многочлени, що не приводяться, грають в кільці многочленів роль, схожу з роллю простих чисел в кільці цілих чисел. Наприклад, вірна теорема: якщо твір pq ділиться на многочлен л, що не приводиться, то p або q ділиться на л. Кожен многочлен, ступені більшої нуля, розкладається в даному полі в твір множників, що не приводяться, єдиним чином (з точністю до множників нульового ступеня).

Наприклад, многочлен x4 + 2, що не приводиться в полі раціональних чисел, розкладається на два множники в полі дійсних чисел і на чотири множники в полі комплексних чисел.

Взагалі, кожен многочлен від одного змінного x розкладається в полі дійсних чисел на множники першого і другого ступеня, в полі комплексних чисел — на множники першого ступеня (основна теорема алгебри).

Для двох і більшого числа змінних цього вже не можна затверджувати. Над будь-яким полем для будь-якого n > 2 існують многочлен від n змінних, що не приводяться в будь-якому розширенні цього поля. Такі многочлени називаються такими, що абсолютно не приводяться.

Властивості многочленів

Кільце многочленів над довільною областю цілісності само є областю цілісності.

Кільце многочленів від будь-якого кінцевого числа змінних над будь-яким факторіальним кільцем само є факторіальним.

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

Більш того, кільце многочленів від одного змінного над полем є евклидовым кільцем.

1.3 Дії над многочленами

Визначення. Два многочлени P(x) і Q(x) відносно х з будь-якими дійсними коефіцієнтами рахуватимемо рівними P(x)= Q(x) лише в тому випадку, якщо рівні їх коефіцієнти при однакових ступенях х.

Значення таких многочленів очевидно рівні. Існує твердження зворотне цьому: якщо значення двох многочленів рівні при всіх значеннях х, то такі многочлени рівні, їх коефіцієнти співпадають при однакових ступенях х.

Многочлени можна складати. Сумою двох многочленів P(x) і Q(x) називається многочлен, у якого коефіцієнт при кожному ступені х рівний сумі коефіцієнтів при тому ж ступені в многочленах P(x) і Q(x).

Многочлени можна віднімати. Різницею двох многочленів P(x) і Q(x) називається многочлен, у якого коефіцієнт при кожному ступені х рівний різниці коефіцієнтів при тому ж ступені в многочленах P(x) і Q(x).

Многочлени можна умножати. Щоб помножити два многочлени P(x) і Q(x), потрібно кожен член многочлена P(x) помножити на кожен член многочлена Q(x) і отримані результати скласти.

Складання, множення і віднімання многочленів – основні арифметичні дії над многочленами.

Хай P(x)= Q(x)S(x), P(x) і Q(x) два многочлени, причому ступінь многочлена P(x) не менше ступеня многочлена Q(x) і, якщо існує такий многочлен S(x), що виконується рівність

P(x)= Q(x)S(x), то говорять, що многочлен P(x) ділиться без остачі на многочлен Q(x). P(x), Q(x), S(x) називаються відповідно ділиме, дільник, приватне. Якщо такого многочлена не існує, то многочлен P(x) не ділиться на Q(x). В цьому випадку, як і при розгляді ділення з числами проводиться ділення із залишком.

Розділити многочлен P(x) на Q(x) із залишком це означає представити многочлен P(x) у вигляді рівності P(x)= Q(x)S(x)+ R(x), де R(x) залишок, причому ступінь R(x) менше ступеня Q(x) .При діленні многочленів із залишком справедлива наступна теорема.

Для будь-яких двох многочленів P(x) і Q(x) завжди можна знайти і притому однозначний два многочлени S(x) і R(x), для яких справедлива рівність P(x)= Q(x)S(x)+ R(x).

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

Приклад 1. Виконати ділення P(x)= x3 – 1 на Q(x)= x + 1. Виконаємо ділення кутом.

Звідси отримуємо x3 – 1 = ( x + 1)(x2 – x + 1) – 2. Приватне S(x)= x2 – x + 1, залишок R(x)= - 2.

Приклад 2. Виконати ділення P(x)= x4 +4x³ – 4x2 + x + 1 на Q(x)= x2 +2x + 1. Виконаємо ділення кутом.

Звідси отримуємо: x⁴ + 4x³ – 4x² + x + 1 = (x² +2x + 1)( x² + 2x – 9) +17 x + 10.

Можна знайти приватне від ділення двох многочленів методом невизначених коефіцієнтів

x⁴ +4x³ – 4x² + x + 1 = (x² +2x + 1)(ax² + bx + c) + dx + e

x⁴ +4x³ – 4x² + x + 1 = ax⁴ +(2a + b)x³ +(c + 2b + a)x² +(b + d + 2c)x + e + c

Прирівнюємо коефіцієнти при однакових ступенях

Отримуємо той же результат.

x⁴ + 4x³ – 4x² + x + 1 = (x² +2x + 1)( x² + 2x – 9) +17 x + 10

Коефіцієнти приватного многочлена на двочлен можна шукати з використанням визначення рівності двох многочленів.

Хай

P(x) = a₀xⁿ + a₁x^n-1 +…+ a_n-1x + a_n ; Q(x) = x – с; S(x) = b₀x^n-1 + b₁x^n-2 +…+ b_n-1.

Отримуємо

a₀xⁿ + a₁x^n-1 + … + a_n-1x + a_n = (x – с)( b₀x^n-1 + b₁x^n-2 + … + b_n-1) + R (1.7)

де R – число оскільки ступінь R менше ступеня x – з . Помножимо S(x) на Q(x) і отримаємо

a₀xⁿ + a₁x^n-1 + … + a_n-1x + a_n = b₀xⁿ + (b₁ - c b₀ )x^n-1 + … +(b_n-1 - c b_n-2 )x + R - c b_n-1 (1.8)

Звідси отримаємо

b₀ = a₀; b_k = cb_k-1 + a_k (k = 1, 2, 3,…, n), b_n = R . R= сb_n-1 + a_n (1.9)

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

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

Теорему Безу використовують для розкладання многочлена на множники.

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

Многочлен

P(x) = a₀xⁿ + a₁x^n-1 + … + a_n-1x + a_n (1.10)

приводимо на безлічі комплексних чисел, але не завжди приводиться на безлічі дійсних або раціональних чисел. Можна розглянути такий приклад. Многочлен P(x) = x² + 9 не приводимо на безлічі дійсних чисел, а на множині комплексних ми отримаємо наступне розкладання x² + 9 = (x + 3i)(x – 3i). Де i = - мнима одиниця. Многочлен P(x) можна представити у вигляді

P(x) = a₀(x – x₁)( x – x₂)…( x – x_n). (1.11)

Якщо провести множення двочленів і привести подібні, складаючи коефіцієнти при однакових ступенях, то отримаємо многочлен вигляду:

a₀xⁿ + a₁x^n-1 + … + a_n-1x + a_n = a₀(xⁿ – (x₁ + x₂ + …+ x_n)x^n-1 + (1.12)

(x₁x₂ + …+ x_n-1 x_n) x^n-2 + … +(-1)ⁿ x₁x_2…x_n).

За визначенням рівних многочленів порівняємо коефіцієнти при однакових ступенях многочленів.

(1.13)

Ці формули носять назву формул Вієта. Формули дозволяють по відомому корінню скласти рівняння, яке можна записати у вигляді

(1.14)

Для розкладання многочленів на множники корисно знати ще дві теореми.

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

a₀xⁿ + a₁x^n-1 + … + a_n-1x + a_n = a₀(x – x₁)( x – x₂)…( x – x_n). (1.15)

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

На підставі попередніх тверджень можна зробити такий вивід, що раціональне коріння рівняння з цілими коефіцієнтами слід шукати серед чисел вигляду де p і q – всілякі дільники (як позитивні, так і негативні!) відповідно вільного члена рівняння і коефіцієнта при старшому ступені. При знаходженні одного кореня ми можемо за допомогою схеми Горнера знизити ступінь многочлена на одиницю.

1.5 Возвратні рівняння

Рівняння четвертого ступеня ax⁴ + bx³ + cx² + dx + e = 0 называють возвратним, якщо при b ¹ 0 и a ¹ 0 рівняння задовольняє умові

(1.16)

Для рішення поділимо на x² ¹ 0, отримаємо рівняння виду:

Отримаємо рівняння

(1.17)

1.6 Використання многочленів для інтерполяції

Мета завдання про наближення (інтерполяції): дану функцію у(х) потрібно приблизно замінити деякою функцією j(х), властивості якої нам відомі так, щоб відхилення в заданій області було найменшим. інтерполяційні формули застосовуються, перш за все, при заміні графічно заданій функції аналітичною, а також для інтерполяції в таблицях.

Методи інтерполяції Лагранжа і Ньютона

Один з підходів до завдання інтерполяції — метод Лагранжа. Основна ідея цього методу полягає в тому, щоб перш за все знайти многочлен, який приймає значення 1 в одній вузловій точці і 0 у всіх інших. Легко бачити, сто функція є необхідним многочленом ступеня n; він рівний 1, если x=xj и 0, когда x=xi, i¹j. Многочлен Lj(x)×yj приймає значення yi в i-й вузловій точці і рівний 0 у всіх інших вузлах. З цього виходить, що є многочлен ступеня n, що проходить через n+1 крапку (xi, yi).

Інший підхід — метод Ньютона (метод розділених різниць). Цей метод дозволяє набути апроксимуючих значень функції без побудови в явному вигляді апроксимуючого полінома. В результаті отримуємо формулу для полінома Pn, що апроксимує функцію f(x):

P(x)=P(x0)+(x-x0)P(x0,x1)+(x-x0)(x-x1)P(x0,x1,x2)+…+ (1.18)

(x-x0)(x-x1)…(x-xn)P(x0,x1,…,xn);

— розділена різниця 1-го порядку;

— розділена різниця 2-го порядку і так далі

Значення Pn(x) у вузлах співпадають із значеннями f(x).

Фактично формули Лагранжа і Ньютона породжують один і той же поліном, різниця тільки в алгоритмі його побудови.