秦九韶算法c++

直接切入正题：

对于一个函数：$f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_{1}x+a_0$

给定 $a_n,a_{n-1}\dots a_0$ 及 $x$，求出 $f(x)$ 的值。

题目描述

如题。

输入格式

输入共两行，第一行为 $n$ 及 $x$。

第二行 $n+1$ 个整数，表示 $a_n$ 到 $a_0$。

输出格式

一行一个整数，表示 $f(x)$。

样例输入

3 2
1 2 3 4
1
2

样例输出

26
1

算法分析：

1. 普通算法
   直接暴力求解，程序如下：

#include 
#include 
#include 
#define L unsigned long long
#define ll long long
#define I unsigned int
#define endl '\n'
#define ref(i, a, b, p) for (signed(i) = (a); (i) <= signed(b); (i) += signed(p))
#define gef(i, a, b, p) for (signed(i) = (a); (i) >= signed(b); (i) -= signed(p))
using namespace std;

int a[1005], x, n;
ll ans;

void work()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> x;
    gef (i, n, 0, 1)
        cin >> a[i];
    ref (i, 0, n, 1)
        ans += a[i] * pow(x, i);	// 如题，直接计算即可
    cout << ans << endl;

    return ;
}

int main()
{
    work();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2. 秦九韶算法

对于这个式子： $f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_{1}x+a_0$，我们对它进行一些变形：
$$\begin{gathered} f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_{1}x+a_0 \\ =(a_n{x}^{n-1}+a_{n-1}{x}^{n-2}+\cdots +a_1)x+a_0 \end{gathered}$$

之后不断提公因数 $x$，得到如下式子：

$f(x)=(\dots ((a_{n}x+a_{n-1})x+a_{n-2})\cdots +a_1)x+a_0$，

这就是 秦九韶算法。

代码实现：

#include 
#include 
#include 
#define L unsigned long long
#define ll long long
#define I unsigned int
#define endl '\n'
#define ref(i, a, b, p) for (signed(i) = (a); (i) <= signed(b); (i) += signed(p))
#define gef(i, a, b, p) for (signed(i) = (a); (i) >= signed(b); (i) -= signed(p))
using namespace std;

int a[1005], x, n;
ll ans;

void work()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> x;
    gef(i, n, 0, 1)
        cin >> a[i];
    ans = a[n];
    gef(i, n, 1, 1)
        ans = ans * x + a[i - 1];
    cout << ans << endl;

    return;
}

int main()
{
    work();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36