浅谈秦九韶算法
好像FFT要用到，所以就学习一下听说还是高中必修三的内容？
目录
-
浅谈秦九韶算法
- 秦九韶算法的应用：
- code
秦九韶算法的应用：
当我们知道 \(x\ 的值时，求下列式子的值：
\[f(x = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_{n - 1}x^{n - 1} + a_nx^n
\]
那秦九韶还提出来干什么
我们发现单单一个 \(x^n\ 就需要 \(n - 1\ 次乘法，那么一共就需要 \(\sum_{i = 1} ^ {n - 1}i\ 次乘法，和 \(n\ 次加法，如下 \(n = 5\ 时：
\[f(x = a_0 + a_1x + a_2x + a_3x + a_4x + a_5x
\]
显然这个十分复杂，所以才要用到奏九韶算法
秦九韶算法就是将上述式子一步步化简成如下式子:
\[f(x = ( \cdots (a_nx + a_{n - 1}x + a_{n - 2}x + \cdots + a_1x + a_0
\]
code
代码十分短
void qinjiushao(
{
for(int i=n-1;i>=1;i--
ans*=x,ans+=a[i];
}