目錄
- 一、題意理解
- 二、解題思路
- 三、多項式加法
- 四、多項式乘法
- 五、完整代碼
更新、更全的《數(shù)據(jù)結(jié)構(gòu)與算法》的更新網(wǎng)站，更有python、go、人工智能教學等著你：https://www.cnblogs.com/nickchen121/p/11407287.html
一、題意理解
題目：
設計函數(shù)分別求兩個一元多項式的乘積與和。
輸入格式：
輸入分2行，每行分別先給出多項式非零項的個數(shù)，再以指數(shù)遞降方式輸入一個多項式非零項系數(shù)和指數(shù)（絕對值均為不超過1000的整數(shù)）。數(shù)字間以空格分隔。
輸出格式：
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項式以及和多項式非零項的系數(shù)和指數(shù)。數(shù)字間以空格分隔，但結(jié)尾不能有多余空格。零多項式應輸出0 0。
例子：
\[ \text{已知兩個多項式：} \\ \begin{align} & 3x^4-5x^2+6x-2 \\ & 5x^{20}-7x^4+3x \end{align} \]
# python語言實現(xiàn)
# 輸入樣例：
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
二、解題思路
存儲方式可以采用鏈表存儲和數(shù)組存儲，為了熟悉鏈式操作，所以采用鏈表存儲。其中指針定義的格式如下所示
三、多項式加法
# python語言實現(xiàn)
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指針處節(jié)點的指數(shù)
tmp2_exp = p2.get_data()[1] # 獲取p2指針處節(jié)點的指數(shù)
# 當指數(shù)相同時，系數(shù)相加，指數(shù)不變
if tmp1_exp == tmp2_exp:
addRes.append([p1.get_data()[0] + p2.get_data()[0], p1.get_data()[1]])
p1 = p1.next # 指針指向下一個節(jié)點
p2 = p2.next
# 當指數(shù)不相同時，選擇較大的指數(shù)項存到結(jié)果中
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
# 對于鏈表中剩余的節(jié)點添加到結(jié)果中
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結(jié)果
# addRes [[5, 20], [-4, 4], [-5, 2], [9, 1], [-2, 0]]
# 列表中每一項代表一各指數(shù)項，其中第一個元素代表系數(shù)，第二個元素代表指數(shù)。如[5，20]：5x^20
# 以下是對addRes進行變形處理
res1 = []
for item in addRes:
if item[0] != 0: # 如果指數(shù)為0，即存在抵消情況，此時不應該輸出
res1.append(item[0])
res1.append(item[1])
if len(res1) == 0: # 如果結(jié)果為0,需要輸出：0 0
return [0, 0]
# 此時的輸出結(jié)果變?yōu)? # [5,20,-4,4,-5,2,9,1,-2,0]
return res1
四、多項式乘法
# python語言實現(xiàn)
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()
# 將系數(shù)相乘和指數(shù)相加放入結(jié)果中
mulRes.append([tmp1[0] * tmp2[0], tmp1[1] + tmp2[1]])
p2 = p2.next
p2 = l2.head # 每次遍歷完l2，都需要回到頭指針，進行下一次遍歷
p1 = p1.next
# 上述運算后，需要合并同類項。定義一個字典，key=指數(shù)，values=系數(shù)
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)
# 結(jié)果變形輸出
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語言實現(xiàn)
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
# 添加節(jié)點
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]
# 當指數(shù)相同時，系數(shù)相加
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:
# 如果多項式中出現(xiàn)抵消，即系數(shù)為0需要刪除
if item[1] != 0:
res2.append(item[1])
res2.append(item[0])
# 如果最后出現(xiàn)空數(shù)組需要輸出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()))
# 變?yōu)殒湵?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))
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
