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

Posted at 2015. 10. 12. 23:38 | Posted in 컴퓨터과학[2-2]/[2-2]자료구조

다항식의 덧셈(배열)

1. 일반

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

2) 작성자:

Driver  OOO

Observer  OOO

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

4) 알고리즘 설명

- 목적 및 기능 :

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

        A(x) = 5x10+4x5+3, B(x) = 3x5+8x2+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) = 5x10+7x5+8x2+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++; }


  1. 개구리
    감사합니다.
  2. 개구리
    15년도에 벌써 이런 것을... 14년도 입학해서 아무것도 모르던 시절이었는데,
    제가 참 늦네요. 그런데 왜 검색하면 맨날 불린님이 검색되죠 하하
  3. 개구리
    코드 수정 할 부분들
    #define _CRT_SECURE_NO_WARNINGS ← scanf 4996 오류 처리, 다른 방법은 scanf_s를 사용해도 됩니다.
    main 앞에 자료 반환형 "int"가 빠져 있습니다.
    &amp = && ← and 기호가 html tag로 바뀐 것 같습니다.
    &lt &gt = < > ← 대소 비교 기호가 html tag로 바뀐 것 같습니다.
    입력 방법은 x^2 + 5 일 경우
    x^2 입력시 : 계수가 1이 되고 지수는 2가 된다.
    상수 5 입력시 : 계수 5, 지수 0이 된다.
  4. 개구리
    연산후 temp = poly[sp].coef + poly[sq].coef; 에서 temp 값이 0이 되면 먹통이 되는 현상 발견
    다음 줄 if (temp)를 if (temp || temp ==0)로 수정

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기