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

프로그래밍/Java 2008. 3. 13. 22:25

다항식 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