조립제법(Horner의 방법) 예제 (2) for Groovy

다항식 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: testSyntheticDivision.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.  *    그루비 소스 TestSyntheticMethod.groovy 를 더욱 그루비 소스 코드 답게 수정한 것이다.
8.  *
9.  *  Execute: groovy testSyntheticDivision.groovy -2 1 3 3 1
10.  *
11.  */
13. // 사용법 표시
14. def printUsage() {
15.      println("사용법: groovy testSyntheticDivision.groovy [수] [피제식의 계수들]")
16.      println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
17. }
19. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
20. String simplify(double v) {
21.     String t = "" + v
22.     if (t.endsWith(".0"))
23.         t = t[0..<(t.length() - 2)]
24.     return t
25. }
27. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
28. // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
29. String simplify(double v, int width) {
30.     String t = "" + v
31.     if (t.endsWith(".0"))
32.         t = t[0..<(t.length() - 2)]
33.     int len = t.length()
34.     if (len < width)
35.         t = "               ".substring(0, width - len) + t
36.     return t;
37. }
39. // 다항식을 내림차순의 스트링 표현으로 반환
40. String toPolyString(double[] c) {
41.     String t = ""
42.     def sc0 = simplify(c[0])
43.     if (c.length > 2) {
44.         if (sc0 == "1")
45.             t += "x^" + (c.length-1)
46.         else if (sc0 == "-1")
47.             t += "-x^" + (c.length-1)
48.         else
49.             t += sc0 + " x^" + (c.length-1)
50.     }
51.     else if (c.length == 2) {
52.         if (sc0 == "1")
53.             t += "x"
54.         else if (sc0 == "-1")
55.             t += "-x"
56.         else
57.             t += sc0 + " x"
58.     }
59.     else if (c.length == 1) {
60.         t += sc0
61.     }
63.     for (i in 1..< c.length) {
64.         def k = c.length - 1 - i
65.         def sc = simplify(c[i])
66.         if (k > 1) {
67.             if (c[i] > 0.0) {
68.                 if (sc == "1")
69.                     t += " + " + "x^" + k
70.                 else
71.                     t += " + " + sc + " x^" + k
72.             }
73.             else if (c[i] < 0.0) {
74.                 if (sc == "-1")
75.                     t += " - " + "x^" + k
76.                 else
77.                     t += " - " + simplify(Math.abs(c[i])) + " x^" + k
78.             }
79.         }
80.         else if (k == 1) {
81.             if (c[i] > 0.0) {
82.                 if (sc == "1")
83.                     t += " + " + "x"
84.                 else
85.                     t += " + " + sc + " x"
86.             }
87.             else if (c[i] < 0.0) {
88.                 if (sc == "-1")
89.                     t += " - " + "x"
90.                 else
91.                     t += " - " + simplify(Math.abs(c[i])) + " x"
92.             }
93.         }
94.         else if (k == 0) {
95.             if (c[i] > 0.0) {
96.                 t += " + " + sc
97.             }
98.             else if (c[i] < 0.0)
99.                 t += " - " + simplify(Math.abs(c[i]))
100.         }
101.     }
102.     return t
103. }
105. // 다항식 나눗셈 결과를
106. //     (피제식) = (제식)(몫) + (나마지)
107. // 형태로 출력
108. def printDivisionResult(double a, double[] c, double[] b) {
109.     print("  " + toPolyString(c))
110.     println()
112.     print("    = ( " + toPolyString( [1.0, -a] as double[] ) + " )")
113.     double[] tmp = new double[b.length - 1]
114.     for (i in 0..<tmp.length) {
115.         tmp[i] = b[i]
116.     }
117.     print("( " + toPolyString(tmp) + " )")
118.     double r = b[b.length - 1]
119.     if (r > 0.0)
120.         print(" + " + simplify(r))
121.     else if (r < 0.0)
122.         print(" - " + simplify(Math.abs(r)))
123.     println()
124. }
126. // 조립제법 계산표 출력 함수
127. def printSyntheticTable(double a, double[] c, double[] s, double[] q) {
128.     print("       | ")
129.     print(simplify(c[0], 6))
130.     for (i in 1..< c.length) {
131.         print("  " + simplify(c[i], 6))
132.     }
133.     println()
135.     print(simplify(a, 6) + " | ")
136.     print("        ")
137.     print(simplify(s[1], 6))
138.     for (i in 2..< s.length) {
139.         print("  " + simplify(s[i], 6))
140.     }
141.     println()
143.     print("       |-")
144.     for (i in 0..< q.length) {
145.         print("--------")
146.     }
147.     println()
149.     print("         ")
150.     print(simplify(q[0], 6))
151.     for (i in 1..< q.length) {
152.         print("  " + simplify(q[i], 6))
153.     }
154.     println()
155. }
157. // 실행 시작 지점
158. if (args.length < 3) {
159.     printUsage()
160.     System.exit(1);
161. }
163. double a = Double.parseDouble(args[0])
164. double[] c = new double[args.length - 1]
165. double[] s = new double[c.length]
166. double[] b = new double[c.length]
167. for (i in 0..<c.length) {
168.     c[i] = Double.parseDouble(args[i + 1])
169. }
171. s[0] = 0.0;
172. b[0] = c[0];
173. for (i in 1..<c.length) {
174.     s[i] = b[i-1]*a
175.  b[i] = c[i] + s[i]
176. }
178. print("몫의 계수는 ");
179. for (i in 0..<(b.length - 2)) {
180.     print(simplify(b[i]) + ", " )
181. }
183. print(simplify(b[b.length - 2]))
184. println(" 이고, 나머지는 " + simplify(b[b.length - 1]) + " 이다.")
185. println()
187. printSyntheticTable(a, c, s, b)
188. println()
190. printDivisionResult(a, c, b)

groovy 명령으로 아래와 같이 실행하여 보았다.


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

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