写在前面：
最近写作业的时候，用到了多项式来构造哈希函数（散列函数），也正因如此，我遇到了秦九韶算法（Horner法则）。
秦九韶算法：
假定现在有一个n次多项式需要计算。
按照朴素算法来计算，我们需要次乘法和次加法。我们知道做乘法的代价是很高的，所以朴素算法是非常低效的。
那么，现在引入今天的重头戏——秦九韶算法（Horner法则）。
这样，对于一个n次多项式，我们至多需要做n次乘法和n次加法。
代码实现：(编译器：DEVC++)
以为例。
#include<iostream>#include<cstdio>#include<ctime>#include<cmath>using namespace std;const int MAX_Number = 1000;// 多项式最大项数，即多项式阶数+1 const int MAX_Time = 1e3;// 被测函数最大重复调用次数const double CLOCKS_PER_SECOND = ((clock_t)1000);//CLOCK_PER_SECOND这个常量表示每一秒（per second）有多少个时钟计时单元const double CLOCKS_PER_MILLISECOND = ((clock_t)1);//CLOCK_PER_SECOND这个常量表示每毫秒（per millisecond）有多少个时钟计时单元clock_t startTime;clock_t endTime;double duration;// (平均)运行时间 // 朴素算法 double f1(int n, double a[], double x){int i;double p = a[0];for (i = 1; i <= n; i++){p += (a[i] * pow(x, i));}return p;}// 秦九韶算法double f2(int n, double a[], double x){int i;double p = a[n];for (i = n; i>0; i--){p = p * x + a[i - 1];}return p;}// 让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算平均每次运行的时间即可 int main(){int i;double a[MAX_Number];// 存储多项式系数 for (int i = 0; i<MAX_Number; i++)// 赋值多项式系数 {a[i] = (double)i;}startTime = clock();for (int i = 0; i<MAX_Time; i++)// 重复调用函数以获得充分多的时钟打点数 {f1(MAX_Number - 1, a, 1.1);}endTime = clock();duration = (double)(endTime - startTime) / CLOCKS_PER_SECOND / MAX_Time;//printf("ticks1=%lf\n",(double)(endTime-startTime));printf("duration1=%.10lf s\n", duration);startTime = clock();for (int i = 0; i<MAX_Time; i++)// 重复调用函数以获得充分多的时钟打点数{f2(MAX_Number - 1, a, 1.1);}endTime = clock();duration = (double)(endTime - startTime) / CLOCKS_PER_SECOND / MAX_Time;//printf("ticks2=%f\n",(double)(endTime-startTime));printf("duration2=%.10lf s\n", duration);}
9次多项式
99次多项式
clock()函数：
clock()：捕捉从程序开始运行到clock()被调用所消耗的时间。时间单位是clock tick。
clock_t：clock()函数返回的变量类型
头文件：ctime
定义时间常数：
const double CLOCKS_PER_SECOND = ((clock_t)1000);
其中，CLOCK_PER_SECOND这个常量表示每一秒（per second）有多少个时钟计时单元const double CLOCKS_PER_MILLISECOND = ((clock_t)1);
其中，CLOCK_PER_SECOND这个常量表示每毫秒（per millisecond）有多少个时钟计时单元
具体步骤：
clock_t start, end;记录开始时间：start = clock();写代码块记录结束时间：end = clock();输出运行时间：cout << (double)(end - start) / CLOCKS_PER_SECOND << "s" << endl;
#include<iostream>#include<cstdio>#include<ctime>#include<cmath>using namespace std;const double CLOCKS_PER_SECOND = ((clock_t)1000);const double CLOCKS_PER_MILLISECOND = ((clock_t)1);clock_t start,end;int main(){start=clock();MyFunction();// 代码块end=clock();cout<<(double)(end-start)/CLOCKS_PER_SECOND<<"s"<<endl;cout<<(double)(end-start)/CLOCKS_PER_MILLISECOND<<"ms"<<endl;}
HDU1212——Big Number
题意：【大整数取模】
给你一个长度不超过1000的大数A，还有一个数值不超过100000的B，快速求A % B。
分析：
由秦九韶算法可知，任意一个整数可以拆分为：
例如：
则大整数取模，就可以转化为n个多项式每步取模。
#include<iostream>#include<cstdio>#include<string>using namespace std;string str;int mod;int Horner(){int ans=0;for(int i=0;i<str.size();i++){ans=(ans*10+str[i]-'0')%mod;}return ans;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>str){cin>>mod;cout<<Horner()<<endl;}return 0;}
