자료구조 [02]다항식의 덧셈(배열) 알고리즘

다항식의 덧셈(배열)

1. 일반

제목 : 다항식의 덧셈(배열)

2) 작성자:

Driver – OOO

Observer – OOO

3) 작성일 및 Version No. : 2015-10-10

4) 알고리즘 설명

- 목적 및 기능 :

● 다항식의 덧셈은 지수가 같은 항들에 대한 계수의 덧셈으로 이루어진다. 예를들어

        A(x) = 5x¹⁰+4x⁵+3, B(x) = 3x⁵+8x²+5

 

- 다항식의 배열

	0	1	2	3	4	5	6	......	99
coef	5	4	3	3	8	5
exp	10	5	0	5	2	0
	sp		fp	sp		fp	avail

위의 두 다항식을 더한 결과는 C(x) = 5x¹⁰+7x⁵+8x²+8과 같다. 따라서 두 다항식을 더하기 위해서는 다항식에 포함된 항들의 지수가 서로 같은지 검사하고 같다면 두 항의 계수를 더한다. 그리고, 한쪽다항식에만 존재하는 항은 그대로 복사하는 원리가 사용된다. 이때 각 항들의 지수는 배열의 인덱스와 동일하기 때문에 이 인덱스를 통해 두 다항식에 포함된 항들의 지수를 쉽게 비교할 수 있을 것이다.

2. 프로그램 설계 (Driver)

1) 환경 –

프로그래밍 언어 : C

도구, 기계 : Eclipse IDE for C/C++ Developers

2) 프로그램 구조 –

다항식의 덧셈(배열)
모듈 (함수기능)	main() 프로그램 전체의 시작부분으로써 실행을 담당한다. void padd(int sp, int fp, int sq, int fq, int *sr, int *fr); 배열의 다항식처음과 끝을 알려주는 함수 void attach(float a, int b); 지수와 계수의 입력을 위한 함수
인수설명	int sp 다항식의 첫 번째를 구분해주는 변수 int fp 다항식의 끝을 구분해주는 변수 int *sr 다항식의 덧셈된 값의 첫 번째를 구분해주는 변수 int *fr 다항식의 덧셈된 값의 끝을 구분해주는 변수
전역변수	typedef struct{float coef; int exp;} polyType; 다항식의 지수부문과 계수부문을 나타내는 구조체 int sp, fp, sq, fq, sr, fr, avail; 다항식의 처음과 끝을 나타내는 변수
지역변수	float v1; int v2; 지수와 계수의 입력을 위한 변수
외부참조	외에 특별한 외부참조 없음.

3. 테스트 및 분석 (Observer)

	입력 값	예상결과	실제결과
Test 01	p(x) = 3x2+4x+5 q(x) = 2x4+2x+4 (일반적인 입력사항)	2x4+3x2+6x+9	2x4+3x2+6x+9

C Programming code

#include <stdio.h> #define MAX_SIZE 100 //배열의 최대 갯수 typedef struct{ //다항식의 구조체 float coef; int exp; } polyType; polyType poly[MAX_SIZE]; //다항식의 배열 int sp, fp, sq, fq, sr, fr, avail; //처음과 끝을 위한 변수 void padd(int sp, int fp, int sq, int fq, int *sr, int *fr); //다항식의 저장을 위한 함수 void attach(float a, int b); //입력값 저장을 위한 함수 int main() { float v1; //계수입력을 위한 변수 int v2; //지수입력을 위한 변수 int i; //일반적 변수 avail = sp = 0; //빈공간을 나타내는 변수 //p식 입력 while(1) { printf("p식 계수: "); //지수 계수 입력 scanf("%f", &amp;v1); printf("p식 지수: "); scanf("%d", &amp;v2); printf("\n"); poly[avail].coef = v1; //다항식의 지수 저장 poly[avail].exp = v2; //다항식의 계수 저장 avail++; //저장 배열 위치 증가 if(v2 == 0) { fp = avail - 1; //다항식의 끝을 표시 sq = avail; break; } } //q식 입력 while(1) { printf("q식 계수: "); //q다항식의 지수 계수 입력 scanf_s("%f", &v1); printf("q식 지수: "); scanf_s("%d", &v2); printf("\n"); poly[avail].coef = v1; //다항식의 지수 저장 poly[avail].exp = v2; //다항식의 계수 저장 avail++; //저장 배열 위치 증가 if(v2 == 0) //다항식의 끝을 나타냄 { fq = avail - 1; break; } } padd(sp,fp,sq,fq, &sr,&fr); for (i = sr ; i <= fr ; i++){ if(poly[i].exp == 0) { printf("%f ", poly[i].coef); //상수는 지수 출력 안함 continue; } printf("%fX^%d", poly[i].coef, poly[i].exp); //다항식의 출력 if(i != fr) printf(" + "); } return 0; } void padd (int sp, int fp, int sq, int fq, int *sr, int *fr) { float temp; *sr = avail; while (sp <= fp && sq <= fq){ if (poly[sp].exp > poly[sq].exp) //지수 비교 { attach(poly[sp].coef, poly[sp].exp); //값을 그냥 저장 sp++; } else if (poly[sp].exp < poly[sq].exp) //지수 비교 { attach(poly[sq].coef, poly[sq].exp); //값을 그냥 저장 sq++; } else { temp = poly[sp].coef + poly[sq].coef; //지수가 같을 경우 //<span style="color: rgb(51, 51, 51); font-family: NanumGothic, 나눔고딕, &quot;Malgun Gothic&quot;, &quot;맑은 고딕&quot;, Dotum, 돋움, Gulim, 굴림, Verdana, Arial, &quot;Trebuchet MS&quot;; text-align: justify;">if (temp || temp ==0)</span> { attach(temp, poly[sp].exp); //더한값 저장 sp++; sq++; } } } for( ; sp <= fp ; sp++ ) attach(poly[sp].coef, poly[sp].exp); for( ; sq <= fq ; sq++) attach(poly[sq].coef, poly[sq].exp); *fr = avail - 1; } void attach (float a, int b) { poly[avail].coef = a; //계수값 저장 poly[avail].exp = b; //지수값 저장 avail++; }