小白专场-多项式乘法与加法运算-python语言实现

概述目录一、题意理解二、解题思路三、多项式加法四、多项式乘法五、完整代码更新、更全的《数据结构与算法》的更新网站，更有python、go、人工智能教学等着你：https://www.cnblogs.comickchen121/p/11407287.html一、题意理解题目：设计函数分别求两个一元多项式的乘积与和。输入格式：输

目录

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

更新、更全的《数据结构与算法》的更新网站，更有python、go、人工智能教学等着你：https://www.cnblogs.com/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 03 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 15 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 resdef 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 res1def 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 res2def 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语言实现全部内容，希望文章能够帮你解决小白专场-多项式乘法与加法运算-python语言实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。