조립제법(Horner의 방법) 예제 for C++

다항식 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)는 몫이다.

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

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

컴파일> cl -EHsc testSyntheticDivisionCPP.cpp

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