Question

两个一元多项式相乘的算法

不是程序，就是用基本操作组合起来的那种，要用链表储存的

Answer 1

把一个多项式的系数存在数组a里.a[i]表示x^i的系数

把另一个多项式的系数存在数组b里.b[i]表示x^i的系数
那么 for i = 1 to n for j = 1 to m c[i+j] += a[i] * b[j] //代表ax^i * bx^j = ab * x^(i+j)
c数组就存储了答案多项式的系数。

追问

要用链表，而且乘完以后还要排序，帮我写一下具体算法嘛，大神

追答

您用链表是神马心态……如果单纯是练习链表的话还是写最经典的约瑟夫问题吧。

这题用链表好像挺麻烦。其实数组就是存储地址相邻的链表.

如果要考察对地址的理解，那还是写成这样吧……

简化了读入,您可以把您的需求说的具体点

#include <cstdio>
#include <cstdlib>
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int a[1000];
    int b[1000];
    for (int i = n; i >= 0; --i) scanf("%d", a+i);
    for (int i = m; i >= 0; --i) scanf("%d", b+i);
    int c[2000];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            *(c+i+j) += *(a+i) * *(b+j);
    for (int i = n+m; i > 0; --i) 
        if (*(c+i))
           if (*(c+i) == 1)
              printf("x^%d + ", i);
           else
              printf("%dx^%d + ", *(c+i), i);
    printf("%d\n", *c);
    
    system("pause");
    return 0;
}

追问

只写算法，数据结构的算法，不用写程序，一元多项式的加法算法看懂了，乘法写不来

追答

设(3x^2 + 2x + 1) * (4x^2 +3 x + 1)
那么a数组 a[0] = 1, a[1] = 2, a[3] = 3
    b数组b[0] = 1, b[1] = 3, b[3] = 4
那么我们模拟手工乘法
首先拿第一个式子的1和第二个式子的1, 3x, 4x^2分别乘
      首先1*1 = 1, x的指数是0，那么c[0] = c[0] + 1 表示加了1个x^0
      1*3x = 3x, x的指数是1, 那么c[1] = c[1] + 3 表示加了3个x^1
      1*4x^2 = 4^2, x的指数是2, 那么c[2] = c[2] + 4 表示加了4个x^2
再拿第一个式子的2x和第二个式子的1, 3x, 4x^2分别乘……
……
结合着程序就能看懂了

追问

void MultiplyPolyn(polynomial &Pa,polynomial &Pb)

pa=pa*pb,直接把值相乘所得值给pa了，乘完之后还要对所得的m*n个多项式排序，太难了

追答

polynomial应该是自己写的一个类吧。

思路还是和上面一样的，就是多项式封装起来。

至于排序，用sort, 自己写一个比较函数, 不知道您是要按什么排?

这些可能对您有帮助 

http://zhidao.baidu.com/question/40060541.html

http://read.pudn.com/downloads8/sourcecode/others/22599/Polynomial/Polynamial.cpp__.htm

这个代码是工程型的了，他用了链表。

Answer 2

直接计算两个一元多项式相乘的系数需要O(n2)的运算量。本文介绍了一种超快的算法——用快速傅立叶变换实现两个一元多项式相乘的快速算法。该算法是通过快速傅立叶变换、快速傅立叶变换逆变换以及卷积来实现的,其运算量为O(nlog2n)。

追问

算法呢