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

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

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

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

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


아래의 소스파일은 C  언어용으로 민들어 두었던 소스 조립제법(Horner의 방법) 예제 for C and Ch 를 아주 조금 수정한 것이다. 수정한 부분은 #include를 #import로 바꾸고, 또

        #import  <Foundation/Foundation.h>

를 추가했을 뿐이다. 만일 Foundation.h 를 수입(import)하지 않으면, calloc, free, atof, exit 에러가 발생한다.

컴파일은 Dev-C++ 개발 도구에서 Ctrl+F11 을 클릭한다.

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

컴파일은 Dev-C++ 에서 Ctrl+F11 클릭

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