다항식 p(x) 를 1차 다항식 x - a 로 나눌 때의 몫과 나머지를 구하는 조립제법을
C 언어로 구현해 보았다. 조립제법은 일명 Horner의 방법이라고도 불리우는데, 이는
x = a 에서 다항식 p(x)의 값 p(a)을 계산하는 가장 빠른 알고리즘이기도 하다.

         p(x) = (x - a)q(x) + r

여기서 r은 나머지이며 r = p(a) 이다. 또 q(x)는 몫이다.

[참고]
    * 온라인으로 조립제법 표 만들기 손으로 계산하는 조립제법 표 
    * 온라인으로 구하는 다항식의 도함수: 조립제법을 이용한 다항식의 도함수


아래의 소스파일은 Ch를 사용하면 컴파일하지 않고 수정 없이 그대로 실행된다.
(실행 예:  ch testSyntheticDivision.c 1 2 3 4 5  )


  1. /*
  2.  *  Filename: testSyntheticDivision.c
  3.  *
  4.  *  Purpose:  Find the quotient and remainder when some polynomial is
  5.  *            divided by a monic polynomial of the first degree.
  6.  *
  7.  *  Compile:  cl testSyntheticDivision.c
  8.  *
  9.  *  Execute:  testSyntheticDivision -2 1 3 3 1
  10.  */
  11. #include <stdio.h>
  12. #include <string.h>
  13. #include <math.h>
  14. #include <memory.h>
  15. void print(char str[]) {
  16.     printf("%s", str);
  17. }
  18. void println(char str[]) {
  19.     printf("%s\n", str);
  20. }
  21. // 사용법 표시
  22. void printUsage() {
  23.      println("사용법: testSyntheticDivision [수] [피제식의 계수들]");
  24.      println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.");
  25. }
  26. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
  27. // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
  28. char *simplify(double v, int width) {
  29.     int n, len;
  30.     static char t[] = "                               ";
  31.     char tmp[] = "                               ";
  32.     sprintf(t, "%g", v);
  33.     n = strlen(t);
  34.     if ((n > 2) && (t[n - 2] == '.') && (t[n - 1] == '0'))
  35.         t[n-2] = '\0';
  36.     len = strlen(t);
  37.     strcpy(tmp, t);
  38.     if (len < width) {
  39.         strncpy(t, "               ", width - len);
  40.         t[width - len] = '\0';
  41.         strcat(t, tmp);
  42.     }
  43.     return (char *) t;
  44. }
  45. // 다항식을 내림차순의 문자열로로 반환하는 함수
  46. // 반환된 문자열은 동적 메모리에 존재하므로.
  47. // 사용 후 반드시 해제(free)하여야 한다.
  48. char *toPolyString(double c[], int size) {
  49.     int SIZE = size;
  50.     int i;
  51.     static char t[300];
  52.     char tmp[80];
  53.     char *pc = simplify(c[0], -1);
  54.     char *pci;
  55.     if (SIZE > 2) {
  56.         if (strlen(pc) == 1 && pc[0] == '1')
  57.             sprintf(t,  "x^%d", SIZE - 1);
  58.         else if (strlen(pc) == 2 && pc[0] == '-' && pc[1] == '1')
  59.             sprintf(t,  "-x^%d", SIZE - 1);
  60.         else
  61.             sprintf(t,  "%s x^%d", simplify(c[0], -1), SIZE - 1);
  62.     }
  63.     else if (SIZE == 2) {
  64.         if (strlen(pc) == 1 && pc[0] == '1')
  65.             strcpy(t,  "x");
  66.         else if (strlen(pc) == 2 && pc[0] == '-' && pc[1] == '1')
  67.             strcpy(t,  "-x");
  68.         else
  69.             sprintf(t,  "%s x", simplify(c[0], -1));
  70.     }
  71.     else if (SIZE == 1) {
  72.         sprintf(t,  "%s", simplify(c[0], -1));
  73.     }
  74.     for (i = 1; i < SIZE; i++) {
  75.         pci = simplify(c[i], -1);
  76.         if (SIZE - 1 - i > 1) {
  77.             if (c[i] > 0.0) {
  78.                 if (strlen(pci) == 1 && pci[0] == '1') {
  79.                     sprintf(tmp,  " + x^%d", SIZE - 1 - i);
  80.                     strcat(t, tmp);
  81.                 }
  82.                 else {
  83.                     sprintf(tmp,  " + %s x^%d", simplify(c[i], -1), SIZE - 1 - i);
  84.                     strcat(t, tmp);
  85.                 }
  86.             }
  87.             else if (c[i] < 0.0) {
  88.                 if (strlen(pci) == 2 && pci[0] == '-' && pci[1] == '1') {
  89.                     sprintf(tmp,  " - x^%d", SIZE - 1 - i);
  90.                     strcat(t, tmp);
  91.                 }
  92.                 else {
  93.                     sprintf(tmp,  " - %s x^%d", simplify(fabs(c[i]), -1), SIZE - 1 - i);
  94.                     strcat(t, tmp);
  95.                 }
  96.             }
  97.         }
  98.         else if (SIZE - 1 - i == 1) {
  99.             if (c[i] > 0.0) {
  100.                 if (strlen(pci) == 1 && pci[0] == '1') {
  101.                     strcat(t, " + x");
  102.                 }
  103.                 else {
  104.                     sprintf(tmp,  " + %s x", simplify(c[i], -1));
  105.                     strcat(t, tmp);
  106.                 }
  107.             }
  108.             else if (c[i] < 0.0) {
  109.                 if (strlen(pci) == 2 && pci[0] == '-' && pci[1] == '1') {
  110.                     strcat(t, " - x");
  111.                 }
  112.                 else {
  113.                     sprintf(tmp,  " - %s x", simplify(fabs(c[i]), -1));
  114.                     strcat(t, tmp);
  115.                 }
  116.             }
  117.         }
  118.         else if (SIZE - 1 - i == 0) {
  119.             if (c[i] > 0.0) {
  120.                 sprintf(tmp,  " + %s", simplify(c[i], -1));
  121.                 strcat(t, tmp);
  122.             }
  123.             else if (c[i] < 0.0) {
  124.                 sprintf(tmp,  " - %s", simplify(fabs(c[i]), -1));
  125.                 strcat(t, tmp);
  126.             }
  127.         }
  128.     }
  129.     return (char *) t;
  130. }
  131. // 다향식 나눗셈 결과를
  132. //     (피제식) = (제식)(몫) + (나마지)
  133. // 형태로 출력
  134. void printDivisionResult(double a, double c[], double b[], int size) {
  135.     int SIZE = size;
  136.     int i;
  137.     double *pTmpPoly;
  138.     double r;
  139.     double monic[] = { 1.0, 0.0 };
  140.     print("  ");
  141.     print(toPolyString(c, SIZE));
  142.     println("");
  143.     print("    = ( ");
  144.     monic[1] = -a;
  145.     print(toPolyString(  monic, 2 ));
  146.     print(" )");
  147.     pTmpPoly = (double *)  calloc(SIZE - 1, sizeof(double));
  148.     for (i = 0; i < SIZE - 1; i++) {
  149.         pTmpPoly[i] = b[i];
  150.     }
  151.     print("( ");
  152.     print(toPolyString(pTmpPoly, SIZE - 1));
  153.     print(" )");
  154.     free(pTmpPoly);
  155.     r = b[SIZE - 1];
  156.     if (r > 0.0) {
  157.         print(" + ");
  158.         print(simplify(r, -1));
  159.     }
  160.     else if (r < 0.0) {
  161.         print(" - ");
  162.         print(simplify(fabs(r), -1));
  163.     }
  164.     println("");
  165. }
  166. // 조립제법 계산표 출력 함수
  167. void printSyntheticTable(double a, double c[], double s[], double q[], int size) {
  168.     int SIZE = size;
  169.     int i;
  170.     print("       | ");
  171.     print(simplify(c[0], 6));
  172.     for (i = 1; i < SIZE; i++) {
  173.         print("  ");
  174.         print(simplify(c[i], 6));
  175.     }
  176.     println("");
  177.     print(simplify(a, 6));
  178.     print(" | ");
  179.     print("        ");
  180.     print(simplify(s[1], 6));
  181.     for (i = 2; i < SIZE; i++) {
  182.         print("  ");
  183.         print(simplify(s[i], 6));
  184.     }
  185.     println("");
  186.     print("       |-");
  187.     for (i = 0; i < SIZE; i++) {
  188.         print("--------");
  189.     }
  190.     println("");
  191.     print("         ");
  192.     print(simplify(q[0], 6));
  193.     for (i = 1; i < SIZE; i++) {
  194.         print("  ");
  195.         print(simplify(q[i], 6));
  196.     }
  197.     println("");
  198. }
  199. // C/C++/Ch 언어의 실행 시작 지점
  200. int main(int argc, char *argv[]) {
  201.     int i;
  202.     int SIZE = argc - 2;
  203.     double a, c[15], s[15], b[15];
  204.     if (argc < 4) {
  205.         printUsage();
  206.         exit(1);
  207.     }
  208.     //////////////////////////////////////////////////////
  209.     // 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
  210.     // 제식은 x -  a
  211.     a = atof(argv[1]);
  212.     for (i = 0; i < SIZE; i++) {
  213.         c[i] = atof(argv[i + 2]);
  214.     }
  215.     //////////////////////////////////////////////////////
  216.     // 조립제법의 주요 부분
  217.     s[0] = 0.0;
  218.     b[0] = c[0];
  219.     for (i = 1; i < SIZE; i++) {
  220.         s[i] = b[i-1]*a;
  221.         b[i] = c[i] + s[i];
  222.     }
  223.     //////////////////////////////////////////////////////
  224.     // 몫의 계수와 나머지를 출력한다.
  225.     print("몫의 계수는 ");
  226.     for (i = 0; i < SIZE - 2; i++) {
  227.         print(simplify(b[i], -1));
  228.         print(", ");
  229.     }
  230.     print(simplify(b[SIZE - 2], -1));
  231.     print(" 이고, 나머지는 ");
  232.     print(simplify(b[SIZE - 1], -1));
  233.     println(" 이다.");
  234.     println("");
  235.     //////////////////////////////////////////////////////
  236.     // 조립제법 표를 출력한다.
  237.     printSyntheticTable(a, c, s, b, SIZE);
  238.     println("");
  239.     //////////////////////////////////////////////////////
  240.     // (피제식) = (제식) x (몫) + (나머지)
  241.     printDivisionResult(a, c, b, SIZE);
  242.     return 0;
  243. }




컴파일> cl testSyntheticDivision.c

실행> testSyntheticDivision 1 2 3 4 5
몫의 계수는 2, 5, 9 이고, 나머지는 14 이다.

       |      2       3       4       5
     1 |              2       5       9
       |---------------------------------
              2       5       9      14

  2 x^3 + 3 x^2 + 4 x + 5
    = ( x - 1 )( 2 x^2 + 5 x + 9 ) + 14



 

Posted by Scripter
,