[DS]희소 다항식

Soni·2024년 7월 10일

자료구조

희소 다항식끼리의 덧셈 구현하는 게 어렵다.

일단 temp 배열에서 exp이 같은 걸 어떻게 찾아내야 할까?

그리고 지수가 같아도 새로 항을 추가해야 하는 경우, 항이 존재하는 경우 계수만 더하는 경우로도 나눠야 한다.
주어진 다항식 A, B끼리의 지수 비교, 그리고 temp 배열 내에서 지수 존재 여부

일단 index가 0이면 temp에 지수가 존재하는지 볼 필요 없이 무조건 새 항을 하나 추가해야 한다.

일단 조건이

this와 poly의 terms_가 exp의 오름차순으로 정렬되어 있다고 가정
하나의 다항식 안에 exp가 중복되는 term이 없다라고 가정
이므로 temp 배열 속 exp가 같은 게 있는지 검사할 필요가 없다.
예외가 있나? 없다.
구현 성공!!!!
근데 while 문을 각각 3번씩 돌려서 하나로 합칠 수 있을 것 같은데 생각 좀 더 해봐야겠다.

헷갈렸던 부분

while (i < this->num_terms_ || j < poly.num_terms_)

에서 두 조건 중 하나만 false이면 빠져나오는 걸로 착각했는데 or 연산자가 둘 중 하나가 참이면 전체가 참이므로 계속 실행됐다. 따라서 두 조건 중 하나가 false면 빠져나오도록 하려면

while (i < this->num_terms_ && j < poly.num_terms_)

로 해줘야 한다.

차수는 오름차순으로 정렬되어 있음.
차수가 7과 11이라면 차수 11인 배열에서는 더 이상 7과 더해질 수 있는 게 없다는 거니깐(오름차순 정렬이므로) 차수가 7인 것을 polynomial 배열에 추가.
더해서 만들어지는 polynomial도 차수가 정렬된 형태로 만들고 싶음.

강의 보니깐 거의 비슷하게 구현했다.

추가해야할 부분

float sum = terms_[i].coef + poly.terms_[j].coef;
if (sum != 0.0f)
{
	temp.NewTerm(sum, terms_[i].exp);
    if (sum != 0.0f)
    {
    	temp.NewTerm(sum, terms_[i].exp);
    }
    i++;
    j++;
 }