2장 - 다항식의 덧셈 구현하기

C언어에서 다항식을 구현하는 방법

 

방법1: 모든 지수의 계수들을 내림차순으로 저장

 

#define MAX_DEGREE 101
typedef struct{
	int degree;
    float coef[MAX_DEGREE];
   }polynomial;

예시) 2x^3 + x^2 -1  

[3, (2,1,0,-1)] 

[최고차항 지수, (계수들 순서대로)]

 

또다른 예시로 x^100 +1이라는 식이 있을 때,

이 방법으로 저장하기 위해선 [100,(1,0,0,0,0.....0,0,0,0,1)]을 저장해야하는데,

계수가 0인 항이 많은 경우 메모리 낭비가 심하다.

 

---

방법 2: 지수와 계수를 모두 저장

#define MAX_TERMS 100
typedef struct{
	float coef;
    int expon;
}polynomial;
polynomial terms[MAX_TERMS]; #여러 다항식을 저장할 terms배열
int avail =0; #저장할 위치

예시) x^100 + 1    ==> {(1,100),(1,0)}

계수,지수를 한 쌍으로 저장한다.

 

근데 이 방법이 1번 방법보다 항상 더 적은 공간을 사용하는 것은 아니다.

x+1이라는 식이 있다고 할 때

1번방법: [1,(1,1)]

2번방법:{(1,1),(1,0)} 이 되므로 2번방법이 더 많은 메모리를 사용할 것 같다.(뇌피셜)

 

이 2번방식을 이용하여 다항식을 더하는 프로그램을 작성해보자.

 

#include <stdio.h>
#include <stdlib.h> //exit 사용하기위해 include 하였음

#define MAX_TERMS 100
#define COMPARE(a,b) (a>b)?1:((a==b)?0:-1)
typedef struct {
	float coef;
	int expon;
}polynomial;
polynomial terms[MAX_TERMS];
int avail = 0;
void attach(float coefficient, int exponent) {
	//다항식에 새로운 항을 추가하는 함수
	if (avail >= MAX_TERMS)
	{
		fprintf(stderr, "에러");
		exit(1);
	}
	terms[avail].coef = coefficient;
	terms[avail++].expon = exponent; //실행 후 avail  1 증가하도록 하였음

}
void p_add(int start_a, int finish_a, int start_b, int finish_b, int* start_d, int* finish_d)
{
	float coefficient; //계수
	*start_d = avail; //새로운 식의 시작위치
	while (start_a <=finish_a && start_b <= finish_b)
		switch (COMPARE(terms[start_a].expon, terms[start_b].expon)) //a다항식 최고차항과 b다항식 최고차항의 지수 비교
		{
			case -1: //a.expon < b.expon
				attach(terms[start_b].coef, terms[start_b].expon); //b의 최고차항을 새로운 식으로 추가
				start_b++;//b의 최고차항을 꺼내 썼으니 start_b 1증가시킴
				break;
			case 0: //a.expon == b.expon
				coefficient = terms[start_a].coef + terms[start_b].coef; //a의 계수+b의 계수 =  새로운 항 계수
				if (coefficient) attach(coefficient, terms[start_a].expon); //계수 합이 0이 아니면 새로운 항 추가
				start_a++; start_b++; //a,b 둘다 썼으니 start 1씩 증가
				break;
			case 1: //a.expon > b.expon
				attach(terms[start_a].coef, terms[start_a].expon); //a의 최고차항을 새로운 식에 추가
				start_a++;
				break;

		}
	//이제 a나 b에 남은 항이 있을 것인데, 그 식을 몽땅 새 식에 추가할 것임
	for (; start_a <= finish_a; start_a++) {
		attach(terms[start_a].coef, terms[start_a].expon);
	}
	for (; start_b <= finish_b; start_b++) {
		attach(terms[start_b].coef, terms[start_b].expon);
	}
	*finish_d = avail - 1; //새로운 식의 끝나는 위치


				
}
int main() {
	//a= 3x^14 + 2x^8  => [(3,14),(2,8)]
	//b= 8x^14 + 3x^10 + 10  =>[(8,14),(3,10)]
	int starta = 0;
	terms[0].coef = 3;
	terms[0].expon = 14;
	terms[1].coef = 2;
	terms[1].expon = 8;
	int finisha = 1;
	int startb = 2;
	terms[2].coef = 8;
	terms[2].expon = 14;
	terms[3].coef = 3;
	terms[3].expon = 10;
	int finishb = 3;
	
	int startd;
	int finishd;

	avail = 4; //위의 식을 내가 직접 입력했기떄문에 avail을 수정하였음
	p_add(starta, finisha, startb, finishb, &startd, &finishd);

	printf("%d %d\n", startd, finishd);


	for (int i=startd; i <= finishd; i++) {
		printf("%d.x^%d ", int(terms[i].coef), terms[i].expon);
	}
}

 

p_add 함수의 인자 중 int* start_d, int*finish_d가 있다.

이는 함수 내에서 start_d변수의 값과 finish_d변수의 값을 수정할 수 있도록 call by address한 것이다

 

마지막 main함수는 내가 결과를 눈으로 확인하고싶어 간단하게 작성한 것임.

 

다항식 a, 다항식 b가 있을 때 동작하는 과정:

1. a,b의 최고차항의 지수를 비교한다.

2. 최고차항 지수가 같다면 두 최고차항을 더하여 새로운 식에 넣는다

3. 최고차항 지수가 다르다면 더 큰 쪽의 항을 새로운 식에 넣는다

4. 위 과정을 a또는 b식이 끝날때까지 반복

5. 반복 후 남은 식을 몽땅 새로운 식에 추가한다.

 

 

---

이 방법의 경우 A,B다항식이 저장된 상태에서 A다항식에 항을 추가,제거하는 등의 수정이 힘들다는 단점이 있다.

위 구현에서는 terms[]배열이 가득 찼을 때 오류메세지를 반환하고 프로그램을 종료시켰으나

종료 대신 terms배열의 크기를 2배로 늘려주는 등의 기능을 추가하면 더 좋을 것 같다.