多项式乘法的实现.doc

目录一、设计目的1二、设计内容11) 问题描述12) 基本要求11.需求分析12.问题求解13、总体设计34. 详细设计45.调试与测试46.关键源程序清单4三、系统测试5四、 总结6五、 附件（系统测试的图表）8多项式乘法的实现一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计内容一元多项式乘法1) 问题描述已知A(x)=a0+a1x+a2x2+am xm和B(x)=b0+b1x+b2x2+bn xn，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)*B(x)。2) 基本要求(1)设计存储结构表示一元多项式；(2)设计算法实现一元多项式乘法；(3)分析算法的时间复杂度和空间复杂度。1.需求分析程序是要完成两个一元多项式乘法的功能。要求输入两个多项式中每个数据项的系数和指数，从而得到一个新的多项式，这个多项式是输入的两个多项式的乘积。多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的计算时(a+b)(m+n)，先把(m+n)看成一个单项式，(a+b) 是一个多项式，运用单项式与多项式相乘的法则，得到(a+b)(m+n)=a(m+n)+b(m+n),然后再次运用单项式与多项式相乘的法则。2.问题求解 一元多项式的乘法是在初中学到的数学知识，我们当时是这样做 的：用第一个数据项的每一项去乘另一个多项式，得到的结果加起来， 然后合并同类项，按照升序，或者降序的方法给得到的多项式进行排 序，这样就得到了结果。 用数据结构来解决这个问题的话，首先要设计多项式的存储结构，然后设计算法 ，这个时候要注意的就是算法的时间复杂度和空间复杂 度。在本次实验里，我用的是一维数组来表示一个一元多项式。其中数组中每个数据的下标表示多项式中数据项的指数，数据的值来表示 此数据项的系数。 通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就失去了意义， 在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数信息。 第一个问题就是要定义几个数组，因为是要对两个多项式计算乘积，所以，我定义了三个数组，两个数组表示要计算的两个多项式， 第三个数组用来表示求得的数组。 第二个问题就是怎么定义数组的长度。为了便于验证试验，我给要输入的两个数组的长度分别定义为M、N，既它们的数据项中指数最两个指数为M-1、N-1的数据项相乘，其结果数据项的指数为M+N-2，所以目标多项式中出现的最大指数就是M+N-2，因此定义目标数组的长 度为M+N-1（0M+N-1）。 第三个问题为了美观，系数为0的数据项就不要显示出来了。在 输出结果时，用到一个条件结构。只输出系数不为0的数据项。 3、总体设计开始 输入aM,bN 定义cM+N-1,且都初始化为0Cm+n=am+bn输出cM+N-1结束4、 详细设计 用数组a表示第一个多项式，其中ai表示多项式A中的指数为m的系数，数组b表示第二个多项式，其中bi表示多项式B中的指数为n的系数。A中指数为m的项与B中指数为n的项相乘，结果是得到指数为m+n的项，而且这个项的系数为am*bn.把这个系数保存在数组c的cm+n中。5.调试与测试方案一： 初始化两个一元多项式的时候输入几个系数为0的数据项，检验程序是否正常运行。方案二： 初始化数组的时候，输入负数，检验程序是否出现错误。6.关键源程序清单源程序： #include #define M 2#define N 2void main()int aM,bN,cM+N-1; /ai表示多项式A中指数为i的系数。printf(请输入多项式A中依次的系数n); /*创建第一个多项式*/for (int i=0;iM;i+)scanf(%d,&ai); printf(多项式A为:A(X)=); /*打印第一个多项式*/for ( i=0;iM;i+) if(ai!=0) printf(%d*X%d+,ai,i); printf(n请输入多项式B中依次的系数n); /*创建第二个多项式*/ for (int j=0;jN;j+) scanf(%d,&bj);printf(多项式B为:B(X)=); /*打印第二个多项式*/ for (int t=0;tN;t+) if(bt!=0) printf(%d*X%d+,bt,t); /*初始化结果多项式*/ for ( i=0;iM+N-1;i+) ci=0; /*计算两个多项式的乘积*/ for (int m=0;mM;m+) for (int n=0;nN;n+) cm+n=am*bn+cm+n;printf(n得出的两个多项式的乘积为:n);printf(A(X)=A(X)*B(X)=n); /*打印出两个多项式的乘积*/ for ( int v=0;vM+N-1;v+) if(cv!=0) printf(%d*X%d+,cv,v); printf(n); 三、系统测试 （见附件） 4、 总结通过这次课程设计，我感觉到要真正做出一个程序并不很容易,但只要用心去做，总会有收获,特别是当我遇到问题,问老师，问同学，去百度，想尽办法去解决,最后终于找到方法时,心里的那份喜悦之情，成就之感真是难以形容.编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。 对于数据结构有了更深层次的理解,循环队列中对边界条件的处理,满足什么条件为队满,满足什么条件为队空。通过3周自己的学习和实践操作，解决实际问题，让我对数据结构有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法。以前我对数据结构（C语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这段时间的学习让我对数据结构（C语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在这次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用C语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。虽然我现在的水平还很差，但我还会继续努力的，在解决实际问题时如果遇到了难题，我们要学会去查找大量的有关这方面的资料，还要借助于网络不断扩大自己的知识面和阅读量。这样也可以锻炼我们的自主学习能力和解决问题的能力，学到了许多以前没学到的东西。在课程设计中的程序都比较复杂，所以需要我们要更加地细心，认真的完成每一步的操作，修改语法，按照老师的指导思想来完成。与此同时也让我们增加了对程序和算法进一步理解。总之，我学到了很多东西，很感谢学校给我们这样一次锻炼自我的机会，也很感谢老师的指导。5、 附件（系统测试的图表）项数为2且部分系数为0时的测试结果： 图2 运行结果图 1项