2025年秦九韶算法

科技前沿 • 2025-02-07 20:09 • 阅读 28

大家好，我是讯享网，很高兴认识大家。

秦九韶算法

秦九韶算法是一种多项式简化算法,它的算法复杂度是O(n)

$a_0x^n + a_1x^{n-1}+\cdots + a_{n-1}x + a_n$

步骤如下：

令 $b_0=a_0$

$b_1=b_0\times x+a_1$

$b_2=b_1 \times x + a_2$

$\cdots\cdots$

$b_n=b_{n-1} \times x + an$

则 $b_n=q(x)$

竖式写法：

$\begin{array}{c|c|ccc} {a_i}&{a_0}&{a_1}&{ \dots }&{a_n}\\\hline{}&{}&{b_0 \times x}&{ \dots }&{b_{n-1} \times x}\\{b_i}&{b_0}&{b_1}&{\dots}&{bn}\\\end{array}$

讯享网

代码如下：

#include <iostream> using namespace std; int main() { 
    double a[100],x; // 代表 ai int n; // 输入数据 cout<<"输入项数n:"; cin>>n; cout<<"输入x的值:"; cin>>x; cout<<"输入多项式系数:"<<endl; for(int i=0;i<n;i++) cin>>a[i]; // 秦九韶算法计算结果  int sum=a[0]; // 也可以用一个数组b[]来代表bi for(int i=1;i<n;i++) { 
    sum*=x; sum+=a[i]; } cout<<"结果:"<<sum; /* 用数组b[]的写法如下: int b[100]; b[0]=a[0]; for(int i=1;i<=n;i++) { b[i]=b[i-1] * x + a[i]; } cout<<b[n]; */ return 0; }

讯享网

运行结果：

在这里插入图片描述

其实还可以这样考虑：

原多项式为

$a_0x^n + a_1x^{n-1}+\cdots + a_{n-1}x + a_n$

我们改变一下多项式的格式

$a_0 + a_1x+\cdots + a_{n-1}x^{n-1} + a_nx^n$

令 $f(n)=x^n$ ，则多项式变为

$a_0 \times f(0) + a_1 \times f(1)+\cdots + a_{n-1} \times f(n-1) + a \times f(n)$

显然 $\times x$ ，这样通过对 $f (n)$ 的改变来进行迭代完成多项式计算

代码如下：

讯享网#include <iostream> using namespace std; int main() { 
    double a[100],x; // 代表 ai int n; // 输入数据 cout<<"输入项数n:"; cin>>n; cout<<"输入x的值:"; cin>>x; cout<<"输入多项式系数:"<<endl; for(int i=0;i<n;i++) cin>>a[i]; // 计算  int f=1; // f(n),也可以考虑用数组f[] int sum=0; for(int i=0;i<n;i++) { 
    sum+=a[i]*f; f*=x; } cout<<f/x<<endl; cout<<sum; /* 用数组f[]的写法如下: int f[100]; f[0]=1; sum=a[0]; for(int i=1;i<n;i++) { f[i]*=f[i-1]*x; sum+=a[i]*f[i]; } cout<<sum; */ return 0; }

2025年秦九韶算法

秦九韶算法

步骤如下：

竖式写法：

代码如下：

运行结果：

其实还可以这样考虑：

代码如下：

相关推荐