Script Programming(스크립트 프로그래밍)

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

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

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

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


아래의 소스파일은 Groovy용 소스파일 testSyntheticDivision.groovy 를 Python용으로 수정한 것이다.

python 대신 jython이나 IronPython 으로도 수정 없이 그대로 실행된다.

1. #  Filename: testSyntheticDivision.py
2. #
3. #  Purpose:  Find the quotient and remainder when some polynomial is
4. #            divided by a monic polynomial of the first degree.
5. #
6. #  Execute:  python testSyntheticDivision.py -2 1 3 3 1
7. #        Or  jython testSyntheticDivision.py -2 1 3 3 1
9. import sys
11. # 사용법 표시
12. def printUsage():
13.     print("사용법: python testSyntheticDivision.py [수] [피제식의 계수들]")
14.     print("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
16. # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
17. # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
18. def simplify(v, width=None):
19.     t = "%d" % v
20.     tlen = len(t)
21.     if t[tlen-2:tlen-1] == ".0":
22.         t = t[0, -2]
23.     if width != None:
24.         if tlen < width:
25.             t = "              "[0: width - tlen] + t
26.     return t
28. # 다항식을 내림차순의 스트링 표현으로 반환
29. def toPolyString(c):
30.     t = ""
31.     sc0 = simplify(c[0])
32.     if len(c) > 2:
33.         if sc0 == "1":
34.             t += "x^%d" % (len(c)-1)
35.         elif sc0 == "-1":
36.             t += "-x^%d" % (len(c)-1)
37.         else:
38.             t += sc0 + " x^%d" % (len(c)-1)
39.     elif len(c) == 2:
40.         if sc0 == "1":
41.             t += "x"
42.         elif sc0 == "-1":
43.             t += "-x"
44.         else:
45.             t += sc0 + " x"
46.     elif len(c) == 1:
47.         t += sc0
49.     for i in range(1, len(c)):
50.         k = len(c) - 1 - i
51.         sc = simplify(c[i])
52.         if k > 1:
53.             if c[i] > 0.0:
54.                 if sc == "1":
55.                     t += " + " + "x^%d" % k
56.                 else:
57.                     t += " + " + sc + " x^%d" % k
58.             elif c[i] < 0.0:
59.                 if sc == "-1":
60.                     t += " - " + "x^%d" % k
61.                 else:
62.                     t += " - " + simplify(abs(c[i])) + " x^%d" % k
63.         elif k == 1:
64.             if c[i] > 0.0:
65.                 if sc == "1":
66.                     t += " + " + "x"
67.                 else:
68.                     t += " + " + sc + " x"
69.             elif c[i] < 0.0:
70.                 if sc == "-1":
71.                     t += " - " + "x"
72.                 else:
73.                     t += " - " + simplify(abs(c[i])) + " x"
74.         elif k == 0:
75.             if c[i] > 0.0:
76.                 t += " + " + sc
77.             elif c[i] < 0.0:
78.                 t += " - " + simplify(abs(c[i]))
79.     return t
81. # 다항식 나눗셈 결과를
82. #     (피제식) = (제식)(몫) + (나머지)
83. # 형태로 출력
84. def printDivisionResult(a, c, b):
85.     strLine = "  " + toPolyString(c)
86.     print( strLine )
88.     strLine = "    = ( " + toPolyString( [1.0, -a] ) + " )"
89.     tmp = [0.0] * (len(b) - 1)
90.     for i in range(0, len(tmp)):
91.         tmp[i] = b[i]
92.     strLine += "( " + toPolyString(tmp) + " )"
93.     r = b[len(b) - 1]
94.     if r > 0.0:
95.         strLine += " + " + simplify(r)
96.     elif r < 0.0:
97.         strLine += " - " + simplify(abs(r))
98.     print( strLine )
100. # 조립제법 계산표 출력 함수
101. def printSyntheticTable(a, c, s, q):
102.     strLine = "       | "
103.     strLine += simplify(c[0], 6)
104.     for i in range(1, len(c)):
105.         strLine += "  " + simplify(c[i], 6)
106.     print( strLine )
108.     strLine = simplify(a, 6) + " |"
109.     strLine += "         "
110.     strLine += simplify(s[1], 6)
111.     for i in range(2, len(s)):
112.         strLine += "  " + simplify(s[i], 6)
113.     print( strLine )
115.     strLine = "       |"
116.     for i in range(0, len(q)):
117.         strLine += "--------"
118.     print( strLine )
120.     strLine = "         "
121.     strLine += simplify(q[0], 6)
122.     for i in range(1, len(q)):
123.         strLine += "  " + simplify(q[i], 6)
124.     print( strLine )
127. # 실행 시작 지점
128. if len(sys.argv) < 3:
129.     printUsage()
130.     sys.exit(1)
132. ######################################################
133. # 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
134. # 제식은 x -  a
135. a = float(sys.argv[1])
136. c = [0.0]*(len(sys.argv) - 2)
137. s = [0.0]*(len(sys.argv) - 2)
138. b = [0.0]*(len(sys.argv) - 2)
140. for i in range(0, len(c)):
141.     c[i] = float(sys.argv[i + 2])
143. ######################################################
144. # 조립제법의 주요 부분
145. s[0] = 0.0
146. b[0] = c[0]
147. for i in range(1, len(c)):
148.     s[i] = b[i-1]*a
149.     b[i] = c[i] + s[i]
151. ######################################################
152. # 몫의 계수와 나머지를 출력한다.
153. print("몫의 계수는"),
154. for i in range(0, len(b) - 2):
155.     print(simplify(b[i], None) + ", " ),
156. print(simplify(b[len(b) - 2], None)),
157. print("이고, 나머지는 " + simplify(b[len(b) - 1], None) + " 이다.")
158. print
160. ######################################################
161. # 조립제법 표를 출력한다.
162. printSyntheticTable(a, c, s, b)
163. print
165. ######################################################
166. # (피제식) = (제식) x (몫) + (나머지)
167. printDivisionResult(a, c, b)

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

다항식 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 대한민국 라이센스에 따라 이용하실 수 있습니다.