秦九韶算法

//计算多项式a0+a1*x+a2*x^2+...+an*x^n
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int ar[n];
    for(i=0;i<n;i++)
    {
        scanf("%d",&ar[i]);
    }
    int p = a[n-1];
    for(i=n-1;i>=0;i--)
    {
        p = p*x + a[i];
    }
    return 0;
}

时间: 06-21

秦九韶算法的相关文章

秦九韶算法求解多项式

秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法.在西方被称作霍纳算法.它是一种将一元n次多项式的求值问题转化为n个一次式的算法. 一般地,一元n次多项式的求值需要经过[n(n+1)]/2次乘法和n次加法,而秦九韶算法只需要n次乘法和n次加法.其大大简化了计算过程,即使在现代,利用计算机解决多项式的求值问题时,秦九韶算法依然是最优的算法. 题目:写程序计算给定多项式在给定点x处的值 f(x) = a0 + a1x + … + an-1xn-1 + anxn 分析:对比使用常规算法和

算法 秦九韶算法

秦九韶算法又叫霍纳算法. 一般地,一元n次多项式的求值需要经过[n(n+1)]/2次乘法和n次加法,而秦九韶算法只需要n次乘法和n次加法.在人工计算时,一次大大简化了运算过程. Pn(x)= anx ^n+a(n-1)x^(n-1)+…+a1x+a0 可简化成 Pn(x)= anx ^n+a(n-1)x^(n-1)+…+a1x+a0=((…(((anx +an-1)x+an-2)x+ an-3)…)x+a1)x+a0 1 package com.qyf404.lean.algorithm; 2

bzoj3157国王奇遇记(秦九韶算法+矩乘)

bz第233题,用一种233333333的做法过掉了(为啥我YY出一个算法来就是全网最慢的啊...) 题意:求sigma{(i^m)*(m^i),1<=i<=n},n<=10^9,m<=200 别人的做法: O(m^2logn),O(m^2),甚至O(m)的神做法 学渣的做法:矩乘+秦九韶算法,O(m^3logn),刚好可以过最弱版本的国王奇遇记的数据 (极限数据单点其实是1.2s+,不想继续卡常了-bzoj卡总时限使人懒惰-如果把矩乘的封装拆掉可能会快点吧,然而人弱懒得拆了...

算法 《秦九韶算法java实践》

[历史背景] 秦九韶算法是中国南宋时期的数学家秦九韶表述求解一元高次多项式的值的算法--正负开方术.它也可以配合牛顿法用来求解一元高次多项式的根.在西方被称作霍纳算法(Horner algorithm或Horner scheme),是以英国数学家威廉·乔治·霍纳命名的. [原理解释] 设有n+1项的n次函数 f(x)=anxn+ an-1xn-1+an-2xn-2+ an-3xn-3+-- a2x2+a1x+ a0 将前n项提取公因子x,得 f(x)=(anxn-1+ an-1xn-2+an-2

【秦九韶算法】【字符串哈希】bzoj3751 [NOIP2014]解方程

在模意义下枚举m进行验证,多设置几个模数,而且小一些,利用f(x+p)%p=f(x)%p降低计算次数.UOJ AC,bzoj OLE. #include<cstdio> #include<iostream> #include<cstring> #include<vector> using namespace std; #define MAXV 4951 vector<int>v; typedef unsigned int ull; const u

快速幂算法

求超大次幂的算法,可将时间复杂度从O(N)降为 O(log?N) 百科里有很清晰的介绍: http://baike.baidu.com/link?url=x4vZ0RoaOyeRqi9vT4vYICe6uy8SeHhB1i6cCHPHTWBEcbdzGG06G8McAymojBn9Aq_1-PU_CVsww39dvmyPI_ int pow4(int a,int b) { int r=1,base=a; while(b!=0) { if(b&1) r*=base; base*=base; b>

快速幂取余算法

下面是一个快速幂的介绍: 先贴一个秦九韶算法(Horner算法)的原理: 设有项的次函数 将前项提取公因子,得 再将括号内的前项提取公因子,得 如此反复提取公因子,最后将函数化为 令 ...... 则即为所求 下面是讲解快速幂的:(By  夜せ︱深   感谢作者) 快速幂取模算法 在网站上一直没有找到有关于快速幂算法的一个详细的描述和解释,这里,我给出快速幂算法的完整解释,用的是C语言,不同语言的读者只好换个位啦,毕竟读C的人较多~ 所谓的快速幂,实际上是快速幂取模的缩写,简单的说,就是快速的求

秦九昭算法

问题4:怎样求一般的多项式当时的值? 求的值时, 即 则 要求值只需要做n次乘法,n次加法.这种算法是由南宋大数学家秦九韶在他的<数书九章>中首先介绍,我们把这种计算方法叫做秦九韶算法. 介绍南宋大数学家秦九韶   秦九韶(1208年-1261年)南宋官员.数学家,与李冶.杨辉. 朱世杰并称宋元数学四大家.主要成就:1247年完成了数学名著<数学九章>,其中的大衍求一术.三斜求积术和秦九韶算法是具有世界意义的重要贡献.秦九韶算法就是中国古代数学的一枝奇葩.直到今天,这种算法仍是多项

位运算之——按位与(&amp;)操作——(快速取模算法)

由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快. 按位与(Bitwise AND),运算符号为& a&b 的操作的结果:a.b中对应位同时为1,则对应结果位也为1. 例如: 10010001101000101011001111000 & 111111100000000 --------------------------------------------- 10101100000000 对10101100000000进行右移8位得到的是101011,这就得