[자료구조 프로그래밍 연습문제] 다항식 계수 배열, 다항식 곱하기, 구조체

1. 다항식 : 계수 배열 representation

 

교재 2.4.2절에 기술된 다항식 표현 방법 두 가지 중 앞부분에 먼저 기술된 계수 배열 표현의 C 구현으로 다항식 A(x) = a_n*x^n + a_(n-1)*x^(n-1) + ... + a_(1)*x^1 + a_(0)*x^0 을 표현하였다고 하자. 최고차항 a_(n)*x^n의 계수 a_(n)은 0이 아니고 나머지 항들의 계수는 0일 수도 있다고 가정한다. A(x)를 나타내는 변수 a를 교재에서 정의한 구조체 자형 polynomial로 선언하면 C 코드로 polynomial a; 이다.

A. 구조체 자료형 polynomial에서 degree의 의미는 무엇인가?

 

차수, 즉 다항식에서 가장 큰 지수를 뜻한다.

B. a.coef[i] = a_(n-i) 라고 명시된 교재의 계수 저장 방법은 수업시간에 설명한 지수 기준 오름순 및 내림순 중 어느 순서에 해당되는가? (Hint : 다항식 A(x) = 3x^4 + 2x^3 + 2x^2 를 예로 들면 A(x) = 3x^4 + 2x^3 + 2x^2 + 0x^1+ 0x^0 이고 최고차항의 지수 n=4 이므로 i 값을 대입해보면 a.coef[0] = a_(4-0) = a_(4) = 3, coef[1] = a_(4-1) = a_3 = 2, ..., a.coef[4] = a_(4-4) = a_0 = 0 이 된다.)

 

내림순

C. 이와 같은 교재의 계수 저장 방법을 쓸 때 a_i*x^i 항의 계수 a_i 는 계수 배열의 어느 원소에 저장되어 있는가? 즉, a.coef[j] = a_i 라면 j의 값은?

 

n-i

 

 

 

2. 다항식 곱하기 : 계수 배열 representation

 

A. 다항식 A(x) = 3x^4 + 2x^3 + 2x^2 와 B(x) = 4x^2 + 3x + 7를 각각 교재 2.4.2절에서 설명한 계수 배열로 표현하되 (즉, polynomial a, b; 로 선언), 배열에 계수를 저장하는 순서는 coef[i] = a_(n-i) 대신 coef[i] = a_i 로 바꾸었다고 하자. a.degree 및 b.degree의 값은? a.coef[] 및 b.coef[] 배열의 값은?

 

a.degree = 4, b.degree = 2

a.coef[]

a.coef[0]	a.coef[1]	a.coef[2]	a.coef[3]	a.coef[4]
0	0	2	2	3

b.coef[]

b.coef[0]	b.coef[1]	b.coef[2]
7	3	4

B. A의 두 다항식 A(x)와 B(x)를 곱하면 C(x) = 12x^6 + 17x^5 + 35x^4 + 20x^3 + 14x^2 를 결과로 얻는다. C(x)도 교재 2.4.2절의 계수 배열로 표현하되 (즉, polynomial c; 로 선언) 계수 저장 순서는 A에서와 동일하게 coef[i] = a_i 로 바꾸었다고 하자. c.degree의 값은? c.coef[] 배열의 값은?

 

c.degree = 6

c.coef[]

c.coef[0]	c.coef[1]	c.coef[2]	c.coef[3]	c.coef[4]	c.coef[5]	c.coef[6]
0	0	14	20	35	17	12

C. 다항식을 계수 배열로 표현하면, 최고차항 이하 존재하지 않는 항에 대해서도 모두 계수 0을 배열에 저장한다. 따라서 공간 낭비가 클 수 있다. 반면에 다항식 더하기, 곱하기 등의 연산은 매우 간단하게 구현 가능하다. 가령 곱하기의 경우 연습문제 I-3번 문항에서 작성했던 다항식 곱하기 프로그램보다 훨씬 간단한 구현이 가능하다. (연습문제 I-3번 문항에서는 계수 배열이 아니라 항(term) 배열로 다항식을 표현했다.) 임의의 두 다항식 A(x), B(x)가 교재 2.4.2절의 계수 배열로 표현되어 있고 A(x)와 B(x)의 곱을 수행한 결과 다항식 C(x) 역시 동일한 표현 방법으로 저장된다고 하자 (즉, polynomial a, b, c; 로 선언). 단, 배열에 계수를 저장하는 순서는 A(x), B(x), C(x) 모두 coef[i] = a_(n-i) 대신 coef[i] = a_i 로 바꾸었다고 하자. 임의의 두 다항식의 곱하기를 수행하는 함수 polynomial mult(polynomial a, polynomial b)를 C 언어로 작성하시오. (Hint: 아래 C 코드의 ‘가’ 부분을 채우시오. ‘가’에 들어갈 문장 수는 많지 않아 mult() 함수는 매우 짧은 프로그램이다.) 제출: 정확성 테스트 실행화면 및 소스코드

polynomial mult(polynomial A, polynomial B) {
	polynomial C;
	int i, j;
    
	‘가’
    
	return C;
}

polynomial mult(polynomial A, polynomial B)
{
	polynomial C ;
	int i, j;
	for (i=0; i<A.degree+B.degree+1; i++) C.coef[i] = 0;
	C.degree = A.degree + B.degree;
	for (i=0; i<A.degree+1; i++)
		for (j=0; j<B.degree+1; j++)
			C.coef[i+j] += A.coef[i] * B.coef[j];
	return C;
}

#include <stdio.h>
#define MAX_DEGREE 7

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

polynomial mult(polynomial A, polynomial B);

int main()
{
	polynomial a, b, c;
	int i;

	a = { 4, {0, 0, 2, 2, 3, 0, 0} };
	b = { 2, {7, 3, 4, 0, 0, 0, 0} };
	
	c = mult(a, b);
	printf("%d차 ", c.degree);
	for (i = 0; i < c.degree + 1; i++)
		printf("%d ", int(c.coef[i]));

	return 0;
}

polynomial mult(polynomial A, polynomial B)
{
	polynomial C;
	int i, j;

	for (i = 0; i < A.degree + B.degree + 1; i++) C.coef[i] = 0;
	C.degree = A.degree + B.degree;

	for (i = 0; i < A.degree + 1; i++)
		for (j = 0; j < B.degree + 1; j++)
			C.coef[i + j] += A.coef[i] * B.coef[j];

	return C;
}

 

D. C에서는 배열에 계수를 저장하는 순서를 coef[i] = a_i 로 가정하였다. 만약 A(x), B(x), C(x) 모두 교재 2.4.2절의 설명처럼 coef[i] = a_(n-i) 의 순서를 사용하여 표현한다면 C에서 작성한 mult()의 코드에 변화가 생기는지 그렇지 않은지 답하고 이유를 설명하시오.

 

변화가 생기지 않는다. 다항식 A(x)의 일반항의 차수를 i, B(x)의 일반항의 차수를 j라고 했을 때, i항의 배열 index는 (a.degree - i)이고 j항의 배열 index는 (b.degree-j)이다. 두 항의 곱의 차수는 (i + j)이고, mult() 함수에 따르면 이 둘의 곱은 C(x)의 배열 ((a.degree - i) + (b.degree - j)) index에 들어간다. 이는 c.degree에 해당하는 (a.degree + b.degree)에서 곱한 항의 차수 (i + j)를 뺀 값과 동일하다.