Horner's Rule
Problem Solving/Algorithm notes 2008. 5. 4. 10:44
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 코드로 다음과 같이 구현할 수 있다..
관련문제로는 UVa 10268 - 498' 가 있다..
이 문제를 풀려면 다항식 미분하는법도 알아야할듯.. OTL ㅠ_ㅠ
다항식의 함수값을 구할 때 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 }
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 |