자료구조
희소다항식 계산
mickey7
2023. 10. 28. 11:58
from LinkedList import LinkedList
class Term :
def __init__(self,coef,expo):
self.coef = coef
self.expo = expo
class SparsePoly(LinkedList):
def __init__(self):
super().__init__
self.coef = [] #계수
self.expo = [] #지수
def degree(self):
return self.expo[0] #최고차항의 차수는 리스트의 첫번째에!
def read(self): #입력
inp1,inp2 = input("계수 차수 입력(종료:-1)").split()
inp1 = float(inp1)
inp2 = int(inp2)
a = Term(inp1,inp2)
self.expo.append(a.expo)
self.coef.append(a.coef)
while(inp1 != -1 and inp2 != -1):
inp1,inp2 = input("계수 차수 입력(종료:-1)").split()
inp1 = float(inp1)
inp2 = int(inp2)
a = Term(inp1,inp2)
if(inp1 == -1):
break;
self.expo.append(a.expo)
self.coef.append(a.coef)
def evaluate(self,n): #수식연산 (Ex. f(x) = x^2 + x --> f(2) = 2^2 + 2 = 10)
Rsum = 0
for i in range(len(self.coef)):
Tsum = self.coef[i]
for count in range(0,self.expo[i]):
Tsum *= n
Rsum += Tsum
return Rsum
def display(self):#출력
num = len(self.coef)
print("입력 다항식 :",end='')
for i in range (0,num):
print(f"{self.coef[i]}x^{self.expo[i]} +",end=' ')
def display2(self):#출력
num = len(self.coef)
print("A+B :",end='')
for i in range (0,num):
print(f"{self.coef[i]}x^{self.expo[i]} +",end=' ')
#연산자 오버로딩 (A+B)
def __add__(self, polyB):
c = SparsePoly()
Self_lastIndex = len(self.expo)-1
polyB_lastIndex = len(polyB.expo)-1
self_innerIndex = 0
polyB_innerIndex = 0
count = 0
try:
while(self_innerIndex <= Self_lastIndex or polyB_innerIndex<=polyB_lastIndex):
if(self.expo[self_innerIndex]>polyB.expo[polyB_innerIndex]):
c.coef.append(self.coef[self_innerIndex])
c.expo.append(self.expo[self_innerIndex])
self_innerIndex += 1
elif(self.expo[self_innerIndex]==polyB.expo[polyB_innerIndex]):
c.coef.append(self.coef[self_innerIndex]+polyB.coef[polyB_innerIndex])
c.expo.append(self.expo[self_innerIndex])
polyB_innerIndex += 1
self_innerIndex +=1
elif(self.expo[self_innerIndex]<polyB.expo[polyB_innerIndex]):
c.coef.append(polyB.coef[polyB_innerIndex])
c.expo.append(polyB.expo[polyB_innerIndex])
polyB_innerIndex += 1
except:#예외 처리문
if(self_innerIndex > Self_lastIndex):
while(polyB_innerIndex<=polyB_lastIndex):
c.coef.append(polyB.coef[polyB_innerIndex])
c.expo.append(polyB.expo[polyB_innerIndex])
polyB_innerIndex += 1
elif(polyB_innerIndex > polyB_lastIndex):
while(self_innerIndex<=Self_lastIndex):
c.coef.append(self.coef[self_innerIndex])
c.expo.append(self.expo[self_innerIndex])
self_innerIndex += 1
self = c
return self
def add(self,polyB): #다항식 덧셈 함수 , 시간복잡도는 O(n^2)
num1 = len(self.coef)
print("A = ",end='')
for i in range (0,num1):
print(f" {self.coef[i]}x^{self.expo[i]} +",end=' ')
print()
num2 = len(polyB.coef)
print("B = ",end='')
for i in range (0,num2):
print(f"{polyB.coef[i]}x^{polyB.expo[i]} +",end=' ')
print()
c = SparsePoly()
Self_lastIndex = len(self.expo)-1
polyB_lastIndex = len(polyB.expo)-1
self_innerIndex = 0
polyB_innerIndex = 0
count = 0
try:
while(self_innerIndex <= Self_lastIndex or polyB_innerIndex<=polyB_lastIndex):
if(self.expo[self_innerIndex]>polyB.expo[polyB_innerIndex]):
c.coef.append(self.coef[self_innerIndex])
c.expo.append(self.expo[self_innerIndex])
self_innerIndex += 1
elif(self.expo[self_innerIndex]==polyB.expo[polyB_innerIndex]):
c.coef.append(self.coef[self_innerIndex]+polyB.coef[polyB_innerIndex])
c.expo.append(self.expo[self_innerIndex])
polyB_innerIndex += 1
self_innerIndex +=1
elif(self.expo[self_innerIndex]<polyB.expo[polyB_innerIndex]):
c.coef.append(polyB.coef[polyB_innerIndex])
c.expo.append(polyB.expo[polyB_innerIndex])
polyB_innerIndex += 1
except:#예외 처리문
if(self_innerIndex > Self_lastIndex):
while(polyB_innerIndex<=polyB_lastIndex):
c.coef.append(polyB.coef[polyB_innerIndex])
c.expo.append(polyB.expo[polyB_innerIndex])
polyB_innerIndex += 1
elif(polyB_innerIndex > polyB_lastIndex):
while(self_innerIndex<=Self_lastIndex):
c.coef.append(self.coef[self_innerIndex])
c.expo.append(self.expo[self_innerIndex])
self_innerIndex += 1
print("A+B =",end=' ')
for i in range (0,len(c.coef)):
print(f"{c.coef[i]}x^{c.expo[i]} +",end=' ')
print()C언어는 구조체를 활용해서 구했는데 파이썬으로 그대로 구현하기 힘들다고 판단해서 직접 구현
add연산부분을 집중적으로 3부분으로 나눠서 살펴보자면 아래와 같다.
새로운 희소다항식 만들고
마지막 인덱스와, 시작인덱스 초기화단계
0.예외처리 전에 실행되는 try안에 while 반복문으로 비교 대상과 리스트 안의 지수의 크기를 비교한다.
0-1. innerIndex를 0부터 시작해서 비교하는 이유는 차수가 expo 리스트 첫번째부터 크기순으로 들어가기 때문)
0-2. 그리고 빈 차수는 0으로 저장하지 않았다는 점이 중요하더ㅏ.
1. 지수의 크기가 큰 부분(expo)이 새로운 희소다항식에 추가(exop,coef)
2. 지수의 크기가 큰 부분의 innerIndex 1증가
예외 처리문 부분은 고민하다가 결국 위 코드를 재사용하기로 했는데 차수의 크기가 다르다보니 차수가 높은쪽에서 먼저 인덱스 초과 error 문제가 발생했기 때문에 그 경우 예외처리하기로 해보았다.
1. 어느 한 다항식의 내부 인덱스가 범위를 넘어가서 error가 발생하면
2. 다른 다항식의 innerIndex와 차수에 저장된 갯수를 비교해서 아직 innerIndex가 마지막 부분까지 증가하지 못했다고 판단하면
3. while 반복문 안에서 새로운 희소다항식에 증가하지 못했던 부분을 위와 같이 채워넣는 방식을 활용했다.