首页 > 代码库 > 一道 google曾出过的笔试题：编程实现对数学一元多项式的相加和相乘操作（1）
一道 google曾出过的笔试题：编程实现对数学一元多项式的相加和相乘操作（1）
数学中一元n次多项式可表示成如下的形式：
Pn(x)=p0+p1x+p2x^2+…+pnx^n (最多有 n+1 项，n +1 个系数唯一确定她)
(1)请设计一套接口用以表示和操作一元多项式
(2)根据上述设计实现一元n次多项式的加法运算
(3)根据上述设计实现一元n次多项式的乘法运算
分析：
题目大概意思：
数学里常见的一元 n 次表达式，设计出加减乘除的函数（方法），同时提供对外接口，把内部实现封装起来，而 n 的大小没有指定。
问题的本质：
就是一系列的单个未知数 x，指数和系数数字p（i）,0 =< i <= n组成的长串的表达式，然后把长长的表达式进行数学运算，假发和乘法，那么立马想到，这里需要线性表这个数据结构，符号多项式的表示和操作是线性表处理的典型用例。 且有变量 N，那么自然会联系到范围问题。
解决思路：
对问题进行进一步分解，常用的线性表，无非就是链表和顺序表，又分静态和动态内存分配的。数学的一元多项式，用一个线性表 P 来表示：P = ( p0, p1, p2, …, pn )
每一项，x的指数 隐含在其系数 p（i） 的下标i里。这样的话，只是存储系数就 ok了，未知数 x 的指数让系数下标标识。比较简单是用数组（静态顺序表存储），那么问题来了……
存储空间不够了怎么办?
显然，可以使用动态线性表，这样，伸缩自如！再也不担心不够存储了！继续分析，这样解决了空间大小的问题（有限范围内的内存），剩下的就是设计计算的算法，联想中学时代的算数，多项式并不是每一个项都必须写出来的，那么问题来了……
如果 p 里含有大量的0怎么办？
显然这样的存储结构也不太好，会大量浪费内存。比如 p=1 + 7x^12000，要用一个长度为 12001 的线性表来表示，表中仅有 两 个非零系数，会浪费大量存储空间。 不划算。需要改变策略，首先一个原则就是：系数=0不存储！那么自然是只存储非0系数，而指数就必须同时也要存储！否则无法标识指数。其实，日常生活里，也是这样的，一个数学或者物理化学的公式，表达式，系数为0的项，没人会把它写出来吧？！而且这样的多项式数序上叫稀疏多项式。
最终，确定使用链表来存储，因为，系数为0的项，经过计算，可能变为非0，相反非0的项经过计算，也可能变味0，必然要用到删除和插入算法，那么显然链表还是最佳的表示方法，效率比较高，不用大量移动元素，且可以动态增长。节省存储空间。
定义 ADT三要素：数据对象，数据关系，数据操作
PS:其实还是面向对象表达 ADT 比较好，当然 c 也完全 ok，个人 c++不是很融汇贯通，高级的语法和特性不敢乱用，免得班门弄斧，贻笑大方……不使用高级特性和复杂语法的话，cpp就索然无味，索性一直用 纯真的 c 来练习一些东西，因为这样更好的把重点放到算法和工程问题本身，而不是复杂庞大的 c++语言的枝端末节上，c++还是比 c 多了很多复杂繁琐的东西（这里又想到了一道奇葩的问题——如何用 c 实现面向对象？）
google 的这个问题充分暴露了本人c++功底不过关， c++求解实现的过程因为使用的是类模版，函数模版，继承，和输入输出等的运算符重载，导致程序代码较多，且出现了很多错误，考虑编码练习和算法设计，重点学习的是思想和方法，还是用c写，c++的巩固和加强完全可以放到其他闲散时间完成.
这个题的难点其实是最后一问！
因为既然是google的题，肯丢最后要考虑时间复杂度和优化问题。只有结果肯丢过不了关，这里先提供一个最直接的思路。也是比较费时间的。o（n*m）
//直接思考，多项式相乘，每一项一一顺次（考虑两个嵌套循环）的去做乘法，指数相加，系数相乘，保存到临时变量，又考虑到有多项，自然是数组保存了……
//这是正常的很直观的思路，可以依靠数组的下标去映射指数，把系数存到对应指数（下标）处，这里是累加的和。
然后再依靠一个循环，顺次去判断数组的内容，取出想要的系数和对应下标（就是指数），组成一个新项，那就ok了。
//最后的阶数必然是两式子最高阶之和，自然这个数组的长度=这个和+1
1 /************************************************************************/ 2 // 头文件Polynomial.h 3 // 定义链表结构 4 /************************************************************************/ 5 #ifndef POLYNOMIAL_H 6 #define POLYNOMIAL_H 7 #include <stdlib.h> 8 #include <stdio.h> 9 #include <float.h> 10 11 //链表结构 12 typedef struct Node{ 13 struct Node *next; 14 double coefficient; 15 int exponent; 16 } Node, *Polynomial; 17 18 //链表初始化 19 void initList(Polynomial *L) 20 { 21 //头结点 22 if (NULL == *L) 23 { 24 *L = (Polynomial)malloc(sizeof(Node)); 25 (*L)->coefficient = 0.0; 26 (*L)->exponent = -1; 27 (*L)->next = NULL; 28 } 29 else 30 { 31 puts("表已经存在！"); 32 } 33 } 34 35 //判断指数同否 36 int compareExponent(Polynomial nodeA, Polynomial nodeB) 37 { 38 int a = nodeA->exponent; 39 int b = nodeB->exponent; 40 41 if (a == b) 42 { 43 return 0; 44 } 45 else 46 { 47 return a > b ? 1 : -1; 48 } 49 } 50 51 //系数判断 52 bool isZeroByCoefficient(Polynomial node) 53 { 54 if (node->coefficient >= -LDBL_EPSILON && node->coefficient <= LDBL_EPSILON) 55 { 56 return true; 57 } 58 else 59 { 60 return false; 61 } 62 } 63 64 //判断2 65 //系数判断 66 bool isZeroByDouble(double a) 67 { 68 if (a >= -LDBL_EPSILON && a <= LDBL_EPSILON) 69 { 70 return true; 71 } 72 else 73 { 74 return false; 75 } 76 } 77 78 //尾插法建表 79 void creatListByTail(Polynomial *L, int n) 80 { 81 //头结点 82 if (NULL == *L) 83 { 84 *L = (Polynomial)malloc(sizeof(Node)); 85 (*L)->coefficient = 0.0; 86 (*L)->exponent = -1; 87 (*L)->next = NULL; 88 Polynomial tail = NULL; 89 Polynomial ptr = *L; 90 //初始化？ 91 if (NULL == (*L)->next) 92 { 93 puts("请按照指数升幂，连续的输入项的系数（double）和指数（int）：（中间空格隔开）"); 94 //循环建表 95 for (int i = 0; i < n; i++) 96 { 97 tail = (Polynomial)malloc(sizeof(Node)); 98 tail->next = NULL; 99 scanf("%lf %d", &tail->coefficient, &tail->exponent);100 101 while (getchar() != ‘\n‘)102 {103 continue;104 }105 //链接106 ptr->next = tail;107 //移动指针108 ptr = ptr->next;109 //尾结点110 }111 }112 else113 {114 puts("表已经建立！");115 }116 }117 else118 {119 puts("表头已经存在！");120 }121 }122 123 //遍历124 void traverseList(Polynomial L)125 {126 Polynomial ptr = L->next;127 int i = 1;128 129 while (ptr != NULL)130 {131 132 printf("一元多项式的第%d项：%g X ^ %d\n", i, ptr->coefficient, ptr->exponent);133 i++;134 ptr = ptr->next;135 }136 }137 138 //求最高阶数139 int getMaxExp(Polynomial L)140 {141 Polynomial ptr = L;142 143 while (ptr->next != NULL)144 {145 ptr = ptr->next;146 }147 148 return ptr->exponent;149 }150 151 //删除结点,删除L中ptr指向的结点152 void deleteNode(Polynomial L, Polynomial ptr)153 {154 Polynomial p = L;155 156 while (p->next != ptr)157 {158 p = p->next;159 }160 161 ptr = p->next;162 p->next->next = ptr->next;163 free(ptr);164 ptr = NULL;165 }166 167 //多项式相加，本质是链表的归并算法168 //可以另外开辟空间，也可以使用已存在的空间存储，这里使用后者的算法169 void addPolynomial(Polynomial LA, Polynomial LB)170 {171 //不再开辟内存172 Polynomial a = LA->next;173 Polynomial b = LB->next;174 Polynomial LC = LB;175 Polynomial tail = LC;176 177 while (a != NULL && b != NULL)178 {179 //判断指数的关系 a > b ? 1 : -1 else 0180 switch (compareExponent(a, b))181 {182 case 1:183 tail->next = b;184 tail = tail->next;185 b = b->next;186 break;187 188 case -1:189 tail->next = a;190 tail = tail->next;191 a = a->next;192 break;193 194 default:195 double temp = a->coefficient + b->coefficient;196 // 0？197 if (isZeroByDouble(temp))198 {199 a = a->next;200 b = b->next;201 //删除202 deleteNode(LC, tail->next);203 }204 else205 {206 tail->next = b;207 tail = tail->next;208 b->coefficient = temp;209 a = a->next;210 b = b->next;211 }// end of if212 }// end of switch213 }//end of while214 //一表比完215 if (NULL == a)216 {217 tail->next = b;218 }219 else220 {221 tail->next = a;222 }// end of if223 224 free(LA);225 LA = NULL;226 }227 228 //多项式相乘229 void mulPolynomial(Polynomial LA, Polynomial LB, Polynomial LC)230 {231 Polynomial a = LA->next;232 Polynomial b = LB->next;233 Polynomial c = LC;234 Polynomial ptr = NULL;235 //两多项式的阶数236 int numA = getMaxExp(LA);237 int numB = getMaxExp(LB);238 //结果多项式的阶数239 int maxNum = numA + numB;240 //动态开辟数组空间241 double *receive = (double *)malloc((maxNum + 1) * sizeof(double));242 //为数组赋值243 for (int i = 0; i < maxNum + 1; i++)244 {245 //i相当于指数，数组值就是相应指数的系数246 receive[i] = 0.0;247 }248 //指数及数组下标249 int expByIndex = 0;250 //顺次扫描A251 while (a != NULL)252 {253 //A不空，顺次扫描B254 while (b != NULL)255 {256 //两项做乘法之后的指数和257 expByIndex = a->exponent + b->exponent;258 //系数之间做乘，结果保存到对应的指数下（下标），259 receive[expByIndex] += (a->coefficient) * (b->coefficient);260 b = b->next;261 }262 263 b = LB->next;264 a = a->next;265 }// end of while266 //数组保存的是全部项，两两分别乘法之后的结果，保存在对应的下标（数组位置）267 for (int i = 0; i < maxNum + 1; i++)268 {269 // 0？270 if (isZeroByDouble(receive[i]))271 {272 //not do sth273 }274 else275 {276 //生成结点277 ptr = (Polynomial)malloc(sizeof(Node));278 //接到 LC 表279 c->next = ptr;280 c = c->next;281 //赋值282 c->coefficient =receive[i];283 c->exponent = i;284 }// end of if285 }// end of for286 287 c->next = NULL;288 }289 290 //链表销毁291 void destroyList(Polynomial *L)292 {293 Polynomial ptr = NULL;294 295 while (*L != NULL)296 {297 ptr = (*L)->next;298 free(*L);299 *L = ptr;300 }301 //302 *L = NULL;303 puts("销毁完毕");304 }305 #endif
注意：
1、
//数组维数在c99之前必须是常量，c99之后可以是变长数组，但是很多编译器还不支持。
//double receive[maxNum + 1] = {0};目前来说error!
2、
最后销毁的时候销毁B就行了，因为把A插到B，B就是C，C就是B，A只剩下头结点，在相加函数里，早已经被删除！如果还销毁B，铁定报错！重复析构。
3、
多项式相乘（其实就是两个链表的合并问题），这里有两个方法比较常见:
最简单也是最费时间（时间复杂度 o（n*m）最高的实现方法）的直接相乘法:
其实很简单，把表 A 的每一项系数分别和表 B 的每一项系数做乘法，同时，把他们的指数相加，存储到临时数组里，这样得到 N（A）x N（B）个新的项，按照指数相同的，把他们的系数相加组合为一新的项，附带这个指数，输出，得结果。
比较经典的是分治法。
1 #include "Polynomial.h" 2 3 int main(void) 4 { 5 puts("第一波计算加法：初始化表A,B"); 6 Polynomial LA = NULL; 7 Polynomial LB = NULL; 8 9 puts("建表A");10 creatListByTail(&LA, 4);11 puts("打印A");12 traverseList(LA);13 puts("建立表B");14 creatListByTail(&LB, 3);15 puts("打印表B");16 traverseList(LB);17 //相加18 puts("表A,B相加");19 addPolynomial(LA, LB);20 puts("打印和");21 traverseList(LB);22 //销毁B即可23 puts("销毁表A,B");24 destroyList(&LB);
1 puts("第二波计算乘法：初始化表A，B，C"); 2 Polynomial LAX = NULL; 3 Polynomial LBX = NULL; 4 Polynomial LCX = NULL; 5 initList(&LCX); 6 7 puts("建表A,B"); 8 creatListByTail(&LAX, 4); 9 puts("打印表A");10 traverseList(LAX);11 puts("建立表B");12 creatListByTail(&LBX, 3);13 puts("打印表B");14 traverseList(LBX);15 //相乘16 puts("表A,B做乘法");17 mulPolynomial(LAX, LBX, LCX);18 puts("打印结果");19 traverseList(LCX);20 //销毁21 puts("销毁表ABC");22 destroyList(&LAX);23 destroyList(&LBX);24 destroyList(&LCX);25 26 system("pause");27 return 0;28 }
还有一种改进的快速的傅里叶变换算法实现（未完待续）
一道 google曾出过的笔试题：编程实现对数学一元多项式的相加和相乘操作（1）