Курсоваяработа
ГЕНЕРАЦИЯПОЛИНОМОВ
Оглавление
Введение
Глава 1. Теоретическая часть погенерации полиномов
1.1 Теория полиномов
1.1.1 Основные определения,используемые в теории полиномов
1.1.2 Определение полинома
1.1.3 Основные свойства полиномов
1.1.4 Используемые в исследованиитеоремы и их доказательства
1.2 Генерация полиномов
Глава 2. Практическая часть погенерации полиномов
2.1 Алгоритм генерации полиномов.
2.2 Написание программы, реализующейалгоритм генерации полиномов
2.2.1 Преодоление проблем, возникшихпри написании программы
2.2.2 Описание и пояснение некоторых частейпрограммы
2.3 Листинг программы, реализующейалгоритм генерации полиномов
Заключение
Список использованных источников илитературы
Приложение
Введение
В данной курсовой работерассмотрена проблема генерации полиномов (многочленов) по их введенным корням.Целью курсовой работы явилась разработка действенного алгоритма и написание наего основе программы, которая генерирует полином по его введенным корням. Проблемаразработки алгоритма для генерации полиномов и написание на его основепрограммы является практически актуальной, так как ни для кого не секрет, что впоследнее время на рынке литературы широко распространены так называемые«решебники». В них можно найти не только решения к заданиям из учебников, но ик заданиям из методической литературы, из которой учителя составляютконтрольные и прочие работы для проверки знаний учащихся. В связи с этим,знания учащихся снижаются, а «успеваемость», которая перестала быть истиннымкритерием знаний учащегося, растет. Поэтому у учителей остается один выход –самим составлять проверочные работы. Однако временные возможности учителяограничены, и он просто не в состоянии составить оригинальные задания на целыйкласс. Составленный алгоритм и программа, реализующая его, способны облегчитьтруд учителя в свете этой проблемы, так как за очень короткое время программныйпродукт способен сгенерировать полином по его введенной степени и корням.Соответственно, не прикладывая ни каких больших умственных усилий, а значит ибольших временных ресурсов, учитель сможет составить множество оригинальныхзаданий, при этом у него останется время для других не менее важных дел.
Данная курсовая работасостоит двух глав, включающих в себя каждый несколько параграфов и подпунктов.
В первой главе приведенатеоретическая часть по генерации полиномов, включающая основные понятия иопределения теории полиномов, основные теоремы алгебры и теории полиномов,дающие научную основу для разработки алгоритма генерации полиномов и написаниина его основе программы.
Во второй главерассказывается об основных проблемах, с которыми я столкнулся при составленииалгоритма и написании программы, приводится алгоритм генерации полиномов,описываются некоторые важные части программы, основывающейся на алгоритме, иприводится листинг программного продукта.
В заключении говорится о проблемах,с которыми столкнулся при составлении алгоритма и написании на его основепрограммы и о путях усовершенствования предложенного алгоритма и программы.
Глава 1. Теоретическая часть по генерации полиномов 1.1 Теория полиномов 1.1.1 Основные определения, используемыев теории полиномов
В первой главе этот пунктможно назвать одним из важнейших, так как в его содержании будут приведеныопределения основных понятий алгебры и теории полиномов, без которых непредставлялось бы возможным понимание всего того, о чем будет говориться востальных параграфах и главах.
Определение 1. Множество – набор, совокупность,собрание каких-либо объектов, называемых его элементами, обладающими общим длявсех них характеристическим свойством. [4, С. 382]
Определение 2. Бинарная операция – правило, покоторому каждой паре (a, b) элементов множества G однозначно ставится в соответствие некоторый элемент с тогоже множества G. [7, С. 11]
Определение 3. Множество R, в котором заданы две бинарные операции + (сложение) и(умножение), называется полем, если выполняются следующие условия (аксиомы поля):
Сложение:
1. Коммутативность: a + b = b + a.
2. Ассоциативность: a + (b + c) = (a + b) + c.
3. Существованиенуля: существует такой элемент 0,
что а + 0 = а для любогоэлемента а.
4. Существованиепротивоположного: для любого элемента, а существует такой элемент (-а), что а +(-а) = 0.
Умножение:
1. Коммутативность: a ∙ b = b ∙ a.
2. Ассоциативность: a ∙ (b ∙ c) = (a ∙ b) ∙c.
3. Существованиеединицы: существует такой элемент 1, что а∙1 = а для всякого элемента а.
4. Существованиеобратного: для любого элемента а ≠ 0 существует такой элемент а-1,такой что а ∙ а-1 = 1.
Сложение и умножение:
Дистрибутивность: a ∙ (b + c) = a ∙ b + а ∙c. [2, С. 16]
Определение 4. Коммутативным кольцом называетсямножество, в котором выполняются аксиомы поля, кроме, может быть, требованиясуществования обратного элемента а-1 для любого а ≠ 0. [2, С.23]
Определение 5. Пусть S – множество. Отображение S * S → S – закон композиции – общее названиедля операции, производящей из двух элементов a, b/>S третий элемент c/>S. [4, С. 279]
Определение 6. Моноид – множество G с ассоциативным законом композиции.[4, С. 386]
Определение 7. Если f(c) = 0, т.е. многочленf(x) обращается в нуль при подстановке в него числа с вместонеизвестного, то с называется корнем многочлена f(x). [1, С. 144]
Определение 8. Ненулевой элемент кольца,произведение которого на некоторый ненулевой элемент равно нулю, называется делителемнуля. [4, С. 176]
Определение 9. Кольцо называется целостным (илиобластью целостности), если оно коммутативно и не содержит делителей нуля. [2,С. 26]
Определение 10. Многочлен называется приводимым вкольце многочленов, если у него существуют делители со степенью больше нуля, номеньше степени полинома, иначе неприводимым. [6, С. 54] 1.1.2 Определение полинома
В математике и ееразделах существует несколько определений такого понятия как полином. Здесь идалее будем называть полином также степенным многочленом или простомногочленом. Приведем некоторые из них.
Первое определение взятоиз [3, С. 60]
Пусть R – некоторое кольцо. Построим спомощью нового, не принадлежащего кольцу R, символа х выражение вида f(х) = ∑аvxv, в которых суммирование ведется по какому-то конечному множествуцелочисленных значений индекса v≥0и «коэффициенты» аvпринадлежат кольцу R. Такие выраженияназываются многочленами; символ х называется переменной, v – степенью полинома.
Второе определение взятоиз [7, С. 131-133]
Пусть S – некоторое множество и N – моноид натуральных чисел.Обозначим через N(S) множество функций S → N,которые равны 0 для почти всех элементов из S. Пусть х/>S и t/>N. Всякий элемент р/>N(S) имеетединственное представление в виде произведения />,где v: S→N –отображение, для которого v(x) = 0 при почти всех х. Такоепроизведение назовем примитивным многочленом и будем обозначать />или просто />.
Пусть А — коммутативное кольцо. Тогда можно образовать множествомоноидов A[N(S)] над А, которуюбудем называть кольцом многочленов от S над A. По определению всякий элемент из A[N(S)] имеетединственное представление в виде линейной комбинации />, где (v) пробегает все отображения множестваS в N, обращающиеся в ноль для почти всех (v). Элементы из А[N(S)] называются многочленами от S над А. Элементы /> называютсякоэффициентами многочлена. Если Sсостоит из одного символа Х, то всякий многочлен может быть записан в виде
/>,
где /> и n – некоторое целое число ≥ 0, называющееся степеньюполинома.
Ниже приведенноеопределение взято из [1, С. 130]
Многочленом (илиполиномом) n-й степени от неизвестного хназывается сумма выражений с целыми степенями:
/>.
Коэффициенты /> будем считатьпроизвольными числами, причем старший коэффициент /> долженбыть отличен от нуля. Для сокращенной записи многочленов употребляются символы f(x), g(x) и т.д.
В данной курсовой работеможно использовать любое из приведенных определений полинома, но в общемпоследнее определение полинома проще для понимания, но имеет не мене глубокийсмысл, чем остальные, так как позволяет взглянуть на полином как на некотороеформальное выражение вполне определенное набором своих коэффициентов (чтогораздо упрощает работу с полиномами при их генерации) с одной стороны и как нафункцию от переменного Х (с точки зрения математического анализа) с другойстороны. 1.1.3 Основные свойства полиномов
1. Равенство одногополинома другому.
Два многочлена f(x) и g(x) будут считаться равными (илитождественно равными), f(x) = g(x), в том случае,если равны их коэффициенты при одинаковых степенях неизвестного. [1, С. 131]
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
/>
Полагая
/> (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. Ввести значение ввиде строки.
3. Инициализироватьцикл (количество итераций равно длине введенной пользователем строки).
4. Перемещаться вовведенной строке посимвольно.
5. Если символ цифраперейти к пункту 6, иначе перейти к пункту 8.
6. Переводим символв цифру.
7. Прибавляем цифру кчислу, которое будет являться переводом введенной строки, если она число, предварительноумноженное его на десять.
8. Выдаем сообщениеоб ошибке и переходим к пункту 2.
9. Запоминаемполучившееся число при корректном вводе.
Второй проблемой явилосьпереполнение типа данных – long приперемножении (в данной программе, написанной на языке С). Однако она быларешена при написании функций проверки при перемножении и общей проверкикоэффициентов генерируемого полинома, которые будут приведены ниже.
Третья проблема –переполнение буфера. При написании программы пришлось увеличить буфер для вводазначений, но при считывании рассматривать только первые девять символов, чтобызаведомо не превысить максимальное значение используемого типа, и, если быловведено более девяти символов, то выдать сообщение об ошибке и попроситьпользователя заново ввести значение.
Четвертая проблема –хранение введенных данных. Для ее преодоления было использовано четыре массива;в первом (массив m)будут хранитьсявсе корни генерируемого полинома (его размер – 2∙n, где n –степень генерируемого полинома), второй и третий – вспомогательные (участвуют вперемножении), в третьем (массив b) будетхраниться корень генерируемого многочлена, взятый из первого массива, (егоразмер – 2); во втором (массив a) вначалехраниться корень генерируемого многочлена из первого массива, а после первогоперемножения в него будет перезаписываться результат перемножения дляследующего выполнения этой операции (размер – n+1); последний массив (массив c) – результирующий, содержит все коэффициенты генерируемогомногочлена после перемножения (размер n+1). 2.2.2 Описание и пояснение некоторых частейпрограммы
В данном пункте будутприведены некоторые части программы, реализующей алгоритм генерации полиномов,с пояснениями.
1. Функцияреализующая нахождение модуля числа типа long
longModul(long a)
{
if(a
return(-a);
else
return(a);
}
Если функция получилаотрицательное число, то она возвращает число с противоположным знаком, впротивном случае само число.
Входные данные – числотипа long.
Выходные данные – числотипа long.
2. Функция проверкивозможности выхода за диапазон типа long при перемножении корней генерируемого полинома.
intprovper(long a, long b)
{
if(b==0|| a==0)
return(1);
else
if(Modul(a)
return(1);
else
return(0);
}
Если одно из переданныхфункции значений равно нулю, то функция возвращает единицу, иначе, еслиабсолютное значение одного из полученных функций значений меньше, чем числоравное частному от деления максимального значения типа long на другое введенное значение, т.е., если приперемножении полученных функцией значений, их произведение не выходит задиапазон типа long, то функция возвращает единицу, впротивном случае – ноль.
Входные данные – двачисла типа long.
Выходные данные – числотипа int (единица или ноль).
3. Функция проверкивыхода за диапазон при сложении коэффициентов генерируемого полинома приодинаковых степенях переменного.
int provsum(longa, long b)
{
if(Modul(a)
return(1);
else
return(0);
}
Если одно из переданныхфункции значений меньше, чем разность максимального значения типа long и другого переданного значения, тофункция возвращает единицу, в противном случае – ноль.
Входные данные – двачисла типа long.
Выходные данные – числотипа int (единица или ноль).
4. Функция,перемножающая два многочлена.
void peremnoz(long *a, int n, long *b, long *c)
{
longz=0;
inti,j;
for (i=0; i
for(j=0; j
{
if(provper(*(a+i),*(b+j))==1)
z=(*(a+i)*(*(b+j)));
else
*(c+(i+j))=MAXLONG;
if(provsum(z,*(c+(i+j)))==1)
*(c+(i+j))+=z;
else
*(c+(i+j))=MAXLONG;
}
}
В функцииинициализируются два цикла, один из которых вложен в другой. Внешний пробегаетпо всем коэффициентам первого многочлена, участвующего в перемножении (впрограмме реализуется в виде массива a, а коэффициенты многочлена – элементы массива а), внутренний – покоэффициентам второго многочлена (в программе – в виде массива b, коэффициенты многочлена – элементымассива b). Если перемножение коэффициентов(элементов массивов) возможно (начинает работу функция int provper(long a, long b)), т.е. не произойдет выход за диапазон типа long, то результат перемножениязаписываем в переменную z, впротивном случае, соответствующему коэффициенту результирующего многочлена (впрограмме – массив c, коэффициентымногочлена – элементы массива) присваивается максимальное значение (MAXLONG) типа long и внутренний цикл прекращает свою работу. Если произведениекоэффициентов массива не вышло за диапазон типа long, то проверяем: не произойдет ли выход за диапазонтипа long при сложении получившегося значения(храниться в переменной z) скоэффициентом результирующего многочлена (элемент массива c) (начинает работу функция int provsum(long a, long b)); если сложение возможно, то к соответствующемукоэффициенту результирующего многочлена (элемент массива c) прибавляется результат перемножениякоэффициентов первых двух многочленов (значение переменной z), иначе, соответствующемукоэффициенту результирующего многочлена присваивается максимальное значение (MAXLONG) типа long.
Работа функцииперемножения основана на свойствах полинома (см. пункт 1.1.3).
Входные данные: триуказателя типа long (на массивы,участвующие в перемножении, и на результирующий массив), число типа int (количество элементов первогомассива).
5. Функция проверкинахождения коэффициентов генерируемого полинома в диапазоне используемого типа.
int prov(long*a, int n)
{
inti, y=0;
for(i=0;i
if(Modul(*(a+i))==MAXLONG)y++;
return(y);
}
В функцииинициализируется цикл (количество итераций равно степени генерируемогомногочлена, увеличенной на единицу). Производим движение по коэффициентамгенерируемого многочлена (элементам массива a); если абсолютное значение какого-либо коэффициентагенерируемого многочлена равно максимальному значению (MAXLONG) типа long,то значение флага (переменной y),изначально равное нулю, увеличиваем на единицу.
Входные данные: указательтипа long (на массив a), число типа int(степень генерируемого полинома, увеличенная на единицу).
Выходные данные: числотипа int.
6. Часть программы,переводящая символ, являющийся цифрой, в число.
{
w=s[i]-'0';
q=10*q+w;
x=1;
}
Если введенный символ –цифра, то из кода этого символа вычитаем из кода символа код нуля и получаемчисло, соответствующее введенному символу. 2.3 Листинг программы, реализующей алгоритм генерацииполиномов
#include
#include
#include
#include
#include
#include
#include
#include
longModul(long a)
{
if(a
else return(a);
}
intprovper(long a, long b)
{
if(b==0|| a==0) return(1);
else
if(Modul(a)
elsereturn(0);
}
intprovsum(long a, long b)
{
if(Modul(a)
else return(0);
}
void peremnoz(long *a, int n, long *b, long *c) {
long z=0;
inti,j;
for (i=0; i
for(j=0; j
{
if(provper(*(a+i),*(b+j))==1)
z=(*(a+i)*(*(b+j)));
else*(c+(i+j))=MAXLONG;
if(provsum(z,*(c+(i+j)))==1)
*(c+(i+j))+=z;
else*(c+(i+j))=MAXLONG;
}
}
int prov(long*a, int n)
{
inti, y=0;
for(i=0;i
if(Modul(*(a+i))==MAXLONG)y++;
return(y);
}
void main()
{
int stepen=0,n=2, w, x=0, i, k, f=1;
long *a, *b,*m, *c, q=0, z;
char *s;
s=(char *)calloc(900, sizeof(char ));
clrscr();
do{
printf(«Введите степень не меньшую,чем 2 и не большую, чем 100:»);
gets(s);
if(strlen(s)
{
printf("\nНе было введено значения. Повторите ввод\n");
x=0;
}
if(strlen(s)>9)
{
printf("\nВведено более 9 символов. Повторите ввод\n");
x=0;
}
else
{
for(i=0;i
if(isdigit(s[i])!=0)
{
w=s[i]-'0';
q=10*q+w;
x=1;
}
else
{
printf("\nВведен символ или пробел. Повторите ввод\n");
x=0;
break;
}
stepen=q;
free(s);
s=(char*) calloc(900, sizeof(char ));
q=0;
w=0;
}
}while(stepen100 || x==0);
clrscr();
a=(long *)calloc(stepen+1, sizeof(long ));
b=(long *)calloc(2, sizeof(long ));
m=(long *)calloc((stepen)*2, sizeof(long ));
c=(long *)calloc(stepen+1, sizeof(long ));
for(i=0;i
{
if(i%2==0)
{
do{
q=0;
printf(«Введите корень многочлена #%d », (i/2)+1);
gets(s);
if(strlen(s)
{
printf("\nНе было введено значения. Повторите ввод\n");
x=0;
}
if(strlen(s)>9)
{
printf("\nВведено более 9 символов. Повторите ввод\n");
x=0;
}
else
{
if(s[0]=='-')
for(k=1;k
if(isdigit(s[k])!=0)
{
w=s[k]-'0';
q=10*q+w;
x=1;
f=-1;
}
else
{
printf("\nВведен символ или пробел. Повторите ввод\n");
x=0;
break;
}
else
for(k=0; k
if(isdigit(s[k])!=0)
{
w=s[k]-'0';
q=10*q+w;
x=1;
f=1;
}
else
{
printf("\nВведен символ или пробел. Повторите ввод\n");
x=0;
break;
}
}
free(s);
s=(char*) calloc(900, sizeof(char ));
}while(x==0);
if(f==1)
{
*(m+i)=q;
q=0;
w=0;
*(m+i)=-*(m+i);
}
else
if(f==-1)
{
*(m+i)=q;
q=0;
w=0;
}
}
else*(m+i)=1;
}
for(i=0;i
{
*(a+i)=*(m+i);
*(b+i)=*(m+2+i);
}
for(k=0;k
{
peremnoz(a,n,b,c);
for(w=0; w
{
*(a+w)=*(c+w);
*(c+w)=0;
}
for(w=0;w
*(b+w)=*(m+(i*n)+w);
n++;
}
clrscr();
if(prov(a,stepen)!=0)
{
printf("\nПроизошел выход за диапазон типа.");
printf("\n\nПри следующемиспользовании данного программного продукта будьте осторожны с\n вводимыми значениями степени икорней");
printf("\n\nСпасибо, чтопользовались моим прогаммным продуктом!:)");
printf("\n\nНажмите любуюкнопку.");
}
else
{
printf("\Генериремый полином:\n");
printf(«x^%d»,stepen);
for(i=stepen-1;i>0;i--)
{
if(i==1)
if(*(a+i)==-1)printf("-x");
else
if(*(a+i)==1)printf("+x");
else
if(*(a+i)
else
if(*(a+i)>0)printf("+%ldx",*(a+i);
else n++;
else
if(*(a+i)==-1)printf("-x^%d",i);
else
if(*(a+i)==1)printf("+x^%d",i);
else
if(*(a+i)
printf("%ldx^%d",*(a+i),i);
else
if(*(a+i)>0)
printf("+%ldx^%d",*(a+i),i);
else n++;
}
if(a[0]
else
if(a[0]>0)printf("+%ld",a[0]);
else n--;
printf("=0");
printf("\n\nСпасибо, чтопользовались моим прогаммным продуктом!:)");
printf("\n\nНажмите любуюкнопку.");
}
free(a);
free(b);
free(c);
free(m);
free(s);
getch();
}
Входные данные: числатипа long.
Выходные данные: числатипа long.
1. При введенных значенияхстепени и корней генерируемого полинома, не допускающих выход за диапазон типа long, – коэффициенты генерируемогомногочлена с соответствующими степенями переменных.
2. При не корректновведенных значениях:
1. Если при вводе степенивведено число меньше двух и больше 100, то выдается сообщение о не корректномвводе с просьбой повторить ввод заново.
2. Если не было введенозначение степени или корня полинома, то выдается сообщение о не корректномвводе с просьбой повторить ввод заново.
3. Если было введеноболее девяти символов, то выдается сообщение о не корректном вводе с просьбойповторить ввод.
4. Если был введен символили пробел, то выдается сообщение о не корректном вводе с просьбой повторитьввод.
5. Если произошел выходза диапазон типа long, то выдаетсясообщение о не корректном вводе с просьбой при следующем использовании данногопрограммного продукта быть аккуратными при вводе степени генерируемого полиномаи его корней, чтобы не допустить выход за диапазон используемого типа.
Результаты теста данногопрограммного продукта можно увидеть в Приложении.
Заключение
В заключение даннойкурсовой работы хотелось бы кратко сказать о проделанной работе, о проблемах, скоторыми столкнулся при выполнении поставленной цели, и о перспективах развитияи улучшения данного программного продукта.
Целью данной курсовойработы было составить алгоритм генерации полиномов по введенной степени икорням и написать программу, реализующую этот алгоритм.
Чтобы выполнитьпоставленную цель, необходимо было решить три задачи:
1. Поиск литературы по предмету даннойкурсовой работы.
2. Составление алгоритма для выполненияпоставленной цели.
3. Написание программы, реализующейсоставленный алгоритм.
При решении третьейзадачи столкнулся с рядом трудностей:
1. Организацией ввода значений и проверкиего корректности. Необходимо было проверять, чтобы введенные значения являлисьтолько числами.
2. Организацией хранения введенныхданных для удобного обращения к ним в ходе написания и работы программы.
3. Проверки, чтобы при работе программыне произошел выход за диапазон используемого типа.
Основными источниками,помогавшими выполнить поставленную цель, явились:
1. Книги по линейной алгебре, в которыхсодержался материал по теории полиномов.
2. Книги по информатике ипрограммированию.
3. Курс лекций, прочитанных в рамкахдисциплин «Программирование на языке Си», «Информатика», «Структуры и алгоритмыкомпьютерной обработки данных», «Алгебра и теория чисел».
Результатом даннойкурсовой работы стал алгоритм генерации полиномов и написанная на его основепрограмма. Данная программа предназначена для работы с целыми числами, хотяалгоритм является действенным и при работе с вещественными числами, а принекоторых его усовершенствованиях (организации работы с мнимой частью) и с комплексными.Следовательно, одной из перспектив развития данного алгоритма является егоулучшение для работы с комплексными числами, а программы – написание ее дляработы со всеми числами: целыми, вещественными, комплексными.
Так же реально улучшить временнуюхарактеристику алгоритма и программы, если после проверки «не вышло липроизведение или сумма коэффициентов многочлена» за диапазон типа, если все же выходпроизошел, сразу же остановить работу алгоритма и программы и выдатьпользователю сообщение об ошибке.
Чтобы более полноиспользовать возможности алгоритма, его лучше реализовывать на тех языкахпрограммирования, у которых типы данных имеют достаточно большие диапазоны.
Решив последнюю задачу, можносразу решить такие задачи, как увеличение вводимого значения степенигенерируемого полинома и количества вводимых символов и буфера.
Не трудно заметить, чтопри перемножении вещественных чисел с дробной частью количество цифр в дробнойчасти их произведения будет равно, в общем случае, сумме количества символовперемножаемых чисел, поэтому количество символов в дробной части произведенияпри большом количестве символов в дробной части перемножаемых чисел достаточнобыстро увеличивается.
Следовательно, одной изсерьезнейших проблем при работе с вещественными и комплексными числами встаетпроблема точности, которую, в принципе на все сто процентов разрешить никогдане удастся, так как программист всегда будет ограничен в ресурсах, поэтомупредставить вещественные можно только лишь с определенной точностью, иногдавполне достаточной.
Надеюсь, что мой опыт вразработке подобных программных продуктов будет полезен другим людям, и даннаяпрограмма из области исследования при выполнении курсовой работы, при условии,конечно же, его усовершенствования, выйдет в свет как полностью готовый киспользованию программный продукт и будет востребован не только в целяхметодических разработок.
Список использованных источников и литературы
1. КурошА.Г. Курсвысшей алгебры / А.Г. Курош. – М.: Наука, 1968. – 431с.
2. Шафаревич И.Р.Основные понятия алгебры / И.Р. Шафаревич. – Ижевск: Ижевская республиканскаятипография, 1999. – 348с.
3. Варден ван дерБ.Л. Алгебра / Б.Л. ван дер Варден. – М.: Наука, 1979. – 623с.
4. Математика. Большойэнциклопедический словарь / Гл. ред. Ю.В. Прохоров. – 3-е изд. – М.: БольшаяРоссийская энциклопедия, 1998. – 848 с.: ил.
5. Подбельский В.В. ЯзыкСи++: Учебное пособие. – 5 –е изд. / В.В. Подбельский. – М.: Финансы истатистика, 2003. – 560с.: ил.
6. Устян А.Е.Методические материалы по курсу «Алгебра и теория чисел» для студентов –государственников / А.Е. Устян. – Тула: Тул.гос.пед.ун –т им. Л.Н. Толстого,1992. – 86с.
7. Зарисский О.Коммутативная алгебра. Том I / О.Зарисский, П. Самюэль. – М.: Издательство иностранной литературы, 1963. – 371с.
8. Ленг С. Алгебра /С. Ленг. – М.: Наука, 1999. – 564с.
Приложение
Таблица тестов
В таблице приведенырезультаты некоторых тестов программы.
Обратите внимание на то,что в скобках показаны некорректно введенные данные и сообщения программы обошибках с просьбами повторить ввод.номер теста входные данные выходные данные 1
2;
1, 2 x^2-3x+2=0 2
3;
1, 2, 3 x^3-6x^2+11-6=0 3
10;
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
x^10-10x^9+45x^-120x^7+210x^6-
-252x^5+210x^4-120x^3 + 45x^2-10x+1 4
4;
1234, 4321, 23 ,32 Произошел выход за диапазон типа 5
2;
999999999, 1 x^2-10000000000x+999999999 6
2;
0, 0 x^2=0 7
(-4),(1), 3;
(q), ( ), 0, 1, 100
(Введен символ или пробел повторите ввод), (Введите степень не меньшую, чем 2, и не большую, чем 100), (Введен символ или пробел повторите ввод), (Не было введено значения),
x^3-101x^2+100x=0 8
5;
-1, 1, -2, 2, 0 x^5-5x^3+4x=0 9
10;
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
x^10-45x^9+870x^8-9450x^7+63273x^6-
-269325x^5+723680x^4-1172700x^3+
+1026576x^2-362880x 10
25;
1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7 Произошел выход за диапазон типа