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

프로그래밍/C# 2009. 1. 16. 13:18

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

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

/*
* Filename: TestSyntheticMethod.cs
*
* Purpose: Find the quotient and remainder when some polynomial is
* divided by a monic polynomial of the first degree.
*
* Compile: csc TestSyntheticMethod.cs
*
* Execute: TestSyntheticMethod -2 1 3 3 1
*/
using System;
namespace MyTestApplication1 {
public class TestSyntheticMethod {
// 사용법 표시
public static void PrintUsage() {
Console.WriteLine("사용법: TestSyntheticMethod [수] [피제식의 계수들]");
Console.WriteLine("조립제법(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) {
Console.WriteLine(" " + ToPolyString(c));
Console.WriteLine();
Console.Write(" = ( " + 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];
}
Console.Write("( " + ToPolyString(tmp) + " )");
double r = b[b.Length - 1];
if (r > 0.0)
Console.Write(" + " + Simplify(r));
else if (r < 0.0)
Console.Write(" - " + Simplify(Math.Abs(r)));
Console.WriteLine();
}
// 조립제법 계산표 출력 메소드
public static void PrintSyntheticTable(double a, double[] c, double[] s, double[] q) {
Console.Write(" | ");
Console.Write(Simplify(c[0], 6));
for (int i = 1; i < c.Length; i++) {
Console.Write(" " + Simplify(c[i], 6));
}
Console.WriteLine();
Console.Write(Simplify(a, 6) + " | ");
Console.Write(" ");
Console.Write(Simplify(s[1], 6));
for (int i = 2; i < s.Length; i++) {
Console.Write(" " + Simplify(s[i], 6));
}
Console.WriteLine();
Console.Write(" |-");
for (int i = 0; i < q.Length; i++) {
Console.Write("--------");
}
Console.WriteLine("");
Console.Write(" ");
Console.Write(Simplify(q[0], 6));
for (int i = 1; i < q.Length; i++) {
Console.Write(" " + Simplify(q[i], 6));
}
Console.WriteLine();
}
// Java 언어의 main 메소드에 해당하는 C# 언어의 Main 메소드
public static void Main(String[] args) {
if (args.Length < 3) {
PrintUsage();
Environment.Exit(1);
}
//////////////////////////////////////////////////////
// 피제식은 c_0 x^n + c_1 x^(n -1) + ... + c_n
// 제식은 x - a
double a = Convert.ToDouble(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] = Convert.ToDouble(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];
}
//////////////////////////////////////////////////////
// 몫의 계수와 나머지를 출력한다.
Console.Write("몫의 계수는 ");
for (int i = 0; i < b.Length - 2; i++) {
Console.Write(Simplify(b[i]) + ", " );
}
Console.Write(Simplify(b[b.Length - 2]));
Console.WriteLine(" 이고, 나머지는 " + Simplify(b[b.Length - 1]) + " 이다.");
Console.WriteLine();
//////////////////////////////////////////////////////
// 조립제법 표를 출력한다.
PrintSyntheticTable(a, c, s, b);
Console.WriteLine();
//////////////////////////////////////////////////////
// (피제식) = (제식) x (몫) + (나머지)
PrintDivisionResult(a, c, b);
}
}
}

컴파일> csc TestSyntheticMethod.cs
실행> 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

'프로그래밍 > C#' 카테고리의 다른 글

황금비율(golden ratio) 구하기 with C# (0)	2009.01.16
현재 시각 알아내기 for C# (0)	2009.01.16
80컬럼 컨솔에 19단표 출력하기 예제 for C# (0)	2009.01.16
(최대공약수 구하기) while... 반복문 예제 for C# (0)	2009.01.16
if ... else ... 조건문 예제 for C# (0)	2009.01.16