Генерация полиномов (стр. 2 из 4)
2. Сложение и умножение полиномов.
Пусть
и 
, где 
, 
, n, s – степени многочленов f(x) и g(x). Если n ≥ s (иначе переобозначим степени полиномов), то их суммой называется многочлен 
, коэффициенты которого получаются сложением коэффициентов f(x) и g(x), стоящих при одинаковых степенях переменного, т.е. 
, i = 0, 1, …, n. Степень суммы равна n, если n ≥ s, но при n = s она может оказаться меньше n, а именно в том случае если 
. [1, С. 132]Произведением многочленов f(x) и g(x) называется многочлен
, коэффициенты которого определяются следующим образом 
, так как , , то 
, поэтому степень произведения многочленов равна n + s. [1, С. 132]3. Замкнутость относительно сложения и умножения. Исходя из первых двух свойств многочлена, очевидно, что складывая или перемножая два каких-либо многочлена от одного и того же переменного с коэффициентами из К, мы получим однозначно многочлен с коэффициентами из того же кольца К.
1.1.4 Используемые в исследовании теоремы и их доказательства
Т1. [1, С. 134]
Для любых двух многочленов f(x) и g(x) можно на найти такие многочлены q(x) и r(x), что
f(x) = g(x) ∙ q(x) + r(x), (1.1)
причем степень r(x) меньше степени g(x) или же r(x) = 0. Многочлены q(x) и r(x), удовлетворяющие этому условию определяются однозначно.
Доказательство. [1, С. 134-135]
Докажем сперва вторую половину теоремы. Пусть существуют еще многочлены q1(x) и r1(x), также удовлетворяющие равенству
f(x) = g(x) ∙ q1(x) + r1(x), (1.2)
причем степень r1(x) меньше степени g(x) или равна нулю. Приравнивая друг другу правые части равенств (1.1) и (1.2), получим:
g(x) ∙ [q(x) – q1(x)] = r1(x) – r(x).
Степень правой части этого равенства меньше степени g(x), степень же левой части была бы при
больше или равна степени g(x). Поэтому должно быть q(x) – q1(x) = 0, т.е. q(x) = q1(x), а тогда и r(x) = r1(x), что и требовалось доказать.Переходим к доказательству первой половины теоремы. Пусть многочлены f(x) и g(x) имеют соответственно степени n и s. Если n < s, то можно положить q(x) = 0, r(x) = f(x). Если же n ≥ s, то воспользуемся методом деления многочленов с действительными коэффициентами, расположенных по убывающим степеням неизвестного. Пусть
Полагая
(1.3)мы получаем многочлен, степень которого меньше n. Обозначим эту степень через n1, а старший коэффициент многочлена f1(x) – через аn1. Положим, далее, если все еще n1 ≥ s,
(1.4)Обозначим эту степень через n2, а старший коэффициент многочлена f2(x) – через аn2. Положим, далее, если все еще n2 ≥ s,
(1.5)и т.д.Так как степень многочленов f1(x), f2(x), … убывают, n > n1 > n2 > …, то мы дойдем после конечного числа шагов до такого многочлена fk(x),
(1.k)степень которого nk меньше s, после чего наш процесс останавливается. Складывая теперь равенства (1.3), (1.4), (1.5), …, (1.k) мы получим:
т.е. многочлены
Действительно удовлетворяют равенству (1.2), причем степень r(x) действительно меньше степени g(x).
Т2. [1, С. 135]
Многочлен g(x) тогда и только тогда будет делителем многочлена f(x), если существует многочлен q(x), удовлетворяющий равенству
f(x) = g(x)
q(x) (2.1)Доказательство. [1, С. 135-136]
Если g(x) является делителем для f(x), то в качестве q(x) следует взять частное от деления f(x) на g(x).
Обратно, пусть многочлен q(x), удовлетворяющий равенству (2.1), существует. Из Т1 о единственности многочленов q(x) и r(x), удовлетворяющих равенству f(x) = g(x) ∙ q(x) + r(x) и условию, что степень r(x) меньше степени g(x), в нашем случае следует, что частное от деления f(x) на g(x) равно q(x), а остаток равен нулю.
Т3. [3, С. 106]
Если а – корень многочлена f(x), то f(x) делится на х – а.
Доказательство. [3, С. 106 -107]
Деление f(x) на х – а дает равенство f(x) = (x –a) ∙ q(x) +r(x). Подставим в это равенство х = а: 0 = r(x), откуда f(x) = (x –a) ∙ q(x).
Т4. Основная теорема алгебры. [1, С. 147]
Всякий многочлен с любыми числовыми коэффициентами, степень которого не меньше единицы имеет хотя бы один корень, в общем случае комплексный.
Доказательство.
См. [1, C.147 – 156]
Следствие 4.1 [1, С. 156]
Многочлен f(x) степени n над полем комплексных чисел имеет каноническое разложение с точностью до множителя нулевой степени вида f(x)=c ∙ (x – a1) ∙ (x – a2) ∙ … ∙ (x – an). Причем это разложение единственное.
Доказательство.
См. [1, С. 156-157]
Следствие 4.2
Всякий многочлен f(x) степени n, n ≥ 1, с любыми числовыми коэффициентами имеет n корней, если каждый корень считать столько раз, какова его кратность.
Доказательство.
См. [1, С. 157]
Из всех приведенных теорем и следствий наибольшее значение для данной курсовой работы имеют следствия 4.1 и 4.2, так как в них говориться, что любой многочлен в общем случае может разлагаться на многочлены первой степени с точностью до множителя нулевой степени, т.е. с точностью до числового коэффициента, и их количество с учетом кратности равно степени разлагаемого многочлена и что многочлены, входящие в каноническое разложение, содержат в себе все корни разлагаемого полинома, соответственно с учетом их кратности.
Это не маловажно, так как теперь можно говорить о том, что, имея степень генерируемого полинома и его корни, мы можем с точностью до числового коэффициента определить и получить необходимый полином указанной степени.
1.2 Генерация полиномов
Генерация достаточно молодая и полностью не исследованная область
информатики и программирования. Дать точного и полного определения, что такое генерация пока еще не возможно. Под генерацией в общем случае понимается процесс динамического изменения некоторых программных параметров. Теоретически генерация может быть случайной, однако на практике случайную генерацию организовать практически не возможно. Так, например, генерация случайных чисел (в действительности псевдо случайных) зависит от многих параметров (время, дата и т.д.). Тема этой курсовой работы генерация полиномов. В программе, реализующей алгоритм генерации полинома, происходит заведомо неслучайная генерация коэффициентов полинома, так как она зависит от двух параметров: степени полинома и его корней
Глава 2. Практическая часть по генерации полиномов
2.1 Алгоритм генерации полиномов
Исследовав теоретическую часть по проблеме генерации полиномов, приступил к практическому применению полученных знаний. Прежде, чем приступать к написанию кода программы, генерирующей полиномы по введенной пользователем степени и корням, составил алгоритм для решения данной задачи.
Алгоритм.
1. Ввести степень генерируемого полинома.
2. Если степень не была введена или был введен символ, не являющийся цифрой, или было введено число меньше двух, то выдать сообщение об ошибке и перейти к пункту 1, иначе, при корректном вводе, перейти к пункту 3.
3. Организовать цикл (количество итераций равно степени генерируемого полинома) для ввода корней генерируемого полинома.
4. Ввести корни генерируемого полинома.
5. Если корень не был введен или был введен символ, не являющийся цифрой, то выдать сообщение об ошибке и перейти к пункту 4, иначе, при корректном вводе, перейти к пункту 6.
6. После окончания работы цикла произвести перемножение введенных корней генерируемого полинома в соответствии с правилами перемножения полиномов (см. пункт 1.1.3.2)
7. Вывести получившийся полином в порядке убывания степеней переменной на экран.
2.2 Написание программы, реализующей алгоритм генерации полиномов
2.2.1 Преодоление проблем, возникших при написании программы
При написании кода программы, реализующей алгоритм генерации полиномов, столкнулись с рядом трудностей.
Во-первых, необходимо было реализовать проверку вводимых данных, чтобы вводимые значениями были только цифры и числа. Для преодоления первой проблемы был разработан следующий алгоритм, реализация которого будет приведена ниже.
1. Инициализировать цикл с постусловием.
2. Ввести значение в виде строки.