【Weiss】【第03章】练习3.7：有序多项式相乘

【练习3.7】

编写一个函数将两个多项式相乘，用一个链表实现。你必须保证输出的多项式按幂次排列，并且任意幂次最多只有一项。

a.给出以O(M²N²)时间求解该问题的算法。

b.写一个以O(M²N)时间执行乘法的程序，其中M≤N。

c.写一个以O(MNlog(MN))时间执行乘法的程序。

d.上面哪个时间界最好？

Answer：

【a】.将两链表元素两两相乘并列出，从第一项开始，依次与其后的所有项比较，如相等则合并。

合并完成后，每次找出幂次最小的项，插入链表。（最原始的方法）

【b】.M≤1时，方法易知。

M≥2时，每次将长度为M的链表的一项，与另一链表的所有项相乘，每次一组N个有序的多项式元素。

对于每两组上式的N个多项式元素，基本按练习3.5有序链表求并的算法（除幂次相同需将系数相加）操作。

求并算法时间复杂度O(M+N)，故该算法复杂度为

(乘法时间）O(MN)+（求并时间）O（(N+N)+(2N+N)+(3N+N)+……+(MN+N))=O（M²N）

【详情见代码】

【c】.同a先将两链表元素两两相乘并列出，对MN项元素进行O(NlogN)的排序

排序完成后，遍历代码，合并同幂次项，最后全部插入链表。时间复杂度为：

（乘法时间）O(MN)+（排序时间）O(MNlogMN)+（合并同类项时间）O(MN)=O(MNlogMN)

【详见代码】

代码部分，首先是测试代码，b和c的测试代码写在一起了

 #include <iostream>

 #include "linklist.h"

 using linklist::List;

 using namespace std;

 int main(void)

 {

     //测试多项式加法

     List<Poly> a;

     a.additem(Poly(, ));

     a.additem(Poly(, ));

     a.additem(Poly(, ));

     a.additem(Poly(, ));

     a.additem(Poly(, ));

     cout << "  ( " << flush;

     a.traverse();

     cout << ")  +\n" << flush;

     List<Poly> b;

     b.additem(Poly(, ));

     b.additem(Poly(, ));

     b.additem(Poly(, ));

     b.additem(Poly(, ));

     b.additem(Poly(, ));

     cout << "  ( " << flush;

     b.traverse();

     cout << ") =\n" << flush;

     List<Poly> answer = linklist::polymulti_seq(a, b);

     List<Poly> another = linklist::polymulti_sort(a, b);

     cout << "\n  ( " << flush;

     answer.traverse();

     cout << ") \n" << flush;

     cout << "\n  ( " << flush;

     another.traverse();

     cout << ") \n" << flush;

     system("pause");

 }

实现部分，首先需在poly.h中重载多项式元素的乘法运算符

 //练习3.7新增，多项式元素乘法*

 Poly operator*(const Poly& poly1, const Poly& poly2)

 {

     Poly answer;

     answer.coefficient = poly1.coefficient*poly2.coefficient;

     answer.exponent = poly1.exponent + poly2.exponent;

     return answer;

 }

然后是小题b代码，包括习题3.5求并成员函数的模板特例化的辅助函数及主相乘算法

 //练习3.7b新增，将3.5求并的成员函数特例化

 template <> void List<Poly>::join(List<Poly> inorder)

 {

     Node<Poly>* curr = front;

     Node<Poly>* prev = nullptr;

     Node<Poly>* curr2 = inorder.front;

     while (curr != nullptr && curr2 != nullptr)

     {

         if (curr->data < curr2->data)

         {

             prev = curr;

             curr = curr->next;

         }

         else if (curr2->data < curr->data)

         {

             additem(curr2->data, prev);

             if (prev == nullptr)

                 prev = front;

             else

                 prev = prev->next;

             curr2 = curr2->next;

         }

         else

         {

             //对比3.5唯一增加语句

             //当两元素幂次相等时，原链表与新链表的多项式系数相加并将指针后移

             curr->data = curr->data + curr2->data;

             prev = curr;

             curr = curr->next;

             curr2 = curr2->next;

         }

     }

     while (curr2 != nullptr)

     {

         additem(curr2->data, prev);

         if (prev == nullptr)

             prev = front;

         else

             prev = prev->next;

         curr2 = curr2->next;

     }

 }

 //练习3.7b新增，以O(M²N）时间执行多项式乘法

 List<Poly> polymulti_seq(const List<Poly> &inorder_a, const List<Poly> &inorder_b)

 {

     //保证首链表长度较小

     if (inorder_a.size() > inorder_b.size())

         return polymulti_seq(inorder_b, inorder_a);

     else

     {

         List<Poly> answer;

         for (Node<Poly>* iter_a = inorder_a.begin(); iter_a != nullptr; iter_a = iter_a->next)

         {

             //用较短链表中每一个元素乘较长链表，得到临时链表

             {

                 List<Poly> temp;

                 for (Node<Poly>* iter_b = inorder_b.begin(); iter_b != nullptr; iter_b = iter_b->next)

                     temp.additem(iter_a->data * iter_b->data);

                 answer.join(temp);

             }

         }

         return answer;

     }

 }

然后为c小题算法，调用了标准库中的快排，需要#include<algorithm>

 //练习3.7c新增，以O（MNlogMN）时间执行多项式乘法

 List<Poly> polymulti_sort(const List<Poly> &inorder_a, const List<Poly> &inorder_b)

 {

     unsigned maxsize = inorder_a.size() * inorder_b.size();

     //申请M*N大小的数组

     Poly* temp_array = new Poly[maxsize];

     unsigned int index = ;

     //依次对链表每两个节点元素相乘并放在数组中

     for (Node<Poly>* iter_a = inorder_a.begin(); iter_a != nullptr; iter_a = iter_a->next)

         for (Node<Poly>* iter_b = inorder_b.begin(); iter_b != nullptr; iter_b = iter_b->next)

             temp_array[index++] = iter_a->data*iter_b->data;

     //对数组进行升序快排

     sort(&temp_array[], &temp_array[--index]);

     List<Poly> answer;

     //单次遍历数组，合并同类项

     for (index = ; index < maxsize; ++index)

     {

         if (temp_array[index] == temp_array[index - ])

             temp_array[index] = temp_array[index - ] + temp_array[index];

         else

             answer.additem(temp_array[index - ]);

     }

     answer.additem(temp_array[index - ]);

     delete[] temp_array;

     return answer;

 }

巴特西

【Weiss】【第03章】练习3.7：有序多项式相乘

最新文章

热门文章