Cho hai đa thức biểu diễn bằng linked list. Mỗi node chứa hệ số, số mũ, con trỏ next. Cần trả về linked list là tổng hai đa thức.
Thuật toán
- dummy = node = Polynomial()
- While poly1 và poly2:
- Nếu power1 > power2: node.next = node = poly1; poly1 = poly1.next
- Nếu power1 < power2: node.next = node = poly2; poly2 = poly2.next
- Ngược lại (power bằng nhau): coef = coeff1 + coeff2; nếu coef != 0: tạo node mới; poly1, poly2 tiến next
- node.next = poly1 or poly2
- Return dummy.next
Code Python
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}', end=' = 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]])
poly2 = create_poly([[2,1], [3,0]])
poly3 = solve(poly1, poly2)
show_poly(poly3)
Input
poly1 = create_poly([[1,1], [1,2]]); poly2 = create_poly([[2,1], [3,0]])
Output
3x^1 + 1x^2 + 3x^0 = 0