【数论】 秦九韶公式

【数论】 秦九韶公式如何算这个公式呢 一般都是用 pow 这是个 n n 1 2 n 复杂度的方法 用秦九韶公式可以把其化简为 n n 的复杂度 是不是很有用呢上面的式子可以这样化简 a n x n 1 a n 1 x n 2 a 1 x a 0 a n x n 2 a n 1 x n 3 a 2 x a 1 x a 0 那么可以一直递归下去 可以得到一个非常简单的表达式注意一点 for 循环要从高次幂开始 这样每次乘的 x 会叠加到第一项上 秦九韶公式

 如何算这个公式呢?

 

a_0+a_1x^1+a_2x^2+a_3x^3+...+a_nx^n

一般都是用pow,这是个n*(n-1)/2+n复杂度的方法,用秦九韶公式可以把其化简为

n+n的复杂度,是不是很有用呢

上面的式子可以这样化简

(a[n]*x^(n-1)+a[n-1]*x^(n-2)+...+a[1])*x+a[0] (((a[n]*x^(n-2)+a[n-1]*x^(n-3)+...+a[2])*x+a[1])*x)+a[0]

那么可以一直递归下去,可以得到一个非常简单的表达式

注意一点:

for循环要从高次幂开始,这样每次乘的x会叠加到第一项上,这才正确

#include<stdio.h> int n,x,a[10]; inline long long qing() { long long sum; for(int i=n;i>=1;i--) { sum=(sum+a[i])*x; } return sum; }

今天的文章 【数论】 秦九韶公式分享到此就结束了,感谢您的阅读。
编程小号
上一篇 2024-12-30 17:57
下一篇 2024-12-30 17:51

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/bian-cheng-ji-chu/92033.html