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

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

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


  1. /*
  2.  *  Filename: TestSyntheticMethod.groovy
  3.  *
  4.  *  Purpose:  Find the quotient and remainder when some polynomial is
  5.  *                 divided by a monic polynomial of the first degree.
  6.  *     이 소스는 자바소스 TestSyntheticMethod.java 에서 배열 생성 부분
  7.  *     new double[] {1.0, -a} 을 [1.0, -a] as double[] 로 변경한 것만 다르다.
  8.  *
  9.  *  Execute: groovy TestSyntheticMethod.groovy -2 1 3 3 1
  10.  */
  11. import java.lang.Math;
  12. public class TestSyntheticMethod {
  13.     // 사용법 표시
  14.     public static void printUsage() {
  15.          System.out.println("사용법: java TestSyntheticMethod [수] [피제식의 계수들]");
  16.          System.out.println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.");
  17.     }
  18.     // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
  19.     public static String simplify(double v) {
  20.         String t = "" + v;
  21.         if (t.endsWith(".0"))
  22.             t = t.substring(0, t.length() - 2);
  23.         return t;
  24.     }
  25.     // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
  26.     // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
  27.     public static String simplify(double v, int width) {
  28.         String t = "" + v;
  29.         if (t.endsWith(".0"))
  30.             t = t.substring(0, t.length() - 2);
  31.         int len = t.length();
  32.         if (len < width)
  33.             t = "               ".substring(0, width - len) + t;
  34.         return t;
  35.     }
  36.     // 다항식을 내림차순의 스트링 표현으로 반환
  37.     public static String toPolyString(double[] c) {
  38.         String t = "";
  39.         if (c.length > 2) {
  40.             if (simplify(c[0]).equals("1"))
  41.                 t += "x^" + (c.length-1);
  42.             else if (simplify(c[0]).equals("-1"))
  43.                 t += "-x^" + (c.length-1);
  44.             else
  45.                 t += simplify(c[0]) + " x^" + (c.length-1);
  46.         }
  47.         else if (c.length == 2) {
  48.             if (simplify(c[0]).equals("1"))
  49.                 t += "x";
  50.             else if (simplify(c[0]).equals("-1"))
  51.                 t += "-x";
  52.             else
  53.                 t += simplify(c[0]) + " x";
  54.         }
  55.         else if (c.length == 1) {
  56.             t += simplify(c[0]);
  57.         }
  58.         for (int i = 1; i < c.length; i++) {
  59.             if (c.length - 1 - i > 1) {
  60.                 if (c[i] > 0.0) {
  61.                     if (simplify(c[i]).equals("1"))
  62.                         t += " + " + "x^" + (c.length - 1 - i);
  63.                     else
  64.                         t += " + " + simplify(c[i]) + " x^" + (c.length - 1 - i);
  65.                 }
  66.                 else if (c[i] < 0.0) {
  67.                     if (simplify(c[i]).equals("-1"))
  68.                         t += " - " + "x^" + (c.length - 1 - i);
  69.                     else
  70.                         t += " - " + simplify(Math.abs(c[i])) + " x^" + (c.length - 1 - i);
  71.                 }
  72.             }
  73.             else if (c.length - 1 - i == 1) {
  74.                 if (c[i] > 0.0) {
  75.                     if (simplify(c[i]).equals("1"))
  76.                         t += " + " + "x";
  77.                     else
  78.                         t += " + " + simplify(c[i]) + " x";
  79.             }
  80.             else if (c[i] < 0.0) {
  81.                 if (simplify(c[i]).equals("-1"))
  82.                     t += " - " + "x";
  83.                 else
  84.                     t += " - " + simplify(Math.abs(c[i])) + " x";
  85.             }
  86.         }
  87.         else if (c.length - 1 - i == 0) {
  88.             if (c[i] > 0.0) {
  89.                 t += " + " + simplify(c[i]);
  90.             }
  91.             else if (c[i] < 0.0)
  92.                 t += " - " + simplify(Math.abs(c[i]));
  93.             }
  94.         }
  95.         return t;
  96.     }
  97.     // 다항식 나눗셈 결과를
  98.     //     (피제식) = (제식)(몫) + (나마지)
  99.     // 형태로 출력
  100.     public static void printDivisionResult(double a, double[] c, double[] b) {
  101.         System.out.print("  " + toPolyString(c));
  102.         System.out.println();
  103.         System.out.print("    = ( " + toPolyString( [1.0, -a] as double[] ) + " )");
  104.         double[] tmp = new double[b.length - 1];
  105.         for (int i = 0; i < tmp.length; i++) {
  106.             tmp[i] = b[i];
  107.         }
  108.         System.out.print("( " + toPolyString(tmp) + " )");
  109.         double r = b[b.length - 1];
  110.         if (r > 0.0)
  111.             System.out.print(" + " + simplify(r));
  112.         else if (r < 0.0)
  113.             System.out.print(" - " + simplify(Math.abs(r)));
  114.         System.out.println();
  115.     }
  116.     // 조립제법 계산표 출력 메소드
  117.     public static void printSyntheticTable(double a, double[] c, double[] s, double[] q) {
  118.         System.out.print("       | ");
  119.         System.out.print(simplify(c[0], 6));
  120.         for (int i = 1; i < c.length; i++) {
  121.             System.out.print("  " + simplify(c[i], 6));
  122.         }
  123.         System.out.println();
  124.         System.out.print(simplify(a, 6) + " | ");
  125.         System.out.print("        ");
  126.         System.out.print(simplify(s[1], 6));
  127.         for (int i = 2; i < s.length; i++) {
  128.             System.out.print("  " + simplify(s[i], 6));
  129.         }
  130.         System.out.println();
  131.         System.out.print("       |-");
  132.         for (int i = 0; i < q.length; i++) {
  133.             System.out.print("--------");
  134.         }
  135.         System.out.println("");
  136.         System.out.print("         ");
  137.         System.out.print(simplify(q[0], 6));
  138.         for (int i = 1; i < q.length; i++) {
  139.             System.out.print("  " + simplify(q[i], 6));
  140.         }
  141.         System.out.println();
  142.     }
  143.     // Java 애플리케이션의 실행 시작 시점 main 메소드
  144.     // (C 언어의 main 함수에 해당)
  145.     public static void main(String[] args) {
  146.         if (args.length < 3) {
  147.             printUsage();
  148.             System.exit(1);
  149.         }
  150.         //////////////////////////////////////////////////////
  151.         // 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
  152.         // 제식은 x -  a
  153.         double a = Double.parseDouble(args[0]);
  154.         double[] c = new double[args.length - 1];
  155.         double[] s = new double[c.length];
  156.         double[] b = new double[c.length];
  157.         for (int i = 0; i < c.length; i++) {
  158.             c[i] = Double.parseDouble(args[i + 1]);
  159.         }
  160.         //////////////////////////////////////////////////////
  161.         // 조립제법의 주요 부분
  162.         s[0] = 0.0;
  163.         b[0] = c[0];
  164.         for (int i = 1; i < c.length; i++) {
  165.            s[i] = b[i-1]*a;
  166.             b[i] = c[i] + s[i];
  167.         }
  168.         //////////////////////////////////////////////////////
  169.         // 몫의 계수와 나머지를 출력한다.
  170.         System.out.print("몫의 계수는 ");
  171.         for (int i = 0; i < b.length - 2; i++) {
  172.             System.out.print(simplify(b[i]) + ", " );
  173.         }
  174.         System.out.print(simplify(b[b.length - 2]));
  175.         System.out.println(" 이고, 나머지는 " + simplify(b[b.length - 1]) + " 이다.");
  176.         System.out.println();
  177.         //////////////////////////////////////////////////////
  178.         // 조립제법 표를 출력한다.
  179.         printSyntheticTable(a, c, s, b);
  180.         System.out.println();
  181.         //////////////////////////////////////////////////////
  182.         // (피제식) = (제식) x (몫) + (나머지)
  183.         printDivisionResult(a, c, b);
  184.     }
  185. }



Groovy 언어로 작성된 소스파일은 groovyc 명형으로 컴파일한 후 , 컴파일된 .class 파일을 java 명령으로 실행해도 되지만, groovy 명령을 사용하여 (아래에서 처험) 컴파일 과정 없이 직접 소스파일을 실행시킬 수 있다.


실행> groovy TestSyntheticMethod.groovy 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


Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
Posted by Scripter
,