- 数据结构编程实验（第3版）
- 吴永辉 王建德编著
- 1444字
- 2021-08-13 17:24:04
4.1.3 多项式的表示与处理
多项式的表示与处理也是直接存取类线性表的一个重要应用。通常，一元n次多项式可表示成如下形式：
一元n次多项式的存储有两种方法：
1）用数值数组a来存储，各个项的系数按照指数递增的次序存储在a[0..n]中（n为最高阶数），a的下标表示当前项的指数值。若第i项在多项式中为空项，即多项式中的系数ai=0，则对应的数组元素a[i]=0。显然，数组a的长度取决于多项式中的最高次幂。
2）用结构数组a来存储，数组a的下标为项序号而非指数值，数组元素为包含当前项系数a[i].coef和指数a[i].exp的结构体。显然，数组a的长度为多项式的实际长度。
在上述数据结构的基础上，便可以展开多项式的运算，例如：
类似地，可以做两个多项式的减法和除法运算，以及其他运算。一般来讲，采用数值数组的存储方式，虽然内存用量较大，但算法简单；采用结构数组的存储方式，虽然内存用量减少，但算法的复杂度增加。
【4.1.3.1 Polynomial Showdown】
给出一个次数从8到0的多项式的系数，请以可读的形式将该多项式规范地输出，没有必要的字符就不用输出。例如，给出系数0、0、0、1、22、-333、0、1和-1，输出x^5+22x^4-333x^3+x-1。
规范规则如下：
·多项式的各项按照指数的递减顺序输出；
·次数出现在“^”之后；
·常数项仅输出常数；
·如果所有的项都以0作为系数，则仅输出常数0；否则仅输出非零系数的项；
·在二元操作符“+”和“-”的两边要有一个空格；
·如果第一个项的系数是正数，在该项前没有符号；如果第一个项的系数是负数，在该项前是减号，例如，-7x^2+30x+66。
·负系数项以被减的非负项的形式出现，（如上所述，第一个项是负系数项时是例外）。例如，不能输出x^2+-3x，应该输出x^2-3x。
·常量1和-1仅在常数项出现。例如，不能输出-1x^3+1x^2+3x^1–1，应该输出-x^3+x^2+3x–1。
输入
输入包含一行或多行的系数，系数间由一个或多个空格分隔开。每行有9个系数，每个系数是绝对值小于1000的整数。
输出
输出给出格式化的多项式，每个多项式一行。
试题来源：ACM Mid-Central USA 1996
在线测试：POJ 1555，ZOJ 1720，UVA 392
试题解析
将指数为n-i-1的系数an-i-1存储在数组元素a[i]中，a[n-1]为常数项。初始时，按照指数由高到低的顺序读入a[0..n-1]。
按照指数由高到低的顺序处理非零项a[i]（a[i]≠0，i=0…n-1）。可分首项还是非首项两种情况处理。
1）a[i]是多项式首项。
·处理系数：若a[i]==-1且非常数项（i<n-1），则直接输出'-'；否则，若a[i]≠1或者为常数项（i==n-1），则输出系数a[i]。
·处理次幂：若指数为1（i==n-2），则直接输出'x'；否则在非常数项（i<n-1）的情况下，输出'x^'(n-i-1)。
首项标志取反。
2）a[i]不是多项式首项。
·处理正负号：输出(a[i]<0?'-':'+')。
·处理系数：在a[i]≠1或-1或者为常数项的情况下，输出a[i]的绝对值。
·处理次幂：若指数为1时（i==n-2），则直接输出'x'；否则在非常数项（i<n-1）的情况下，输出'x^'(n-i-1)。
若处理完多项式后，多项式的首项标志无变化，则说明所有系数都为0，应输出0。
参考程序
#include <iostream> //预编译命令
using namespace std; //使用C++标准程序库中的所有标识符
const int n = 9; //定义多项式的项数
inline int fabs(int k) // 返回k的绝对值
{
return k < 0 ? -k : k;
}
int main(void) //主函数
{ //主函数开始
int a[n];
while (cin >> a[0]) { //按照指数由高到低的顺序输入各项的系数
for (int i = 1; i < n; i++)
cin >> a[i];
bool first = true; //设首项标志
for (int i = 0; i < n; i++)
if (a[i]) { //按照指数由高到低的顺序输出非零项
if (first) { // 处理首项
if (a[i] == -1 && i < n - 1) //处理当前项为-1的情况
cout << '-';
else if (a[i] != 1 || i == n - 1) //处理当前项非1的情况
cout << a[i];
if (i==n - 2) //若指数为1时，不输出指数；指数
//大于1时，输出指数
cout << 'x';
else if (i < n - 1)
cout << "x^" << n - i - 1;
first = false; //首项标志取反
} else { //如果是第一个非零系数之后的非
//零系数，先输出运算符号，接着
//输出系数的绝对值
cout <<' '<<(a[i]< 0 ? '-' : '+') << ' '; //输出正负号
if (fabs(a[i]) != 1 || i == n - 1)//不输出系数为1时的系数
cout << fabs(a[i]);
if (i == n - 2) //指数为1时，不输出指数；指数
//大于1时，输出指数
cout << 'x';
else if (i < n - 1)
cout << "x^" << n - i - 1;
}
}
if (first) //若所有系数都为0，则输出0
cout << 0;
cout << endl; //输出空行
}
return 0;
}
采用数组存储方式，不仅可以方便地规范多项式的输出，还可以方便地进行多项式的运算。
【4.1.3.2 Modular multiplication of polynomials】
本题考虑系数为0或1的多项式。两个多项式相加是通过对多项式中相应幂次项的系数进行相加来实现的。系数相加是加法操作后再除以2取余，即(0+0)mod 2=0、(0+1)
mod 2=1、(1+0)mod 2=1且(1+1)mod 2=0。所以，这也和或操作相似。
(x^6+x^4+x^2+x+1)+(x^7+x+1)=x^7+x^6+x^4+x^2
两个多项式相减是相似的。系数相减是减法操作后再除以2取余，也是一个或操作，所以两个多项式相减和两个多项式相加是相同的。
(x^6+x^4+x^2+x+1)-(x^7+x+1)=x^7+x^6+x^4+x^2
两个多项式相乘用通常的方法实现（当然，系数相加还是加法操作后再除以2取余）。
(x^6+x^4+x^2+x+1)(x^7+x+1)=x^13+x^11+x^9+x^8+x^6+x^5+x^4+x^3+1
多项式f(x)和g(x)相乘，并除以h(x)取模是f(x)g(x)除以h(x)的余数。
(x^6+x^4+x^2+x+1)(x^7+x+1)modulo(x^8+x^4+x^3+x+1)=x^7+x^6+1
多项式最高的次数称为它的度。例如，x^7+x^6+1的度是7。
给出3个多项式f(x)、g(x)和h(x)，请编写一个程序计算f(x)g(x)modulo h(x)。
本题设定f(x)和g(x)的度小于h(x)的度，多项式的度小于1000。
因为多项式系数是0或1，一个多项式可以用d+1个01字符来表示，01字符串长度为d+1，其中d是多项式的度，01字符串表示多项式的系数。例如，多项式x^7+x^6+1可以表示为8 1 1 0 0 0 0 0 1。
输入
输入由T个测试用例组成。在输入的第一行给出测试用例数（T）。每个测试用例由三行组成，分别表示多项式f(x)、g(x)和h(x)，多项式的表示如上所述。
输出
输出多项式f(x)g(x)modulo h(x)，每个多项式一行。
试题来源：ACM Taejon 2001
在线测试：POJ 1060，ZOJ 1026，UVA 2323
试题解析
设多项式f(x)的字符串长度为lf，各项的系数存储在f[lf-1..0]中；多项式g(x)的字符串长度为lg，各项的系数存储在g[lg-1..0]中；多项式h(x)的字符串长度为lh，各项的系数存储在h[lh-1..0]中；数组sum用于存储f(x)*g(x)的乘积和(f(x)*g(x))modulo h(x)的结果，字符串长度为ls，各项的系数存储在sum[ls-1..0]中。
1）计算sum(x)=f(x)*g(x)。
由于f(x)和g(x)的系数为0或1，因此f(x)*g(x)的字符串长度为ls=lf+lg-1。f中xi的系数f[i]与g中xj的系数g[j]相乘，相当于位的与运算f[i] & g[j]，结果加到乘积多项式的xi+j的系数上去，相当于异或运算sum[i+j]=sum[i+j]^(f[i] & g[j])（0≤i≤lf-1，0≤j≤lg-1）。
2）计算sum(x)=sum(x)modulo h(x)。
sum(x)对h(x)取模，相当于sum(x)除h(x)，直至余数小于h(x)为止，这个余数即取模的结果。问题是怎样判别当前余数sum(x)与h(x)的大小。
若ls>lh，则sum(x)大；若ls<lh，则h(x)大；若ls==lh，则从最高次幂ls-1开始由高到低逐项比较系数：若sum[i]==1，h[i]==0，则sum(x)大；若sum[i]==0，h[i]==1，则h(x)大。
显然，若当前sum(x)大于h(x)，则让sum(x)除一次h(x)：从h的最低位开始，按照次幂由低至高的顺序进行相除运算，将h[i]异或到sum[i+ls-lh]上去，即sum[i+d]=sum[i+d]^h[i]，i=0…ls-1。然后重新调整sum的最高次幂（while(ls & & !sum[ls-1])--ls；）。
这个过程一直进行到sum(x)小于h(x)为止。此时得出的ls即余数多项式的项数，各项的系数为sum[ls-1..0]。
参考程序
#include <iostream> //预编译命令
using namespace std; //使用C++标准程序库中的所有标识符
const int maxl = 1000 + 5; //乘积数组sum的容量
int compare(int a[], int la, int b[], int lb) //比较多项式a和b的大小
{
if (la > lb) //比较a和b的最高次幂
return 1;
if (la < lb)
return -1;
for (int i = la - 1; i >= 0; i--) //在a和b的最高次幂相同的情况下，按照
//次幂由高到低的顺序逐项比较
if (a[i] && !b[i])
return 1;
else if (!a[i] && b[i])
return -1;
return 0;
}
int main(void) //主函数
{ //主函数开始
int loop;
cin >> loop; //读测试组数
while (loop--) {
int f[maxl], g[maxl], h[maxl];
int lf, lg, lh;
cin >> lf; //读多项式f的最高次幂
for (int i = lf - 1; i >= 0; i--) //依次读f中每一项的系数
cin >> f[i];
cin >> lg; //读多项式g的最高次幂
for (int i = lg - 1; i >= 0; i--) // 依次读g中每一项的系数
cin >> g[i];
cin >> lh; //读多项式h的最高次幂
for (int i = lh - 1; i >= 0; i--) //依次读h中每一项的系数
cin >> h[i];
int sum[maxl+maxl], ls=lf+lg-1; //乘积数组sum及其长度初始化
for (int i = 0; i < ls; i++)
sum[i] = 0;
for (int i = 0; i < lf; i++) //计算乘积数组sum
for (int j = 0; j < lg; j++)
sum[i + j] ^= (f[i] & g[j]);
// 计算乘积对h[]的取模
while (compare(sum, ls, h, lh)>=0) { //若当前余数sum不小于h，则继续除以h
int d = ls - lh; //计算sum除以h的余数
for (int i = 0; i < lh; i++)
sum[i + d] ^= h[i];
while (ls && !sum[ls - 1]) //确定sum的最高次幂
--ls;
}
if (ls == 0) //计算和输出余数数组sum的长度
ls = 1;
cout << ls << ' ';
for (int i = ls - 1; i > 0; i--) //输出sum中每一项的系数
cout << sum[i] << ' ';
cout << sum[0] << endl;
}
return 0;
}