알고리즘 Poly_Add를 구현해라

• 입력 : 다항식 A와 B가 저정된 구조체 배열 poly, 다항식의 시작과 끝을 가리키는 인덱스 변수 (As/Ae, Bs/Be), 빈 공간의 시작위치 avail
• 출력 : A와 B를 더한 다항식 C

Poly_Add 알고리즘은 임의의 두개의 다항식의 합을 구하는 알고리즘이다. 다항식의 합에서 생각해야 하는 것은 차수가 동일 할 때는 차수가 같은 것끼리 더하고 다른 것은 그냥 두면 된다. 먼저 차수와 계수를 구조체로 받고 이것을 이용하면 되는데 반복문과 조건문 만을 이용해도 되지만 이것들을 일차원 배열에 값을 넣고 A다항식과 B의 다항식 그리고 두개를 더해서 생기는 C의 다항식을 저장할 위치를 변수로 받는다.

#include <stdio.h>
#define NO_OF_TERMS 20

typedef struct {
	int coef;
	int expon;
}Term;
int Cs;
int Ce;
void insert(Term poly[], int avail, int coef, int expon) {
	poly[avail].coef = coef;	/*저장된 위치에 계수 넣기*/
	poly[avail].expon = expon;	/*저장된 위치에 차수 넣기*/
}
void Poly_Add(Term poly[], int As, int Ae, int Bs, int Be, int* avail) {
	int n = 0;
	int sumCoef = 0;
	Cs = *avail;
	while (As <= Ae && Bs <= Be) /*다항식 C 만들기*/
	{
		if (poly[As].expon > poly[Bs].expon)	/*A의 차수가 B보다 클 때*/
			n = 1;
		else if (poly[As].expon == poly[Bs].expon)	/*A의 차수가 B와 같을 때*/
			n = 2;
		else     /*B의 차수가 A보다 클 때*/
			n = 3;
		switch (n)
		{
		case 1:
			insert(poly, *avail, poly[As].coef, poly[As].expon);
			As += 1;
			break;
		case 2:
			sumCoef = poly[As].coef + poly[Bs].coef;	/*A와 B계수를 더함*/
			if (sumCoef)
				insert(poly, *avail, sumCoef, poly[As].expon);
			else       /*A와 B계수를 더해서 0되기 때문에 avail -= 1*/
				*avail -= 1;
			As += 1;
			Bs += 1;
			break;
		case 3:
			insert(poly, *avail, poly[Bs].coef, poly[Bs].expon);
			Bs += 1;
			break;
		}
		*avail += 1;
	}
	for (int i = As; i < Ae + 1; i++) {      /*A의 잔여항 복사*/
		insert(poly, *avail, poly[i].coef, poly[i].expon);
		*avail += 1;
	}
	for (int i = Bs; i < Be + 1; i++) {     /*B의 잔여항 복사*/
		insert(poly, *avail, poly[i].coef, poly[i].expon);
		*avail += 1;
	}
	Ce = *avail - 1;
}
void Print_Poly(Term poly[], int As, int Ae, int Bs, int Be, int avail) {
	for (int i = 0; i < avail; i++) {
		if (i == As)
			printf("Polynomial A : ");
		else if (i == Bs)
			printf("Polynomial B : ");
		else if (i == Cs)
			printf("Polynomial C : ");
		printf("%d*x^%d", poly[i].coef, poly[i].expon);
		if (i == Ae || i == Be || i == Ce)
			printf("\\n\\n");
		else
			printf(" + ");
	}
}

int main() {
	Term poly[NO_OF_TERMS] = { {3, 5}, {2, 3}, {2, 0}, {4, 4}, {5, 3}, {2, 1} }; 
  /*저장된 A,B 다항식의 계수와 차수*/
	int As = 0;
	int Ae = 2;
	int Bs = 3;
	int Be = 5;
	int avail = 6;
	Poly_Add(poly, As, Ae, Bs, Be, &avail);
	Print_Poly(poly, As, Ae, Bs, Be, avail);
	return 0;
}

결과

1. 주어진 값을 이용해서 출력

2. 두 다항식의 차수를 동일하게 하고 출력

3. 두 다항식의 차수를 다르게 하고 출력

과제에 대한 고찰

이번 문제는 정적배열을 가지고 문제를 풀었다. 차수를 비교해서 switch를 이용해 C를 만들고 난 후 잔여항이 왜 남는지 고민한거 말고는 어려운 문제는 아니였다. 처음에는 이 문제를 볼 때 동적배열이 필요함을 알 수 있었다. 정적배열을 가지고 풀면 만약 다항식이 이 정해진 배열의 길이를 넘을 수 있기 때문이다. 그래서 이 문제를 풀기전 20분동안 이문제를 해결하라는 문제를 받았을 때 malloc을 사용해봤는데 다항식을 scanf로 받을 때 마다 relloc을 이용해서 공간을 늘리려니 문제가 많았다. 이 다음에 배우겠지만 연결리스트로 풀면 좋겠다는 생각이 많이 든 그런 문제였다.