พหุนามเก็บใน linked list โหนดแต่ละตัวมี coefficient, power, next บวก 2 พหุนามโดย merge แบบ merge sort: เปรียบเทียบ power ใส่ power มากกว่าก่อน ถ้า power เท่ากัน บวก coefficient ถ้าผลรวมไม่เป็น 0 สร้างโหนดใหม่
ขั้นตอนการทำงาน
- สร้าง dummy node และ node pointer
- วนลูป poly1 และ poly2 ยังไม่หมด
- ถ้า poly1.power > poly2.power: per node = poly1, ขยับ poly1
- ถ้า poly1.power < poly2.power: per node = poly2, ขยับ poly2
- ถ้าเท่ากัน: บวก coefficient ถ้าไม่เป็น 0 สร้างโหนดใหม่ ขยับทั้งคู่
- ต่อส่วนที่เหลือของ poly1 หรือ poly2
- คืน dummy.next
ตัวอย่างโค้ด
class polynomial:
def __init__(self, coeff=0, pow=0, nxt=None):
self.coefficient = coeff
self.power = pow
self.next = nxt
def create_poly(expression):
head = None
for element in expression:
if head is None:
head = polynomial(element[0], element[1])
else:
temp = head
while temp.next:
temp = temp.next
temp.next = polynomial(element[0], element[1])
return head
def show_poly(head):
temp = head
while temp.next:
print(f"{temp.coefficient}x^{temp.power}", end=" + ")
temp = temp.next
print(f"{temp.coefficient}x^{temp.power} = 0")
def solve(poly1, poly2):
dummy = node = polynomial()
while poly1 and poly2:
if poly1.power > poly2.power:
node.next = node = poly1
poly1 = poly1.next
elif poly1.power < poly2.power:
node.next = node = poly2
poly2 = poly2.next
else:
coef = poly1.coefficient + poly2.coefficient
if coef:
node.next = node = polynomial(coef, poly1.power)
poly1 = poly1.next
poly2 = poly2.next
node.next = poly1 or poly2
return dummy.next
poly1 = create_poly([[1,1], [1,2]]) # 1x^1 + 1x^2
poly2 = create_poly([[2,1], [3,0]]) # 2x^1 + 3x^0
poly3 = solve(poly1, poly2)
show_poly(poly3) # Output: 3x^1 + 1x^2 + 3x^0 = 0
อินพุต/เอาต์พุต
Input: poly1=[[1,1],[1,2]], poly2=[[2,1],[3,0]] Output: 3x^1 + 1x^2 + 3x^0 = 0
