|
|
| Генерация полиномов |
то не маловажно, так как теперь можно говорить о том, что, имея степень генерируемого полинома и его корни, мы можем с точностью до числового коэффициента определить и получить необходимый полином указанной степени. 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. Функция реализующая нахождение модуля числа типа longlong Modul(long a) { if (a<0) return (-a); else return (a); }Если функция получила отрицательное число, то она возвращает число с противоположным знаком, в противном случае само число.Входные данные - число типа long.Выходные данные - число типа long.2. Функция проверки возможности выхода за диапазон типа long при перемножении корней генерируемого полинома.int provper(long a, long b) Если одно из переданных функции значений равно нулю, то функция возвращает единицу, иначе, если абсолютное значение одного из полученных функций значений меньше, чем число равное частному от деления максимального значения типа long на другое введенное значение, т.е., если при перемножении полученных функцией значений, их произведение не выходит за диапазон типа long, то функция возвращает единицу, в противном случае - ноль.Входные данные - два числа типа long.Выходные данные - число типа int (единица или ноль). 3. Функция проверки выхода за диапазон при сложении коэффициентов генерируемого полинома при одинаковых степенях переменного.int provsum(long a, long b) { if(Modul(a)<(MAXLONG-Modul(b))) return(1); else return(0); }Если одно из переданных функции значений меньше, чем разность максимального значения типа long и другого переданного значения, то функция возвращает единицу, в противном случае - ноль.Входные данные - два числа типа long.Выходные данные - число типа int (единица или ноль). 4. Функция, перемножающая два многочлена.void peremnoz (long *a, int n, long *b, long *c) { long z=0; int i,j; for ( i=0; i<n;i++) for( j=0; j<2; 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) { int i, y=0; for(i=0;i<n+1;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 <stdio.h>#include <conio.h>#include <math.h>#include <string.h>#include <ctype.h>#include <stdlib.h>#include <values.h>#include <time.h>long Modul(long a) { if (a<0) return (-a); else return (a); }int provper(long a, long b) int provsum(long a, long b) { if(Modul(a)<(MAXLONG-Modul(b))) return(1); else return(0); }void peremnoz (long *a, int n, long *b, long *c) { long z=0; int i,j; for ( i=0; i<n;i++) for( j=0; j<2; 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) { int i, y=0; for(i=0;i<n+1;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)<1) {printf("\nНе было введено значения. Повторите ввод\n"); x=0; }if(strlen(s)>9) {printf("\nВведено более 9 символов. Повторите ввод\n"); x=0; }else { for( i=0;i<strlen(s); 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( stepen<2 || stepen>100 || 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<stepen*2;i++){ if(i%2==0) { do{ q=0; printf("Введите корень многочлена #%d ", (i/2)+1); gets(s); if(strlen(s)<1) {printf("\nНе было введено значения. Повторите ввод\n"); x=0; } if(strlen(s)>9) {printf("\nВведено более 9 символов. Повторите ввод\n"); x=0; } else { if(s[0]=='-') for(k=1; k<strlen(s); 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<strlen(s);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<2;i++) { *(a+i)=*(m+i); *(b+i)=*(m+2+i); }for( k=0;k<stepen-1;k++) { peremnoz(a,n,b,c); for( w=0; w<n+1; w++) { *(a+w)=*(c+w); *(c+w)=0; } for(w=0;w<2;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)<0) printf("%ldx",*(a+i)); elseif(*(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)<0)printf("%ldx^%d",*(a+i),i); elseif(*(a+i)>0) printf("+%ldx^%d",*(a+i),i); else n++; } if(a[0]<0) printf("%ld",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 | Произошел выход за диапазон типа | | |
Страницы: 1, 2
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
