小白専用場-多項式乗算と加算演算-python言語実現
6795 ワード
目次一、題意理解 二、解題構想 三、多項式加算 四、多項式乗算 五、完全コード 更新、より完全な「データ構造とアルゴリズム」の更新サイトは、python、go、人工知能教育が待っています.https://www.cnblogs.com/nickchen121/p/11407287.html
一、題意理解
テーマ:設計関数はそれぞれ2つの1元多項式の積と和を求めます.
入力フォーマット:2行に分けて入力し、各行にそれぞれ多項式の非ゼロ項の個数を与え、指数降下方式で多項式の非ゼロ項係数と指数(絶対値は1000を超えない整数)を入力します.数字の間はスペースで区切られています.
出力フォーマット:出力は2行に分けられ、積多項式および多項式非ゼロ項の係数と指数をそれぞれ指数降順で出力します.数字間はスペースで区切られていますが、末尾に余分なスペースはありません.ゼロ多項式は0 0を出力しなければならない.
例:[text{既知の2つの多項式:}\begin{align}&3 x^4-5 x^2+6 x-2&5 x^{20}-7 x^4+3 xend{align}]
二、問題を解く構想
ストレージ方式はチェーンテーブルストレージと配列ストレージを採用することができ,チェーン操作を熟知するためにチェーンテーブルストレージを採用する.ポインタ定義のフォーマットは次のとおりです.
三、多項式加算
四、多項式乗算
五、完全なコード
一、題意理解
テーマ:設計関数はそれぞれ2つの1元多項式の積と和を求めます.
入力フォーマット:2行に分けて入力し、各行にそれぞれ多項式の非ゼロ項の個数を与え、指数降下方式で多項式の非ゼロ項係数と指数(絶対値は1000を超えない整数)を入力します.数字の間はスペースで区切られています.
出力フォーマット:出力は2行に分けられ、積多項式および多項式非ゼロ項の係数と指数をそれぞれ指数降順で出力します.数字間はスペースで区切られていますが、末尾に余分なスペースはありません.ゼロ多項式は0 0を出力しなければならない.
例:[text{既知の2つの多項式:}\begin{align}&3 x^4-5 x^2+6 x-2&5 x^{20}-7 x^4+3 xend{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))