조립제법(Horner의 방법) 예제 for Boo

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

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

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

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


아래의 소스파일은 Python용 소스파일 testSyntheticDivision.py를 Boo용으로 수정한 것이다.
소스파일을 저장할 때는 UTF-8 인코딩으로 저장해야 한다.

Boo  언어는 그 구문의 바탕을 Python 언어의 것에서 빌렸다.
그러나 Python 언어는 변수의 타입이 런타임시에 결정되는 동적 타입(dynamically typed) 언어이지만, Boo 언어는 변수의 타입이 컴파일시에 결정되는 정적 타입(statically typed) 언어라는 점에서 차이점이 있다.

      (1) 함수를 구현할 때 매개변수의 타입을 지정해야 한다.
      (2) 변수 선언시에 타입을 지정해야 하는 경우가 많다.
      (3) 리스트에서 가져온 데이터의 타입을 다시 지정해야 한다.

1. #  Filename: testSyntheticDivision.boo
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:  booi testSyntheticDivision.boo -2 1 3 3 1
8. import System
10. # 사용법 표시
11. def printUsage():
12.     print("사용법: booi testSyntheticDivision.boo [수] [피제식의 계수들]")
13.     print("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
15. # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
16. # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
17. def simplify(v as double, width as int):
18.     t = "${v}"
19.     tlen = len(t)
20.     if t[tlen-2:tlen-1] == ".0":
21.         t = t[0:-2]
22.     if width > 0:
23.         if tlen < width:
24.             t = "              "[0: width - tlen] + t
25.     return t
27. # 다항식을 내림차순의 스트링 표현으로 반환
28. def toPolyString(c as List):
29.     t = ""
30.     sc0 = simplify(Convert.ToDouble(c[0]), -1)
31.     if len(c) > 2:
32.         if sc0 == "1":
33.             t += "x^${len(c)-1}"
34.         elif sc0 == "-1":
35.             t += "-x^${len(c)-1}"
36.         else:
37.             t += sc0 + " x^${len(c)-1}"
38.     elif len(c) == 2:
39.         if sc0 == "1":
40.             t += "x"
41.         elif sc0 == "-1":
42.             t += "-x"
43.         else:
44.             t += sc0 + " x"
45.     elif len(c) == 1:
46.         t += sc0
48.     for i in range(1, len(c)):
49.         k = len(c) - 1 - i
50.         sc = simplify(Convert.ToDouble(c[i]), -1)
51.         if k > 1:
52.             if Convert.ToDouble(c[i]) > 0.0:
53.                 if sc == "1":
54.                     t += " + " + "x^${k}"
55.                 else:
56.                     t += " + " + sc + " x^${k}"
57.             elif Convert.ToDouble(c[i]) < 0.0:
58.                 if sc == "-1":
59.                     t += " - " + "x^${k}"
60.                 else:
61.                     t += " - " + simplify(Math.Abs(Convert.ToDouble(c[i])), -1) + " x^${k}"
62.         elif k == 1:
63.             if Convert.ToDouble(c[i]) > 0.0:
64.                 if sc == "1":
65.                     t += " + " + "x"
66.                 else:
67.                     t += " + " + sc + " x"
68.             elif Convert.ToDouble(c[i]) < 0.0:
69.                 if sc == "-1":
70.                     t += " - " + "x"
71.                 else:
72.                     t += " - " + simplify(Math.Abs(Convert.ToDouble(c[i])), -1) + " x"
73.         elif k == 0:
74.             if Convert.ToDouble(c[i]) > 0.0:
75.                 t += " + " + sc
76.             elif Convert.ToDouble(c[i]) < 0.0:
77.                 t += " - " + simplify(Math.Abs(Convert.ToDouble(c[i])), -1)
78.     return t
80. # 다향식 나눗셈 결과를
81. #     (피제식) = (제식)(몫) + (나마지)
82. # 형태로 출력
83. def printDivisionResult(a as double, c as List, b as List):
84.     strLine = "  " + toPolyString(c)
85.     print( strLine )
87.     strLine = "    = ( " + toPolyString( [1.0, -a] ) + " )"
88.     tmp = [0.0] * (len(b) - 1)
89.     for i in range(0, len(tmp)):
90.         tmp[i] = b[i]
91.     strLine += "( " + toPolyString(tmp) + " )"
93.     r as double = b[len(b) - 1]
94.     if r > 0.0:
95.         strLine += " + " + simplify(r, -1)
96.     elif r < 0.0:
97.         strLine += " - " + simplify(Math.Abs(r), -1)
98.     print( strLine )
100. # 조립제법 계산표 출력 함수
101. def printSyntheticTable(a, c as List, s as List, q as List):
102.     strLine = "       | "
103.     strLine += simplify(c[0], 6)
104.     for i in range(1, len(c)):
105.         strLine += "  " + simplify(c[i], 6)
107.     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(Convert.ToDouble(q[0]), 6)
122.     for i in range(1, len(q)):
123.         strLine += "  " + simplify(Convert.ToDouble(q[i]), 6)
124.     print( strLine )
126. def write(s):
127.     Console.Write(s)
130. # 실행 시작 지점
131. if len(argv) < 2:
132.     printUsage()
133.     Environment.Exit(1)
135. ######################################################
136. # 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
137. # 제식은 x -  a 
138.  as double = Convert.ToDouble(argv[0])
139. c as List = [0.0]*(len(argv) - 1)
140. s as List = [0.0]*(len(argv) - 1)
141. b as List = [0.0]*(len(argv) - 1)
143. for i in range(0, len(c)):
144.     c[i] = Convert.ToDouble(argv[i + 1])
146. ######################################################
147. # 조립제법의 주요 부분
148. s[0] = 0.0
149. b[0] = c[0]
150. for i in range(1, len(c)):
151.     s[i] = Convert.ToInt32(b[i-1])*a
152.     b[i] = Convert.ToInt32(c[i]) + Convert.ToInt32(s[i])
154. ######################################################
155. # 몫의 계수와 나머지를 출력한다.
156. write("몫의 계수는 ")
157. for i in range(0, len(b) - 2):
158.     write(simplify(b[i], -1) + ", ")
159. write(simplify(b[len(b) - 2], -1))
160. write(" 이고, 나머지는 " + simplify(b[len(b) - 1], -1) + " 이다.")
161. print
162. print
164. ######################################################
165. # 조립제법 표를 출력한다.
166. printSyntheticTable(a, c, s, b)
167. print
169. ######################################################
170. # (피제식) = (제식) x (몫) + (나머지)
171. printDivisionResult(a, c, b)

실행> booi testSyntheticDivision.boo 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 대한민국 라이선스에 따라 이용하실 수 있습니다.