Horner's Rule

다항식의 함수값을 구할 때 Horner's rule이 사용된다..

y = a0 + a1*x + a2*x^2 + a3*x^3 + ... + an*x^n
  = a0 + x(a1 + x(a2 + ... + x(an-1 + x*an)


c 코드로 다음과 같이 구현할 수 있다..

  1 y = 0;
  2 i = n;
  3 while (i >= 0) {
  4     y = a[i] + x * y;
  5     i = i - 1;
  6 }


관련문제로는 UVa 10268 - 498' 가 있다..
이 문제를 풀려면 다항식 미분하는법도 알아야할듯.. OTL ㅠ_ㅠ

'Problem Solving > Algorithm notes' 카테고리의 다른 글

Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12

to Top