다항식 p(x) 를 1차 다항식 x - a 로 나눌 때의 몫과 나머지를 구하는 조립제법을
Java 언어로 구현해 보았다. 조립제법은 일명 Horner의 방법이라고도 불리우는데, 이는
x = a 에서 다항식 p(x)의 값 p(a)을 계산하는 가장 빠른 알고리즘이기도 하다.
p(x) = (x - a)q(x) + r
여기서 r은 나머지이며 r = p(a) 이다. 또 q(x)는 몫이다.
[참고]
* 온라인으로 조립제법 표 만들기 손으로 계산하는 조립제법 표
* 온라인으로 구하는 다항식의 도함수: 조립제법을 이용한 다항식의 도함수
- /*
- * Filename: TestSyntheticMethod.java
- *
- * Purpose: Find the quotient and remainder when some polynomial is
- * divided by a monic polynomial of the first degree.
- *
- * Compile: javac -d . TestSyntheticMethod.java
- *
- * Execute: java TestSyntheticMethod -2 1 3 3 1
- */
- import java.lang.Math;
- public class TestSyntheticMethod {
- // 사용법 표시
- public static void printUsage() {
- System.out.println("사용법: java TestSyntheticMethod [수] [피제식의 계수들]");
- System.out.println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.");
- }
- // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
- public static String simplify(double v) {
- String t = "" + v;
- if (t.endsWith(".0"))
- t = t.substring(0, t.length() - 2);
- return t;
- }
- // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
- // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
- public static String simplify(double v, int width) {
- String t = "" + v;
- if (t.endsWith(".0"))
- t = t.substring(0, t.length() - 2);
- int len = t.length();
- if (len < width)
- t = " ".substring(0, width - len) + t;
- return t;
- }
- // 다항식을 내림차순의 스트링 표현으로 반환
- public static String toPolyString(double[] c) {
- String t = "";
- if (c.length > 2) {
- if (simplify(c[0]).equals("1"))
- t += "x^" + (c.length-1);
- else if (simplify(c[0]).equals("-1"))
- t += "-x^" + (c.length-1);
- else
- t += simplify(c[0]) + " x^" + (c.length-1);
- }
- else if (c.length == 2) {
- if (simplify(c[0]).equals("1"))
- t += "x";
- else if (simplify(c[0]).equals("-1"))
- t += "-x";
- else
- t += simplify(c[0]) + " x";
- }
- else if (c.length == 1) {
- t += simplify(c[0]);
- }
- for (int i = 1; i < c.length; i++) {
- if (c.length - 1 - i > 1) {
- if (c[i] > 0.0) {
- if (simplify(c[i]).equals("1"))
- t += " + " + "x^" + (c.length - 1 - i);
- else
- t += " + " + simplify(c[i]) + " x^" + (c.length - 1 - i);
- }
- else if (c[i] < 0.0) {
- if (simplify(c[i]).equals("-1"))
- t += " - " + "x^" + (c.length - 1 - i);
- else
- t += " - " + simplify(Math.abs(c[i])) + " x^" + (c.length - 1 - i);
- }
- }
- else if (c.length - 1 - i == 1) {
- if (c[i] > 0.0) {
- if (simplify(c[i]).equals("1"))
- t += " + " + "x";
- else
- t += " + " + simplify(c[i]) + " x";
- }
- else if (c[i] < 0.0) {
- if (simplify(c[i]).equals("-1"))
- t += " - " + "x";
- else
- t += " - " + simplify(Math.abs(c[i])) + " x";
- }
- }
- else if (c.length - 1 - i == 0) {
- if (c[i] > 0.0) {
- t += " + " + simplify(c[i]);
- }
- else if (c[i] < 0.0)
- t += " - " + simplify(Math.abs(c[i]));
- }
- }
- return t;
- }
- // 다항식 나눗셈 결과를
- // (피제식) = (제식)(몫) + (나마지)
- // 형태로 출력
- public static void printDivisionResult(double a, double[] c, double[] b) {
- System.out.print(" " + toPolyString(c));
- System.out.println();
- System.out.print(" = ( " + toPolyString( new double[] {1.0, -a} ) + " )");
- double[] tmp = new double[b.length - 1];
- for (int i = 0; i < tmp.length; i++) {
- tmp[i] = b[i];
- }
- System.out.print("( " + toPolyString(tmp) + " )");
- double r = b[b.length - 1];
- if (r > 0.0)
- System.out.print(" + " + simplify(r));
- else if (r < 0.0)
- System.out.print(" - " + simplify(Math.abs(r)));
- System.out.println();
- }
- // 조립제법 계산표 출력 메소드
- public static void printSyntheticTable(double a, double[] c, double[] s, double[] q) {
- System.out.print(" | ");
- System.out.print(simplify(c[0], 6));
- for (int i = 1; i < c.length; i++) {
- System.out.print(" " + simplify(c[i], 6));
- }
- System.out.println();
- System.out.print(simplify(a, 6) + " | ");
- System.out.print(" ");
- System.out.print(simplify(s[1], 6));
- for (int i = 2; i < s.length; i++) {
- System.out.print(" " + simplify(s[i], 6));
- }
- System.out.println();
- System.out.print(" |-");
- for (int i = 0; i < q.length; i++) {
- System.out.print("--------");
- }
- System.out.println("");
- System.out.print(" ");
- System.out.print(simplify(q[0], 6));
- for (int i = 1; i < q.length; i++) {
- System.out.print(" " + simplify(q[i], 6));
- }
- System.out.println();
- }
- // Java 애플리케이션의 실행 시작 시점 main 메소드
- // (C 언어의 main 함수에 해당)
- public static void main(String[] args) {
- if (args.length < 3) {
- printUsage();
- System.exit(1);
- }
- //////////////////////////////////////////////////////
- // 피제식은 c_0 x^n + c_1 x^(n -1) + ... + c_n
- // 제식은 x - a
- double a = Double.parseDouble(args[0]);
- double[] c = new double[args.length - 1];
- double[] s = new double[c.length];
- double[] b = new double[c.length];
- for (int i = 0; i < c.length; i++) {
- c[i] = Double.parseDouble(args[i + 1]);
- }
- //////////////////////////////////////////////////////
- // 조립제법의 주요 부분
- s[0] = 0.0;
- b[0] = c[0];
- for (int i = 1; i < c.length; i++) {
- s[i] = b[i-1]*a;
- b[i] = c[i] + s[i];
- }
- //////////////////////////////////////////////////////
- // 몫의 계수와 나머지를 출력한다.
- System.out.print("몫의 계수는 ");
- for (int i = 0; i < b.length - 2; i++) {
- System.out.print(simplify(b[i]) + ", " );
- }
- System.out.print(simplify(b[b.length - 2]));
- System.out.println(" 이고, 나머지는 " + simplify(b[b.length - 1]) + " 이다.");
- System.out.println();
- //////////////////////////////////////////////////////
- // 조립제법 표를 출력한다.
- printSyntheticTable(a, c, s, b);
- System.out.println();
- //////////////////////////////////////////////////////
- // (피제식) = (제식) x (몫) + (나머지)
- printDivisionResult(a, c, b);
- }
- }
컴파일> javac -d . TestSyntheticMethod.java
실행> java TestSyntheticMethod 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 대한민국 라이센스에 따라 이용하실 수 있습니다.
'프로그래밍 > Java' 카테고리의 다른 글
| 황금비율(golden ratio) 구하기 with Java (0) | 2008.03.24 |
|---|---|
| 현재 시각 알아내기 for Java (0) | 2008.03.24 |
| 80컬럼 컨솔에 19단표 출력하기 예제 for Java (0) | 2008.03.03 |
| (최대공약수 구하기) while... 반복문 예제 for Java (0) | 2008.02.20 |
| if...else... 조건문 사용 예제 for Java (0) | 2008.02.19 |
