Zhao70's Blog

秦九韶算法

发表于 | 分类于

简介

当处理一个多项式在 x = x0 处的值的时候, 不断地对求 x^n 是低效的。 尤其是当n很大的时候, pow(x, n)在多项式系数的循环当中将整个算法的复杂度变为O(n^2).

公式

"秦九韶算法"

程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for(int i = 0; i <= n; ++i)
    {
        cin >> arr[i];
    }
    int x;
    cin >> x;
    int ans = arr[n];
    for(int i = n - 1; i >= 0; --i)
    {
        ans = ans * x + arr[i];
    }
    cout << ans << endl;
    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
import java.util.ArrayList;
import java.util.Scanner;
public class QinJiuZhaoAlgorithm {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		ArrayList<Integer> arr = new ArrayList<Integer>();
		int nNum = in.nextInt();
		for(int i = 0; i <= nNum; i++)
		{
			arr.add(in.nextInt());
		}
		int x = in.nextInt();
		int ans = arr.get(arr.size() - 1);
		for(int i = arr.size() - 2; i >= 0; --i)
		{
			ans = arr.get(i) + x * ans;
		}
		System.out.println(ans);
	}
}