다항식 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 을 클릭한다.
- /*
- * Filename: testSyntheticDivisionMain.m
- *
- * Purpose: Find the quotient and remainder when some polynomial is
- * divided by a monic polynomial of the first degree.
- *
- * Compile: Click Ctr;+F11 on Dec-C++
- *
- * Execute: testSyntheticDivision -2 1 3 3 1
- */
- #import <Foundation/Foundation.h>
- #import <stdio.h>
- #import <string.h>
- #import <math.h>
- #import <memory.h>
- void print(char str[]) {
- printf("%s", str);
- }
- void println(char str[]) {
- printf("%s\n", str);
- }
- // 사용법 표시
- void printUsage() {
- println("사용법: testSyntheticDivision [수] [피제식의 계수들]");
- println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.");
- }
- // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
- // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
- char *simplify(double v, int width) {
- int n, len;
- static char t[] = " ";
- char tmp[] = " ";
- sprintf(t, "%g", v);
- n = strlen(t);
- if ((n > 2) && (t[n - 2] == '.') && (t[n - 1] == '0'))
- t[n-2] = '\0';
- len = strlen(t);
- strcpy(tmp, t);
- if (len < width) {
- strncpy(t, " ", width - len);
- t[width - len] = '\0';
- strcat(t, tmp);
- }
- return (char *) t;
- }
- // 다항식을 내림차순의 문자열로 반환하는 함수
- // 반환된 문자열은 동적 메모리에 존재하므로.
- // 사용 후 반드시 해제(free)하여야 한다.
- char *toPolyString(double c[], int size) {
- int SIZE = size;
- int i;
- static char t[300];
- char tmp[80];
- char *pc = simplify(c[0], -1);
- char *pci;
- if (SIZE > 2) {
- if (strlen(pc) == 1 && pc[0] == '1')
- sprintf(t, "x^%d", SIZE - 1);
- else if (strlen(pc) == 2 && pc[0] == '-' && pc[1] == '1')
- sprintf(t, "-x^%d", SIZE - 1);
- else
- sprintf(t, "%s x^%d", simplify(c[0], -1), SIZE - 1);
- }
- else if (SIZE == 2) {
- if (strlen(pc) == 1 && pc[0] == '1')
- strcpy(t, "x");
- else if (strlen(pc) == 2 && pc[0] == '-' && pc[1] == '1')
- strcpy(t, "-x");
- else
- sprintf(t, "%s x", simplify(c[0], -1));
- }
- else if (SIZE == 1) {
- sprintf(t, "%s", simplify(c[0], -1));
- }
- for (i = 1; i < SIZE; i++) {
- pci = simplify(c[i], -1);
- if (SIZE - 1 - i > 1) {
- if (c[i] > 0.0) {
- if (strlen(pci) == 1 && pci[0] == '1') {
- sprintf(tmp, " + x^%d", SIZE - 1 - i);
- strcat(t, tmp);
- }
- else {
- sprintf(tmp, " + %s x^%d", simplify(c[i], -1), SIZE - 1 - i);
- strcat(t, tmp);
- }
- }
- else if (c[i] < 0.0) {
- if (strlen(pci) == 2 && pci[0] == '-' && pci[1] == '1') {
- sprintf(tmp, " - x^%d", SIZE - 1 - i);
- strcat(t, tmp);
- }
- else {
- sprintf(tmp, " - %s x^%d", simplify(fabs(c[i]), -1), SIZE - 1 - i);
- strcat(t, tmp);
- }
- }
- }
- else if (SIZE - 1 - i == 1) {
- if (c[i] > 0.0) {
- if (strlen(pci) == 1 && pci[0] == '1') {
- strcat(t, " + x");
- }
- else {
- sprintf(tmp, " + %s x", simplify(c[i], -1));
- strcat(t, tmp);
- }
- }
- else if (c[i] < 0.0) {
- if (strlen(pci) == 2 && pci[0] == '-' && pci[1] == '1') {
- strcat(t, " - x");
- }
- else {
- sprintf(tmp, " - %s x", simplify(fabs(c[i]), -1));
- strcat(t, tmp);
- }
- }
- }
- else if (SIZE - 1 - i == 0) {
- if (c[i] > 0.0) {
- sprintf(tmp, " + %s", simplify(c[i], -1));
- strcat(t, tmp);
- }
- else if (c[i] < 0.0) {
- sprintf(tmp, " - %s", simplify(fabs(c[i]), -1));
- strcat(t, tmp);
- }
- }
- }
- return (char *) t;
- }
- // 다향식 나눗셈 결과를
- // (피제식) = (제식)(몫) + (나마지)
- // 형태로 출력
- void printDivisionResult(double a, double c[], double b[], int size) {
- int SIZE = size;
- int i;
- double *pTmpPoly;
- double r;
- double monic[] = { 1.0, 0.0 };
- print(" ");
- print(toPolyString(c, SIZE));
- println("");
- print(" = ( ");
- monic[1] = -a;
- print(toPolyString( monic, 2 ));
- print(" )");
- pTmpPoly = (double *) calloc(SIZE - 1, sizeof(double));
- for (i = 0; i < SIZE - 1; i++) {
- pTmpPoly[i] = b[i];
- }
- print("( ");
- print(toPolyString(pTmpPoly, SIZE - 1));
- print(" )");
- free(pTmpPoly);
- r = b[SIZE - 1];
- if (r > 0.0) {
- print(" + ");
- print(simplify(r, -1));
- }
- else if (r < 0.0) {
- print(" - ");
- print(simplify(fabs(r), -1));
- }
- println("");
- }
- // 조립제법 계산표 출력 함수
- void printSyntheticTable(double a, double c[], double s[], double q[], int size) {
- int SIZE = size;
- int i;
- print(" | ");
- print(simplify(c[0], 6));
- for (i = 1; i < SIZE; i++) {
- print(" ");
- print(simplify(c[i], 6));
- }
- println("");
- print(simplify(a, 6));
- print(" | ");
- print(" ");
- print(simplify(s[1], 6));
- for (i = 2; i < SIZE; i++) {
- print(" ");
- print(simplify(s[i], 6));
- }
- println("");
- print(" |-");
- for (i = 0; i < SIZE; i++) {
- print("--------");
- }
- println("");
- print(" ");
- print(simplify(q[0], 6));
- for (i = 1; i < SIZE; i++) {
- print(" ");
- print(simplify(q[i], 6));
- }
- println("");
- }
- // C/C++/Ch/Objective-C 언어의 실행 시작 지점
- int main(int argc, char *argv[]) {
- int i;
- int SIZE = argc - 2;
- double a, c[15], s[15], b[15];
- if (argc < 4) {
- printUsage();
- exit(1);
- }
- //////////////////////////////////////////////////////
- // 피제식은 c_0 x^n + c_1 x^(n -1) + ... + c_n
- // 제식은 x - a
- a = atof(argv[1]);
- for (i = 0; i < SIZE; i++) {
- c[i] = atof(argv[i + 2]);
- }
- //////////////////////////////////////////////////////
- // 조립제법의 주요 부분
- s[0] = 0.0;
- b[0] = c[0];
- for (i = 1; i < SIZE; i++) {
- s[i] = b[i-1]*a;
- b[i] = c[i] + s[i];
- }
- //////////////////////////////////////////////////////
- // 몫의 계수와 나머지를 출력한다.
- print("몫의 계수는 ");
- for (i = 0; i < SIZE - 2; i++) {
- print(simplify(b[i], -1));
- print(", ");
- }
- print(simplify(b[SIZE - 2], -1));
- print(" 이고, 나머지는 ");
- print(simplify(b[SIZE - 1], -1));
- println(" 이다.");
- println("");
- //////////////////////////////////////////////////////
- // 조립제법 표를 출력한다.
- printSyntheticTable(a, c, s, b, SIZE);
- println("");
- //////////////////////////////////////////////////////
- // (피제식) = (제식) x (몫) + (나머지)
- printDivisionResult(a, c, b, SIZE);
- return 0;
- }
컴파일은 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
'프로그래밍 > Objective-C' 카테고리의 다른 글
황금비율(golden ratio) 구하기 with Objective-C (0) | 2012.04.30 |
---|---|
현재 시각 알아내기 for Objective-C (0) | 2012.04.30 |
80컬럼 컨솔에 19단표 출력하기 예제 for Objective-C (0) | 2012.04.30 |
(최대공약수 구하기) while... 반복문 예제 for Objective-C (0) | 2012.04.30 |
if...else... 조건문 사용 예제 for Objective-C (0) | 2012.04.29 |