【摘要】这套权限管理是配合Zend Framework设计的，用在其他地方的时候可以做些修改。一、表构成 1.总共有七张表组成 2.管理员信息表(sys_user)、系统模块信息表(sys_module)与用户分组信息表(sys_group)这三张是独立的表，没有与其他表发生关系。 3.用户分组信息表... 阅读全文
数学中一元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
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
没有评论:
发表评论