多项式

多项式是数学中相当重要的表达方式，如果使用计算机来处理多项式的各种相关运算，通常可以使用列表、链表和字典等数据结构来存储多项式。

假如一个多项式 $P(x)=a_{n}X^{n}+a_{n-1}X^{n-1}+...+a_{1}X+a_{0}$ ，P(x)就为一个n次多项式。

使用列表存储多项式

使用一个二维列表来存储多项式。二维列表中的每个元素均为一个列表，存储多项式中某一项的指数和系数。例如多项式 $p=2X^{5}+3X^{4}+5X^{2}+4X+1$ 可以用二维列表表示为：

[[5, 2], [4, 3], [2, 5], [1, 4], [0, 1]]

使用字典存储多项式

字典也可以存储一个多项式。字典中以多项式指数为key，指数对应的系数和为value。例如多项式 $p=2X^{5}+3X^{4}+5X^{2}+4X+1$ 可以用字典存储为：

{5: 2, 4: 3, 2: 5, 1: 4, 0: 1}

使用链表存储多项式

链表也可以存储多项式。每一个节点的数据域中，存储每项的系数和指数。

解决方案

使用列表

根据上面建立的数据结构模型，我们使用二维列表来表示和存储多项式。

class PolyException(Exception):    def __init__(self, message, code):        self.message = message        self.code = codedef parse_poly(poly):    """    parse poly    :param poly: string    :return: list    """    poly_list = poly.split("+")    result = []    for pos in range(len(poly_list)):        poly_list[pos] = poly_list[pos].strip()        if "X" not in poly_list[pos]:            if not poly_list[pos].isdigit():                raise PolyException("poly format error.", 1001)        temp_list = poly_list[pos].split("X^")        if len(temp_list) != 2 and len(temp_list) != 1:            raise PolyException("poly format error.", 1002)        if len(temp_list) == 2:            key = int(temp_list[1])            if temp_list[0] == "":                value = 1            else:                value = int(temp_list[0])        else:            key = 0            value = int(temp_list[0])        index = -1        for i in range(len(result)):            if result[i][0] == key:                index = i                break        if index != -1:            result[index][1] += value        else:            result.append([key, value])    return resultdef add(poly_a_list, poly_b_list):    for data in poly_b_list:        exist = False        for i in range(len(poly_a_list)):            if data[0] == poly_a_list[i][0]:                poly_a_list[i][1] += data[1]                exist = True                break        if not exist:            poly_a_list.append(data)    return poly_a_listif __name__ == '__main__':    # 1. 输入两个多项式    try:        poly_a = input("Input polynomial A: ")        # poly_a = "X^4+1"        poly_a_list = parse_poly(poly_a)        poly_b = input("Input polynomial B: ")        # poly_b = "3X^2+3X^4+3"        poly_b_list = parse_poly(poly_b)        # 2. 多项式相加        result = add(poly_a_list, poly_b_list)        # 3. 输出结果        print("result is: ", end="")        message_list = []        for data in result:            if data[0] == 0:                message_list.append(str(data[1]))            else:                message_list.append(str(data[1]) + "X^" + str(data[0]))        print("+".join(message_list))    except PolyException as e:        print("errcode: %s" % e.code)        print("errmsg: %s" % e.message)

使用字典

下面采用字典数据结构来存储多项式。当多项式相加时，指数相同（即Key相同），系数相加（即Value相加合并），最后得到的字典就是两个多项式相加的结果。

class PolyException(Exception):    def __init__(self, message, code):        self.message = message        self.code = codedef parse_poly(poly):    """    parse poly    :param poly: string    :return: dict    """    poly_list = poly.split("+")    poly_dict = {}    for pos in range(len(poly_list)):        poly_list[pos] = poly_list[pos].strip()        if "X" not in poly_list[pos]:            if not poly_list[pos].isdigit():                raise PolyException("poly format error.", 1001)        temp_list = poly_list[pos].split("X^")        if len(temp_list) != 2 and len(temp_list) != 1:            raise PolyException("poly format error.", 1002)        if len(temp_list) == 2:            key = temp_list[1]            value = temp_list[0]        else:            key = 0            value = temp_list[0]        if key in poly_dict:            poly_dict[key] += value        else:            poly_dict[key] = value    return poly_dictif __name__ == '__main__':    # 1. 输入两个多项式    try:        poly_a = input("Input polynomial A: ")        # poly_a = "3X^4+1"        poly_a_dict = parse_poly(poly_a)        poly_b = input("Input polynomial B: ")        # poly_b = "3X^4+5"        poly_b_dict = parse_poly(poly_b)    except PolyException as e:        print("errcode: %s" % e.code)        print("errmsg: %s" % e.message)        exit(e.code)    # 2. 多项式相加    for key in poly_b_dict:        if key in poly_a_dict:            poly_a_dict[key] = int(poly_a_dict[key]) + int(poly_b_dict[key])        else:            poly_a_dict[key] = int(poly_b_dict[key])    # 3. 输出结果    print("result is: ")    message = ""    for key in poly_a_dict:        if key == 0:            message += str(poly_a_dict[key]) + " + "        else:            message += str(poly_a_dict[key]) + "X^" + str(key) + " + "    message = message[:-3]    print(message)

使用链表

我们使用来表示和存储多项式。不同于链接中单向链表的节点数据结构，我们重新定义节点结构PolyNode，并重写链表类，仅保留多项式相加相关的方法，并适配新的节点结构。我们将上述代码保存在link.py中：

class PolyNode(object):    def __init__(self, value, exponent):        self.value = value        self.exponent = exponent        self.next = None    def __add__(self, other_node):        self.next = other_node    def __eq__(self, other_node):        if self.value != other_node.value:            return False        elif self.exponent != other_node.exponent:            return False        else:            return True    def update(self, other_node):        self.value = other_node.value        self.exponent = other_node.exponentclass LinkedList(object):    def __init__(self):        self.head = PolyNode(0, 0)    def empty(self) -> bool:        return self.head.next is None    def add(self, node):        if self.empty():            self.head + node        else:            ptr = self.head.next            self.head + node            node + ptr    def extend(self, linked_list):        if linked_list.empty():            return        point = self.head.next        while point.next is not None:            point = point.next        point + linked_list.head.next        return    def remove(self, target: PolyNode):        if self.empty():            raise ValueError("remove from empty linked list")        ptr = self.head.next        left_ptr = self.head        while True:            if ptr == target:                break            if ptr.next is None:                raise IndexError("value do not exist")            ptr = ptr.next            left_ptr = left_ptr.next        if ptr.next is None:            left_ptr.next = None        else:            left_ptr.next = ptr.next        return    def __len__(self):        if self.empty():            return 0        ptr = self.head.next        count = 0        while ptr is not None:            count += 1            ptr = ptr.next        return count    def find(self, exponent):        if self.empty():            return        ptr = self.head        while ptr.next is not None:            ptr = ptr.next            if ptr.exponent == exponent:                return ptrdef create() -> LinkedList:    return LinkedList()def parse_poly(poly):    poly_list = poly.split("+")    poly_linked = create()    for pos in range(len(poly_list)):        poly_list[pos] = poly_list[pos].strip()        if "X" not in poly_list[pos]:            if not poly_list[pos].isdigit():                raise ValueError("poly format error.")        temp_list = poly_list[pos].split("X^")        if len(temp_list) != 2 and len(temp_list) != 1:            raise ValueError("poly format error.")        if len(temp_list) == 2:            key = temp_list[1]            value = temp_list[0]        else:            key = 0            value = temp_list[0]        if value == "":            value = 1        else:            value = int(value)        key = int(key)        node = poly_linked.find(key)        if node is None:            poly_linked.add(PolyNode(value, key))        else:            value += node.value            poly_linked.replace(node, PolyNode(value, key))    return poly_linkeddef add(linked1, linked2):    ptr1 = linked1.head.next    added_node = []    while ptr1 is not None:        ptr2 = linked2.head.next        while ptr2 is not None:            if ptr2.exponent == ptr1.exponent:                ptr1.value += ptr2.value                added_node.append(ptr2)                break            ptr2 = ptr2.next        ptr1 = ptr1.next    for node in added_node:        linked2.remove(node)    if len(linked2) > 0:        linked1.extend(linked2)def print_result(linked):    print("result is:", end="")    ptr = linked.head.next    message_list = []    while ptr is not None:        if ptr.exponent == 0:            message_list.append(str(ptr.value))        else:            message_list.append(str(ptr.value) + "X^" + str(ptr.exponent))        ptr = ptr.next    print("+".join(message_list))if __name__ == '__main__':    try:        poly_a = input("Input polynomial A: ")        # poly_a = "X^4+1"        poly_a_linked = parse_poly(poly_a)        poly_b = input("Input polynomial B: ")        # poly_b = "3X^2+3X^4+6"        poly_b_linked = parse_poly(poly_b)        add(poly_a_linked, poly_b_linked)        print_result(poly_a_linked)    except ValueError as e:        print(str(e))

传送门

转载地址：http://xbsoi.baihongyu.com/

你可能感兴趣的文章