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' 카테고리의 다른 글

Modular Arithmetic 1탄 - Extended Euclid  (2) 2009.02.22
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Game Theory  (0) 2007.12.19
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28

Leave a Comment


to Top