두 개의 다항식이 주어지고 두 개의 다항식의 덧셈을 찾아야 한다고 가정합니다. 다항식은 연결 목록으로 표현되어야 합니다. 다항식의 항은 연결 목록 노드로 표시됩니다. 각 연결 목록 노드에는 계수 값, 거듭제곱 값 및 다음 연결 목록 노드에 대한 포인터가 포함됩니다. 두 개의 연결 목록 다항식을 더한 세 번째 연결 목록을 반환해야 합니다.
따라서 입력이 다음과 같으면
1x^1 + 1x^2 =0 및 2x^1 + 3x^0 =0,
그러면 출력은 3x^1 + 1x^2 + 3x^0 =0
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
더미 :=새로운 다항식 노드
-
node :=새로운 다항식 노드
-
poly1 및 poly2가 비어 있지 않은 동안 수행
-
poly1의 거듭제곱> poly2의 거듭제곱이면
-
다음 노드 :=poly1
-
노드 :=폴리1
-
poly1 :=poly1의 다음
-
-
그렇지 않으면 poly1의 거듭제곱
-
다음 노드 :=poly2
-
노드 :=폴리2
-
poly2 :=poly2의 다음
-
-
그렇지 않으면
-
coef :=폴리1의 계수 + 폴리2의 계수
-
coef가 0이 아니면
-
poly1 :=poly1의 다음
-
poly2 :=poly2의 다음
-
-
-
-
노드 다음:=poly1 또는 poly2
-
더미 다음으로 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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 == None: head = polynomial(element[0], element[1]) else: temp = head while temp.next != None: temp = temp.next if temp.next == None: temp.next = polynomial(element[0], element[1]) return head def show_poly(head): temp = head while temp.next != None: print(str(temp.coefficient) + 'x^' + str(temp.power), end = ' + ') temp = temp.next if temp.next == None: print(str(temp.coefficient) + 'x^' + str(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)
입력
poly1 = create_poly([[1,1], [1,2]]) poly2 = create_poly([[2,1], [3, 0]])
출력
3x^1 + 1x^2 + 3x^0 = 0