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

배열의 응용 : 다항식

---

$ p(x)=a_nx^n + a_{n-1}x^{n-1}+ ... + a_1x + a_0 $를 배열을 이용하여 표현해보자

• 첫 번째 방법 : 모든 차수의 계수값을 배열에 저장 (ex. 10x^5 + 6x + 3)

  #define MAX_DEGREE 101 // 다항식의 최대 차수 + 1
  typedef struct {
      int degree;
      float coef[MAX_DEGREE];
  } polynomial;
  
  polynomial a = {5, {10, 0, 0, 0, 6, 3}}

  • 문제점 : 대부분의 항의 계수가 0인 희소 다항식의 경우에 공간의 낭비가 심함

  • 장점 : 다항식의 덧셈이나 뺄셈 시에 같은 차수의 계수를 쉽게 찾을 수 있어 알고리즘이 간단해짐

  • ex) 두 다항식을 더하는 프로그램

    • 차수가 큰 항을 새로운 구조체로 이동시키고, 차수가 같으면 두 구조체의 coef(계수)를 더하여 새로운 구조체의 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;
  
  // 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;
      int degree_b = B.degree;
      C.degree = MAX(A.degree, B.degree); // 결과 다항식 차수
  
      while (Apos <= A.degree && Bpos <= B.degree) {
          if (degree_a > degree_b) {  // A항 > B항
              C.coef[Cpos++] = A.coef[Apos++];
              degree_a--;
          }
          else if (degree_a == degree_b) {  // A항 == B항
              C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
              degree_a--; degree_b--;
          }
          else {            // B항 > A항
              C.coef[Cpos++] = B.coef[Bpos++];
              degree_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);
      printf("%3.1f \n", p.coef[p.degree]);
  }
  
  // 주함수
  int main(void)
  {
      polynomial a = { 5,{ 3, 6, 0, 0, 0, 10 } };
      polynomial b = { 4,{ 7, 0, 5, 0, 1 } };
      polynomial c;
  
      print_poly(a);
      print_poly(b);
      c = poly_add1(a, b);
      printf("-----------------------------------------------------------------------------\n");
      print_poly(c);
      return 0;
  }

• 두 번째 방법 : 공간을 절약하기 위해 다항식에서 0이 아닌 항만을 하나의 전역 배열에 저장

  다항식의 0이 아닌 항들을 (계수, 차수) 형식으로 구조체 배열에 저장

  #define MAX_TERMS 101
  struct {
      float coef;
      int expon;
  } terms[MAX_TERMS];
  int avail; // 현재 비어있는 요소의 인덱스를 저장

  • ex) 10x^5 + 6x + 3의 경우 ((10, 5), (6, 1), (3, 0))으로 표시하는 것

  • 장점 : 항의 총 개수가 MAX_TERMS를 넘지만 않으면 많은 다항식을 저장할 수 있다.

  • 단점 : 하나의 다항식이 시작되고 끝나는 위치를 가리키는 인덱스 변수들을 관리하여야 한다

    차수 또한 저장해야 하기 때문에 첫 번째 방법보다 공간을 더 많이 필요로 할 수도 있다

    다항식의 덧셈을 비록한 연산들의 구현이 첫 번재 방법보다 좀 더 어려워진다

  • 두 개의 다항식을 더하는 알고리즘

    • 두 다항식 A, B의 각 항 차수를 비교하여, 차수가 같으면 계수를 더해서 새로운 다항식 C로 옮기고, 차수가 다르면 A와 B중에서 차수가 큰 항을 C로 옮긴다.

    • 위 과정을 어느 한쪽의 다항식이 끝날 때 까지 반복

  #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;
  
  // 두개의 정수를 비교
  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[As].expon);
              As++;            break;
          case '=':     // A의 차수 == B의 차수
              tempcoef = terms[As].coef + terms[Bs].coef;
              if (tempcoef)
                  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.1fx^%d\n", terms[e].coef, terms[e].expon);
  }
  //
  int main(void)
  {
      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("-----------------------------------------------------------------------------\n");
      print_poly(Cs, Ce);
      return 0;
  }

참조) C언어로 쉽게 풀어 쓴 자료구조(천인국, 2016, 생능출판사)