算法练习专栏算法小扩展01——秦九昭算法（选看）

image-20240225162752015

题目描述

秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。

对于一个一元次多项式：f(x)=a_{n}x^n+a_{n-1}x^{n-1}+······+a_1x+a_0

在代入一个特定的进行整体求值时，若用朴素方法处理，需要经过\frac{n(n+1)}{2}次乘法和n次加法。但使用秦九韶算法计算，通过去除冗余的计算步骤，只需次乘法和次加法就可计算出f(x)的值。

秦九韶算法的中心思想：

f(x)=a_{n}x^n+a_{n-1}x^{n-1}+······+a_1x+a_0

改写为

f(x)=((······(a_nx+a_{n-1})x+a_{n-2})x+······)x+a_1)x+a_0。

输入

第1行输入n，表示系数的个数。

第2行输，a_0，a_1，······，a_{n-1}，a_n，表示系数。

第3行输入ans。

输出

一行，表示上述的值。

分析

用朴素方法处理的值时，计算f(x)的值时，计算x，x^2，······，x^{n-1}，x^n会造成许多冗余操作，而秦九韶算法通过多项式的层层嵌套，巧妙地避开了不必要的计算，减少计算操作的次数。秦九韶算法分析：

1.答案ans初始化为a_n；

2.对于i=1，2，······，n-1，n，循环执行ans=ans\times x+a_{n-i}；

3.输出结果ans。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int n,x,ans,a[21];
int main(){
    cin>>n;
    for(int i=0;i<=n;i++)
        cin>>a[i];
    cin>>x;
    ans=a[n];
    for(int i=1;i<=n;i++)
        ans=ans*x+a[n-i];
    cout<<ans; 
    return 0;
}

(a1)