用秦九韶算法求多项式这里是怎么查的5次乘法

来源：蜘蛛抓取(WebSpider) 时间：2018-05-02 14:48 标签： 用秦九韶算法求多项式
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
秦九韶算法有多少次乘法,多少次加法
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
从a0 + a1x开始到an x^n,共有n次加法,n次乘法
为您推荐：
其他类似问题
扫描下载二维码秦九韶算法，有没有通俗点的解释，看不懂T_T v1 v2又是什么东西_百度知道
秦九韶算法，有没有通俗点的解释，看不懂T_T v1 v2又是什么东西
我有更好的答案
希望你采纳
那要怎么计算
那次数提高了又要怎么办
总比直接算简单吧
考试好像不常见
高考会考？
你看下这个
这个我也不清楚
反正懂总比不懂好
你是学霸吧
计算时把v分开算？
这是我们老师给我们的
我也是没办法呀
为什么你写出v1v2v3
这道题不用
如果求v才这样
我们老师三言两语就带过了
我也是醉了
凡事靠自己
其实这是我补课讲的
我这个题比较难……
6次方了……
你先由高次到低次写下来
在按照前面那个做
祝你学习进步
你也是(^_^)
采纳率：57%
为您推荐：
其他类似问题
秦九韶算法的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。秦九韶算法（霍纳算法）求解多项式 - SteveWang - 博客园
尘世中一个迷途小书童，读书太少，想得太多
posts - 72, comments - 37, trackbacks - 0, articles - 0
　　秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法，在西方被称作霍纳算法。它是一种将一元n次多项式的求值问题转化为n个一次式的算法。
　　一般地，我们用系数表达一个一元n次多项式（对应的，还有点值表达），在这种表达方式下直接求值需要执行n(n+1)/2次乘法和n次加法，时间复杂度为O(n2)；而秦九韶算法只需要n次乘法和n次加法，时间复杂度为O(n)，大大简化了计算过程，即使在现代，利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法。
　　题目：写程序计算给定多项式在给定点x处的值　　f(x) = a0&+ a1x + & + an-1xn-1&+ anxn
　　分析：对比使用常规算法和秦九韶算法求解多项式，并输出它们各自消耗的时间进行比较。
　　　　　这里用到了time.h头文件中的clock()函数，它的函数原型如下：
_CRTIMP clock_t __cdecl __MINGW_NOTHROW clock (void);
// 可以把它直接视为clock_t clock(void);
　　　　　
　　　　　返回值clock_t是用来保存时间的数据类型，它是一个长整型数。这个函数返回从开启这个程序进程到程序中调用clock()函数之间的CPU时钟计时单元（clock tick，即时钟打点）数
　　　　　在time.h文件中，还定义了一个常量CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元（clock tick）。其定义如下：&
#define CLOCKS_PER_SEC ((clock_t)1000)
　　　　　可以看到每过千分之一秒（1毫秒），调用clock()函数返回的值就加1。所以想要得到一段程序从开始到现在执行的时间(以秒为单位)，只需用&(double)clock()/CLOCKS_PER_SEC&，也可以使用CLK_TCK替代CLOCKS_PER_SEC，详见
　　　　　这里我们只需测试我们自定义函数执行的时间，这个时间往往不足一个clock tick，所以我们必须重复调用被测函数，使得测出的总的时钟打点间隔充分长，最后在除以调用次数，才能得到被测函数的单次执行时间
　　源码：
#include&stdio.h&
#include&time.h&
#include&math.h&
#define MAXK 1e7
// 被测函数重复调用次数1*10^7
#define MAXN 10
// 多项式最大项数，即多项式阶数+1(n阶多项式有n+1个项，包括一个常数项)
clock_t start,
// clock_t是clock()函数的返回变量类型
// 记录被测函数运行时间，以秒为单位
double f1(int n,double a[],double x);
// 常规算法声明
double f2(int n,double a[],double x);
// 秦九韶算法函数声明
int main()
double a[MAXN];
// 存储多项式的系数(系数暂且赋值为i)
for(i=0; i&MAXN; i++)
a[i] = (double)i;
/* 不再测试范围内的准备工作写在clock()调用之前 */
start = clock();
// 开始计时
for(i=0; i&MAXK; i++)
f1(MAXN-1,a,1.1);
// 重复调用测试函数f1以获得充分多的时间打点数
stop = clock();
// 停止计时
/* 其他不再测试范围的处理写在后面 */
duration = (double)(stop - start)/CLOCKS_PER_SEC/MAXK;// 计算测试函数单次运行时间
printf("ticks1 = %ld\t",stop-start);
printf("duration1 = %6.2e\n",duration);
/* 不再测试范围内的准备工作写在clock()调用之前 */
start = clock();
// 开始计时
for(i=0; i&MAXK; i++)
f2(MAXN-1,a,1.1);
// 重复调用测试函数f2以获得充分多的时间打点数
stop = clock();
// 停止计时
/* 其他不再测试范围的处理写在后面 */
duration = (double)(stop - start)/CLOCKS_PER_SEC/MAXK;// 计算测试函数单次运行时间
printf("ticks2 = %ld\t",stop-start);
printf("duration2 = %6.2e\n",duration);
double f1( int n, double a[], double x )
// 常规算法
double p = a[0];
for (i=1; i&=n; i++)
p += (a[i] * pow(x, i));
double f2( int n, double a[], double x )
// 秦九韶算法
double p = a[n];
for (i=n; i&0; i-- )
p = a[i-1] + p*x;
　　运行结果：
　　从结果看出，两种方法的运行时间不在一个数量级之上，利用秦九韶算法f2计算多项式大大的提高了效率。

我要回帖

更多关于 用秦九韶算法求多项式 的文章

 

随机推荐