数论 | 秦九韶算法（Horner法则）

2019-06-09 本文已影响0人 0与1的邂逅

写在前面：

最近写作业的时候，用到了多项式来构造哈希函数（散列函数），也正因如此，我遇到了秦九韶算法（Horner法则）。

秦九韶算法：

假定现在有一个n次多项式需要计算。

按照朴素算法来计算，我们需要 $\frac{n(n+1)}{2}$ 次乘法和 $n$ 次加法。我们知道做乘法的代价是很高的，所以朴素算法是非常低效的。

那么，现在引入今天的重头戏——秦九韶算法（Horner法则）。

这样，对于一个n次多项式，我们至多需要做 $n$ 次乘法和 $n$ 次加法。

代码实现：(编译器：DEVC++)

以 $f(x)=n*x^n+(n-1)*x^{n-1}+……+2*x^2+1*x+0$ 为例。

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cmath>
using namespace std;

const int MAX_Number=1000;// 多项式最大项数，即多项式阶数+1 
const int MAX_Time=1e7;// 被测函数最大重复调用次数
const double CLOCKS_PER_SECOND = ((clock_t)1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t)1);
clock_t start,end; 
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;
    }

    start=clock();
    for(int i=0;i<MAX_Time;i++)// 重复调用函数以获得充分多的时钟打点数 
    {
        f1(MAX_Number-1,a,1.1);
    }
    end=clock();
    duration=(double)(end-start)/CLOCKS_PER_SECOND/MAX_Time;
    //printf("ticks1=%lf\n",(double)(end-start));
    printf("duration1=%.10lf s\n",duration); 

    start=clock();
    for(int i=0;i<MAX_Time;i++)// 重复调用函数以获得充分多的时钟打点数
    {
        f2(MAX_Number-1,a,1.1);
    }
    end=clock();
    duration=(double)(end-start)/CLOCKS_PER_SECOND/MAX_Time;
    //printf("ticks2=%f\n",(double)(end-start));
    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 = a_ka_{k-1}a_{k-2}.......a_2a_1a_0$ 可以拆分为：

$n = (((((a_k)*10 + a_{k-1})*10 + a_{k-2})*10 + .......)*10 + a_1)*10+a_0$

例如： $1234 = ((1*10 + 2)*10 + 3)*10 + 4$

则大整数取模，就可以转化为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;
}

写在最后：

参考资料：

端午假期接近尾声，高考的硝烟渐渐散去。早已远离高考考场，但是，那种拼搏的刻苦，是我想找回的！