霍纳法则简介
假设有n＋2个实数a0，a1，…，an,和x的序列，要对多项式Pn(x)= anxn＋an－１xn－１＋…＋a１x＋a０求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，它需要进行n＋(n－1)＋…＋1＝n(n＋１)/2次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法，即Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０＝((…(((anx ＋an－１)x＋an－２)x+ an－3)…)x＋a1)x＋a０，这种求值的安排我们称为霍纳法则。
具体实现：
#include <iostream>
using namespace std;
int Horner_rule(int arr[],int n,int x)
{int i,ans = 0;;for(i = 0; i<n; i++)//次数项从0次开始{ans = arr[i]+x*ans;}return ans;
}
int main()
{int n,x,i,t,arr[1000];cin>>t;while(t--){cout<<"输入 : n , x : ";cin>>n>>x;cout<<"输入 "<<n <<" 个数 : ";for(i = n-1; i>=0; i--) //求值是从 an 开始，所以倒着存cin>>arr[i];for(i = 0; i<n-1; i++)cout<<arr[i]<<"*x"<<"^"<<i<<"+";cout<<arr[i]<<"*x"<<"^"<<i<<" = ";cout<<Horner_rule(arr,n,x)<<endl;}return 0;
}