秦九韶算法

梦回江南 · 2022-11-17 12:48:22 · 个人记录

直接切入正题：

对于一个函数：f(x) = a_nx^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + \dots+a_1x + 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

样例输出

26

算法分析：

1. 普通算法

直接暴力求解，程序如下：

#include <cmath>
#include <iostream>
#include <algorithm>
#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;
}

2. 秦九韶算法

对于这个式子： f(x) = a_nx^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + \dots+a_1x + a_0，我们对它进行一些变形：

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