目录

一、题意理解 二、解题思路 三、多项式加法 四、多项式乘法 五、完整代码

更新、更全的《数据结构与算法》的更新网站，更有python、go、人工智能教学等着你：https://HdhCmsTestcnblogs测试数据/nickchen121/p/11407287.html

一、题意理解

题目： 设计函数分别求两个一元多项式的乘积与和。

输入格式： 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式： 输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

例子：

\[\text{已知两个多项式：} \\begin{align} & 3x^4-5x^2+6x-2 \& 5x^{20}-7x^4+3x \end{align} \]

#?python语言实现

#?输入样例：
4?3?4?-5?2??6?1??-2?0
3?5?20??-7?4??3?1

#?输出样例：
15?24?-25?22?30?21?-10?20?-21?8?35?6?-33?5?14?4?-15?3?18?2?-6?1
5?20?-4?4?-5?2?9?1?-2?0

二、解题思路

存储方式可以采用链表存储和数组存储，为了熟悉链式操作，所以采用链表存储。其中指针定义的格式如下所示

三、多项式加法

#?python语言实现

def?adds(l1,?l2):??#?l1,l2为链表,且不为空
????p1?=?l1.head
????p2?=?l2.head
????addRes?=?[]
????while?(p1?is?not?None)?and?(p2?is?not?None):??#?当p1和p2都部位空时，进行运算
????????tmp1_exp?=?p1.get_data()[1]??#?获取p1指针处节点的指数
????????tmp2_exp?=?p2.get_data()[1]??#?获取p2指针处节点的指数

????????#?当指数相同时，系数相加，指数不变
????????if?tmp1_exp?==?tmp2_exp:
????????????addRes.append([p1.get_data()[0]?+?p2.get_data()[0],?p1.get_data()[1]])
????????????p1?=?p1.next??#?指针指向下一个节点
????????????p2?=?p2.next

????????#?当指数不相同时，选择较大的指数项存到结果中
????????if?tmp1_exp?>?tmp2_exp:
????????????addRes.append([p1.get_data()[0],?p1.get_data()[1]])
????????????p1?=?p1.next
????????if?tmp1_exp?<?tmp2_exp:
????????????addRes.append([p2.get_data()[0],?p2.get_data()[1]])
????????????p2?=?p2.next

????#?对于链表中剩余的节点添加到结果中
????while?p1?is?not?None:
????????addRes.append([p1.get_data()[0],?p1.get_data()[1]])
????????p1?=?p1.next
????while?p2?is?not?None:
????????addRes.append([p2.get_data()[0],?p2.get_data()[1]])
????????p2?=?p2.next

????#?此时的addRes结果
????#?addRes?[[5,?20],?[-4,?4],?[-5,?2],?[9,?1],?[-2,?0]]
????#?列表中每一项代表一各指数项，其中第一个元素代表系数，第二个元素代表指数。如[5，20]：5x^20

????#?以下是对addRes进行变形处理
????res1?=?[]
????for?item?in?addRes:
????????if?item[0]?!=?0:??#?如果指数为0，即存在抵消情况，此时不应该输出
????????????res1.append(item[0])
????????????res1.append(item[1])
????if?len(res1)?==?0:??#?如果结果为0,需要输出：0??0
????????return?[0,?0]

????#?此时的输出结果变为
????#?[5,20,-4,4,-5,2,9,1,-2,0]
????return?res1

四、多项式乘法

#?python语言实现

def?muls(l1,?l2):
????p1?=?l1.head
????p2?=?l2.head
????mulRes?=?[]
????while?p1?is?not?None:??#?将第一项的每一项乘以第二项的每一项
????????tmp1?=?p1.get_data()
????????while?p2?is?not?None:
????????????tmp2?=?p2.get_data()
????????????#?将系数相乘和指数相加放入结果中
????????????mulRes.append([tmp1[0]?*?tmp2[0],?tmp1[1]?+?tmp2[1]])
????????????p2?=?p2.next
????????p2?=?l2.head??#?每次遍历完l2，都需要回到头指针，进行下一次遍历
????????p1?=?p1.next
????#?上述运算后，需要合并同类项。定义一个字典，key=指数，values=系数
????d?=?{}
????for?item?in?mulRes:
????????if?item[1]?not?in?d.keys():
????????????d[item[1]]?=?0
????????d[item[1]]?+=?item[0]
????#?字典按照key的大小排序
????d?=?sorted(d.items(),?key=lambda?x:?x[0],?reverse=True)
????#?结果变形输出
????res2?=?[]
????for?item?in?d:
????????if?item[1]?!=?0:
????????????res2.append(item[1])
????????????res2.append(item[0])
????if?len(res2)?==?0:
????????return?[0,?0]
????return?res2

五、完整代码

#?python语言实现

class?Node:
????def?__init__(self,?coef,?exp):
????????self.coef?=?coef
????????self.exp?=?exp
????????self.next?=?None

????def?get_data(self):
????????return?[self.coef,?self.exp]


class?List:
????def?__init__(self,?head):
????????self.head?=?head

????#?添加节点
????def?addNode(self,?node):
????????temp?=?self.head
????????while?temp.next?is?not?None:
????????????temp?=?temp.next
????????temp.next?=?node

????????#?打印

????def?printLink(self,?head):
????????res?=?[]
????????while?head?is?not?None:
????????????res.append(head.get_data())
????????????head?=?head.next
????????return?res


def?adds(l1,?l2):??#?l1,l2为链表,且不为空
????p1?=?l1.head
????p2?=?l2.head
????addRes?=?[]
????while?(p1?is?not?None)?and?(p2?is?not?None):
????????tmp1_exp?=?p1.get_data()[1]
????????tmp2_exp?=?p2.get_data()[1]
????????#?当指数相同时，系数相加
????????if?tmp1_exp?==?tmp2_exp:
????????????addRes.append([p1.get_data()[0]?+?p2.get_data()[0],?p1.get_data()[1]])
????????????p1?=?p1.next
????????????p2?=?p2.next
????????if?tmp1_exp?>?tmp2_exp:
????????????addRes.append([p1.get_data()[0],?p1.get_data()[1]])
????????????p1?=?p1.next
????????if?tmp1_exp?<?tmp2_exp:
????????????addRes.append([p2.get_data()[0],?p2.get_data()[1]])
????????????p2?=?p2.next
????while?p1?is?not?None:
????????addRes.append([p1.get_data()[0],?p1.get_data()[1]])
????????p1?=?p1.next
????while?p2?is?not?None:
????????addRes.append([p2.get_data()[0],?p2.get_data()[1]])
????????p2?=?p2.next

????res1?=?[]
????for?item?in?addRes:
????????if?item[0]?!=?0:
????????????res1.append(item[0])
????????????res1.append(item[1])
????if?len(res1)?==?0:
????????return?[0,?0]
????return?res1


def?muls(l1,?l2):
????p1?=?l1.head
????p2?=?l2.head
????mulRes?=?[]
????while?p1?is?not?None:
????????tmp1?=?p1.get_data()
????????while?p2?is?not?None:
????????????tmp2?=?p2.get_data()
????????????mulRes.append([tmp1[0]?*?tmp2[0],?tmp1[1]?+?tmp2[1]])
????????????p2?=?p2.next
????????p2?=?l2.head
????????p1?=?p1.next

????exps?=?[]
????for?item?in?mulRes:
????????if?item[1]?not?in?exps:
????????????exps.append(item[1])

????d?=?{}
????for?item?in?mulRes:
????????if?item[1]?not?in?d.keys():
????????????d[item[1]]?=?0
????????d[item[1]]?+=?item[0]

????d?=?sorted(d.items(),?key=lambda?x:?x[0],?reverse=True)

????res2?=?[]
????for?item?in?d:
????????#?如果多项式中出现抵消，即系数为0需要删除
????????if?item[1]?!=?0:
????????????res2.append(item[1])
????????????res2.append(item[0])
????#?如果最后出现空数组需要输出0?0
????if?len(res2)?==?0:
????????return?[0,?0]
????return?res2


def?print_list(x):
????for?i?in?x[:-1]:
????????print(i,?end='?')
????print(x[-1],?end='')


#?输入
a1?=?list(map(int,?input().split()))
a2?=?list(map(int,?input().split()))

#?变为链表
if?a1[0]?!=?0:
????head1?=?Node(a1[1],?a1[2])
????l1?=?List(head1)
????if?a1[0]?>?1:
????????for?i?in?range(a1[0]?-?1):
????????????node?=?Node(a1[i?*?2?+?3],?a1[i?*?2?+?4])
????????????l1.addNode(node)

if?a2[0]?!=?0:
????head2?=?Node(a2[1],?a2[2])
????l2?=?List(head2)
????if?a2[0]?>?1:
????????for?i?in?range(a2[0]?-?1):
????????????node?=?Node(a2[i?*?2?+?3],?a2[i?*?2?+?4])
????????????l2.addNode(node)
#?考虑链表长度进行运算
if?len(a1)?==?1?and?len(a2)?==?1:??#?都为0，则输出都为0
????print_list([0,?0])
????print()
????print_list([0,?0])
elif?len(a1)?==?1?and?len(a2)?>?1:??#?一个为0，另一个为多项式
????print_list([0,?0])
????print()
????print_list(a2[1:])
elif?len(a2)?==?1?and?len(a1)?>?1:
????print_list([0,?0])
????print()
????print_list(a1[1:])
else:??#?都为多项式
????print_list(muls(l1,?l2))
????print()
????print_list(adds(l1,?l2))

查看更多关于小白专场-多项式乘法与加法运算-python语言实现的详细内容...