[자료구조] 4. 배열의 응용 : 다항식

이전 정리글 ↓

[자료구조] 3. C언어 배열과 구조체

 

다항식

우리가 흔히 아는 다항식을, 배열을 사용해 구현해 보자. 
다항식은 다음과 같이 생겼다.
 

사진에 서술되어 있듯 각각 a = 계수,  x^2 = 변수,  2 = 차수  라 부른다.
가장 큰 차수를 다항식의 차수라 명명한다.
 

( 3x⁵ + 6x⁴ + 0x³ + 0x² + 0x + 10 ) + ( 7x⁴ + 0x³ + 5x² + 0x + 1 ) = C

이 식을 배열로 구현해서, C의 값을 구해보자.
 

다항식 덧셈 프로그램 1

해당 식의 차수에 대한 계수값들의 리스트 coef를 만든다.
하나의 다항식이 1개의 degree변수와 1개의 coef 배열을 필요로 하기 때문에,
묶어서 구조체로 만들고 이 구조체를 사용해 한 개의 다항식을 표현할 수 있다.

#include <stdio.h>
#define MAX(a, b) (((a)>(b) ? (a):(b)))
#define MAX_DEGREE 101
typedef struct {
	int degree;
	float coef[MAX_DEGREE];
} polynomial;

 
아래 코드들과 주석을 잘 살펴보자. 
실습해보면 더 좋다.
 

// 메인함수
int main()
{
    polynomial a = { 5, {3, 6, 0, 0, 0, 10} };
    // 다항식 a의 최대 차수는 5
    polynomial b = { 4, {7,0,5,0,1} };
    // 다항식 b의 최대 차수는 4
    polynomial c;

    print_poly(a);
    print_poly(b);
    printf("---------------------------------------------------");
    c = poly_add1(a, b);

    print_poly(c);
    return 0;
}

// C = A + B 여기서 A와 B는 다항식이다. 구조체가 반환
polynomial poly_add1(polynomial A, polynomial B)
{
    polynomial C;						// 결과 다항식
    int Apos = 0, Bpos = 0, Cpos = 0; 	// 배열 인덱스 변수
    int degree_a = A.degree;            // degree_a는 현재 5
    int degree_b = B.degree;            // degree_b는 현재 4
    C.degree = MAX(A.degree, B.degree); // A와 B 둘 중 최대차수의 값을 가짐 => C.degree는 5

    while (Apos <= A.degree && Bpos <= B.degree) {
        if (degree_a > degree_b) {
            C.coef[Cpos++] = A.coef[Apos++];
            degree_a--;
            // 만약 a의 차수가 b의 차수보다 크다면,
            // C의 계수는 a의 계수를 가진 후 둘다 ++
            // a의 차수에 -- 연산
        }

        else if (degree_a == degree_b) {
            C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
            degree_a--; degree_b--;
            // 만약 a의 차수와 b의 차수가 같다면,
            // C의 계수는 a의 계수와 b의 계수를 더한 값이 됨. 
            // 셋다 ++ 연산 후, a와 b의 차수에 -- 연산
        }

        else {
            C.coef[Cpos++] = B.coef[Bpos++];
            degree_b--;
            // 만약 a의 차수가 b의 차수보다 작다면,
            // C의 계수는 b의 계수를 가진 후 둘다 ++
            // b의 차수에 -- 연산
        }
    }
    return C;
}

void print_poly(polynomial p)
{
    for (int i = p.degree; i > 0; i--)
        printf("%3.1fx^%d + ", p.coef[p.degree - i], i);
    // 정수는 3자리, 소수점은 아래 1째 자리까지 표현
    printf("%3.1f \n", p.coef[p.degree]);
}

 
위의 코드는 간단하고 쉽게 이해된다.
하지만 대부분 항의 계수가 0인 희소 다항식의 경우, 공간이 낭비된다. 
그리고 부호를 다른 경우를 처리하지 못한다는 것. 
 
 

다항식 덧셈 프로그램 2

공간을 절약하기 위해 다른 알고리즘을 구현해보자. 
0이 아닌 항만을 하나의 전역 배열에 저장할 수도 있겠다.  
다항식이 0이 아닌 항들은 (계수, 차수)의 형식으로 구조체 배열에 저장된다.
 
( 3x⁵ + 2x + 8 )의 경우, ( (3, 5), (2, 1), (8, 0) ) 과 같이 저장할 수 있겠다.
이러한 방법으로 다항식을 더해보는 프로그램을 구현해보자.
 
일단 구조체 선언먼저.

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 101
typedef struct {
	float coef;
	int expon;
}polynomial;

polynomial terms[MAX_TERMS] = { { 8, 3}, { 7, 1}, {1,0}, {10, 3}, {3, 2}, {1, 0 } };
int avail = 6;

 
뒤의 함수들은, 프로그램 1을 이해했다면 어렵지 않게 이해할 수 있다.

// 메인함수
int main()
{
	int As = 0, Ae = 2, Bs = 3, Be = 5, Cs, Ce;
	poly_add2(As, Ae, Bs, Be, &Cs, &Ce);
	print_poly(As, Ae);
	print_poly(Bs, Be);
	printf("----------------------------------------------");
	print_poly(Cs, Ce);

	return 0;
}

// 두개의 정수를 비교
char compare(int a, int b)
{
	if (a > b) return '>';
	else if (a == b) return '=';
	else return '<';
}

// 새로운 항을 다항식에 추가
void attach(float coef, int expon)
{
	if (avail > MAX_TERMS) {
		fprintf(stderr, "항의 개수가 너무 많음\n");
		exit(1);
	}
	terms[avail].coef = coef;
	terms[avail].expon = expon;
	avail++;
}

// C = A + B
void poly_add2(int As, int Ae, int Bs, int Be, int* Cs, int* Ce)
{
	float tempcoef;
	*Cs = avail;
	while (As <= Ae && Bs <= Be)
		switch (compare(terms[As].expon, terms[Bs].expon)) {
		case '>':	// A의 차수 > B의 차수
			attach(terms[As].coef, terms[Bs].expon);
			As++;	break;
		case '=':	// A의 차수 = B의 차수
			attach(tempcoef, terms[As].expon);
			As++; Bs++; break;
		case '<':	// A의 차수 < B의 차수
			attach(terms[Bs].coef, terms[Bs].expon);
			Bs++;	break;
		}

	// A의 나머지 항들을 이동함
	for (; As <= Ae; As++)
		attach(terms[As].coef, terms[As].expon);
	// B의 나머지 항들을 이항함
	for (; Bs <= Be; Bs++)
		attach(terms[Bs].coef, terms[Bs].expon);
	*Ce = avail - 1;
}

void print_poly(int s, int e)
{
	for (int i = s; i < e; i++)
		printf("%3.1fx^%d + ", terms[i].coef, terms[i].expon);
	printf("%3.1f^%d\n", terms[e].coef, terms[e].expon);
}