精华内容
下载资源
问答
  • /*2.39采用存储量同多项式项数m成正比的顺序存储结构编写求稀疏多项式算法,并分析算法的时间复杂度*/ #include <stdlib.h> #include <stdio.h> #include <math.h> #define OK 1 #define ERROR...
    /*2.39采用存储量同多项式项数m成正比的顺序存储结构编写求稀疏多项式的算法,并分析算法的时间复杂度*/
    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>
    
    #define OK 1
    #define ERROR 0
    
    typedef int Status;
    
    typedef struct {//项结构
    	int coef;//系数
    	int exp;//指数
    }Ployn;
    
    typedef struct {//多项式结构(顺序表)
    	Ployn* elem; 
    	int length;
    }SqPloy;
    
    Status InitSqPloy(SqPloy& L) {
    	//初始化多项式
    	L.elem = (Ployn*)malloc(100 * sizeof(Ployn));
    	if (!L.elem)
    		return ERROR;
    	L.length = 0;
    	return OK;
    }//InitSqPloy
    
    Status CreatSqPloy(SqPloy& L, int m) {
    	//创建一个m项的多项式
    	Ployn* p = L.elem;//指针p指向多项式第一项
    	printf("逐项请输入稀疏多项式的系数和指数,英文逗号隔开\n");
    	for (int i = 0; i < m; i++) {
    		//依次输入每项的系数和指数
    		scanf_s("%d,%d", &(p->coef), &(p->exp));
    		p++;
    		L.length++;
    	}
    	return OK;
    }//CreatSqPloy
    
    Status ShowSqPloy(SqPloy& L) {
    	//展示多项式
    	Ployn* p = L.elem;
    	printf("P(X) =");
    	for (int i = 0; i < L.length; i++){
    		printf("%d x exp(%d) ",p->coef,p->exp);
    		p++;
    	}
    	printf("\n");
    	return OK;
    }//ShowSqPloy
    
    int Calculate(SqPloy& L, int x0) {
    	//计算并返回多项式的值
    	int a;
    	int s = 0;
    	Ployn* p = L.elem;
    	for (int i = 0; i < L.length; i++){
    		a = p->coef * int(pow(x0, p->exp));
    		p++;
    		s += a;
    	}
    	return s;
    }//Calculate
    
    int main() {
    	SqPloy L;
    	InitSqPloy(L);
    	CreatSqPloy(L, 3);//以三项式为例
    	ShowSqPloy(L);
    	printf("多项式的结果为:%d",Calculate(L, 3));//给x0赋值位3,计算多项式
    }
    
    
    
    
    

    运行结果:
    在这里插入图片描述

    Calculate函数中,循环体执行次数为顺序表长度,时间复杂度 O(n)=n。

    展开全文
  • 多项式求值秦九韶算法

    千次阅读 2021-01-05 22:20:00
    1.多项式求值的秦九韶算法 设给定nnn次多项式p(x)=a0xn+a1xn−1+⋯+an−1x+an,a0≠0,p(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,\quad a_0\neq 0,p(x)=a0​xn+a1​xn−1+⋯+an−1​x+an​,a0​​=0, x∗处的...

    1.多项式求值的秦九韶算法

    设给定 n n n次多项式 p ( x ) = a 0 x n + a 1 x n − 1 + ⋯ + a n − 1 x + a n , a 0 ≠ 0 , p(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,\quad a_0\neq 0, p(x)=a0xn+a1xn1++an1x+an,a0=0,
    x ∗ 处 的 值 p ( x ∗ ) . 若 直 接 计 算 每 一 项 a i x n − i 再 相 加 , 共 需 要 x^*处的值p(x^*).若直接计算每一项a_ix^{n-i}再相加,共需要 xp(x).aixni,
    ∑ i = 0 n ( n − i ) = 1 + 2 + ⋯ + n = n ( n + 1 ) 2 = O ( n 2 ) \sum_{i = 0}^{n}(n-i)=1+2+\cdots+n=\frac{n(n+1)}{2}=O(n^2) i=0n(ni)=1+2++n=2n(n+1)=O(n2)次乘法, n n n次加法.若采用
    p ( x ) = ( ⋯ ( a 0 x + a 1 ) x + ⋯ + a n − 1 ) x + a n , p(x)=(\cdots(a_0x+a_1)x+\cdots+a_{n-1})x+a_n, p(x)=((a0x+a1)x++an1)x+an,它可表示为
    { b 0 = a 0 , b i = b i − 1 x ∗ + a i , i = 1 , 2 , … , n , \begin{cases} b_0=a_0,\\ b_i=b_{i-1}x^*+a_i,i=1,2,\ldots,n, \end{cases} {b0=a0,bi=bi1x+ai,i=1,2,,n,
    b n = p ( x ∗ ) 即 为 所 求 . b_n=p(x^*)即为所求. bn=p(x).此算法称为秦九韶算法,用它计算 n 次 多 项 式 p ( x ) n次多项式p(x) np(x)的值只用 n 次 乘 法 和 n 次 加 法 n次乘法和n次加法 nn
    乘 法 次 数 由 O ( n 2 ) 降 为 O ( n ) , 且 只 用 n + 2 个 存 储 单 元 , 国 外 称 此 算 法 为 H o r n e r 算 法 乘法次数由O(n^2)降为O(n),且只用n+2个存储单元,国外称此算法为Horner算法 O(n2)O(n),n+2Horner

    2.Python实现秦九韶算法

    import numpy as np
    from sympy.abc import x
    
    
    def polynomial(coefficient_array: np.ndarray, is_ascending_order: bool = False):
        """
        构造指定系数的多项式
        :param coefficient_array: 多项式系数数组
        :param is_ascending_order: 多项式排列顺序
        :return: 多项式
        """
        degree = coefficient_array.shape[0]
        if is_ascending_order:
            coefficient_array = coefficient_array[::-1]
        # default,descending order arrangement
        p_x = coefficient_array[-1]
        for i in range(degree - 1, 0, -1):
            p_x += coefficient_array[degree - i - 1] * pow(x, i)
        return p_x
    
    
    def qin_jiu_shao(coefficient_array: np.ndarray, value, is_ascending_order: bool = False):
        """
        多项式求值的秦九韶算法,即Horner算法
        :param coefficient_array: 多项式系数数组
        :param value: 自变量的值
        :param is_ascending_order: 多项式排列顺序
        :return: the value of polynomial
        example:
        2*x**4 - 3*x**2 + 3*x - 4=((((2x+0)x-3)x+3)x-4)
        3*x**5 - 2*x**3 + x + 7=(((((3x+0)x-2)x+0)x+1)x+7)
        """
        if is_ascending_order:
            coefficient_array = coefficient_array[::-1]
        degree = coefficient_array.shape[0]
        b = coefficient_array[0]
        for i in range(1, degree):
            b = b * value + coefficient_array[i]
        return b
    

    3.多项式求值测试

    if __name__ == '__main__':
        # 测试成功,来源详见李庆扬数值分析第5版P14,e.g.11
        # 降幂排列
        coefficient0 = np.array([2, 0, -3, 3, -4])
        print(polynomial(coefficient0))
        print(qin_jiu_shao(coefficient0, -2))
        # 升幂排列
        coefficient1 = np.array([-4, 3, -3, 0, 2])
        print(polynomial(coefficient1, is_ascending_order=True))
        print(qin_jiu_shao(coefficient1, -2, is_ascending_order=True))
        # 测试成功,来源详见李庆扬数值分析第5版P20,e.x.14
        # 降幂排列
        coefficient2 = np.array([3, 0, -2, 0, 1, 7])
        print(polynomial(coefficient2))
        print(qin_jiu_shao(coefficient2, 3))
        # 升幂排列
        coefficient3 = np.array([7, 1, 0, -2, 0, 3])
        print(polynomial(coefficient3, is_ascending_order=True))
        print(qin_jiu_shao(coefficient3, 3, is_ascending_order=True))
    

    4.求值运行结果

    在这里插入图片描述

    展开全文
  • 利用秦九韶算法求多项式 示例:例如p(x)=pow(x,5)-3pow(x,4)+4pow(x,2)-x+1 ,当x=3时的。 按秦九韶算法展开:则p(x)=(x(x(x(x-3)+4)-1)+1),则最里层为(x-3),对它的解释为最高项的系数与x的乘积加上次高...

    示例:求p(x) = x⁵ - 3 x⁴ + 4 x² - x + 1 ,当x = 3时的值。
    按秦九韶算法展开:则p(x)=(x(x(x(x-3)+4)-1)+1),则最里层为(x-3),对它的解释为最高项的系数与x的乘积加上次高项的系数,这个结果作为下一次循环的系数,即计算(x(x-3)+4)等于上次计算结果(x-3)与x的乘积x(x-3)加上次次高项(x(x-3)+4)的系数4。依次迭代,最终得出多项式的值。

    • 运行示例:

    在这里插入图片描述

    • 源码:
    //实现利用秦九韶算法求多项式的值
    //示例:例如求p(x)=pow(x,5)-3*pow(x,4)+4*pow(x,2)-x+1 ,当x=3时的值
    //按秦九韶算法展开:则p(x)=(x(x(x(x-3)+4)-1)+1)
    #include<iostream>
    using namespace std;
    int main(void)
    {
    	double item,x,coefficient;   //coefficient每项前的系数,x为自变量
    	int up,i;   //up为最高次项的次数
    
    	cout << "请输入自变量x的值:";
    	cin >> x;
    
    	cout << "请输入最高次项的次数:";
    	cin >> up;
    
    	cout << "请输入"<<up<<"次项的系数:";
    	cin >> coefficient;
    
    	//把item赋值为最里层最高次项的系数, 以便进入第一次循环时进行最里层第一项的计算,避免再次输入次高项系数时最高项系数被覆盖
    	item = coefficient;
    
    	//系数cofficient依次从次高项直至次数为0项依次输入
    	for (i = up-1; i >= 0; i--) 
    	{
    		if (i == 0)
    		 {
    			cout << "请输入常数项的值:";
    			cin >> coefficient;
    		}
    		else 
    		{
    			cout << "请输入" << i << "次项的系数:";
    			cin >> coefficient;
    		}
    
    		//按秦九韶算法展开,最里面一项为最高次项的一次乘系数加上次高项的系数,往后依次迭代
    		item = item * x + coefficient; 
    	}
    
    	cout << "\n所求多项式的值为:" << item << endl;
    
    	return 0;
    }
    
    展开全文
  • 编写程序求多项式 在某一点x的。 相关知识:秦九韶算法(递推计算公式) 递推关系的由来:因为 可以改写为
  • 多项式秦九韶算法c语言

    千次阅读 2020-08-16 20:46:53
    多项式秦九韶算法c语言 1)最直接的方法是根据多项式的标准表达式,通过循环累计求和来实现这个函数,但效率会很低。...//秦九韶多项式算法 double fun1(int n, double* a, double x){ int i; double p =

    多项式秦九韶算法c语言

    在这里插入图片描述

    1)最直接的方法是根据多项式的标准表达式,通过循环累计求和来实现这个函数,但效率会很低
    2)秦九韶算法,通过不断提取公因式x来减少乘法运算的次数

    #include <stdio.h>
    #include<math.h>
    #include<time.h>
    #define MAXN 10
    
    
    //秦九韶多项式算法
    double fun1(int n, double* a, double x){
    
        int i;
        double p = a[n];//初始值
        for(i = n; i > 0; i--){
            p = a[i-1] + x * p;
        }
        return p;
    }
    
    //一般算法
    double fun2(int n, double* a, double x){
        double p = a[0];//初始值
        int i;
        for(i = 1; i <= n; i++){
            p += a[i] * pow(x,i);
        }
        return p;
    }
    
    int main()
    {
        double a[MAXN];
        int i;
        for(i = 0; i < MAXN; i++) a[i] = i;
        double p = fun1(MAXN, &a, 1);
        printf("%.2f", p);
        return 0;
    }
    
    展开全文
  • C语言 多项式乘法 算法

    千次阅读 2021-01-13 16:46:21
    多项式乘法 什么是多项式? 由若干个单项式相加组成的代数式叫做多项式(若有减法:减一个数等于加上它的相反数)。 多项式中的每个单项式叫做多项式的项,这些单项式中的最高项次数,就是这个多项式的次数。 ...
  • 计算多项式值的秦九韶算法

    千次阅读 2016-09-11 08:26:59
    //计算多项式值的秦九韶算法 double getresult(double array[],int n,double x)//double array[];//存系数,a[0]为常数项 { double result=array[n-1]; for(int i=n-1;i>=1;i--) result=array[i-1]+result*x; ...
  • 一般地,一元n次多项式求值需要经过(n+1)*n/2次乘法和n次加法,而秦九韶算法只需要n次乘法和n次加法。在人工计算时,一次大大简化了运算过程。 把一个n次多项式 改写成如下形式: 求多项式...
  • 给定两个一元多项式,实现两个一元多项式的相加算法。提示:用一条单链表表示一个一元多项式,每个节点包含三个域:指数域、系数域和后继结点链。 可直接运行 #include <stdio.h> #include <stdlib.h> #...
  • 本程序的功能是本原多项式(java),算法参考文献为维普资讯网 文章标号1000-3428(2004)16-0108-02 伪随机序列中本原多项式生成算法 作者:吕辉 何晶 王刚。 如果有别的算法需要实现程序的,请联系我。小弟联系...
  • 此法只用n次加法和n次乘法,称此算法为秦九韶算法 数据结构:一维数组 实验要求:编写通用程序——能够任意多项式在任意一点的
  • 多项式求值 要求实现一个函数,计算阶数为n,系数为a[0] … a[n]的多项式 f(x)=∑​i=0n​​(a[i]×x​i​​) f(x)=∑ ​_{i=0}^n ​​ (a[i]×x ​^i ​​ ) f(x)=∑​i=0n​​​(a[i]×x​i​​) 在x点的。 也...
  • 多项式插值是计算函数近似的一种方法。其中函数值仅在几个点上已知。 该算法的基础是建立级数小于等于n的一个插值多项式pn(z),其中n+1是已知函数值的点的个数。 多项式插值法 许多问题都可以按照函数的方式来...
  • 秦九韶算法 求解多项式值

    千次阅读 2013-09-20 09:53:15
    cout请输入自变量X的:"; cin>>x; cout依次降幂输入多项式的系数,无系数需输入0代:" ; for(t;t>=0;t--) cin>>a[t]; p1=a[n]*x+a[n-1]; for(n=n-2;n>=0;n--) p1=p1*x+a[n]; cout; ...
  • //降幂排列的一元稀疏多项式。pow(x, y)是x的y次幂的函数, 其原型在"math.h"中 Polynomial p = PL->link; double value = p->coef; int e = p->exp; //存放系数am和指数em的 p = p->link; //...
  • //多项式相加: #include <iostream> using namespace std; class Node {//项的定义 public: int a; int b; Node* next; Node(int aa, int bb) { a = aa; b = bb; next = NULL;; } }; class ...
  • 1126: 零起点学算法33——求多项式 Time Limit: 1 SecMemory Limit: 64 MB 64bit IO Format: %lldSubmitted: 2614Accepted: 1356[Submit][Status][Web Board] Description 形如1-2+3-4...+n,你会编写吗? ...
  • 一元多项式

    2021-08-08 00:02:46
    //一元多项式 #include<stdio.h> #include<math.h> double poly(double x,int n,double a[])//函数一元多项式 { int exp; double sum=0; for(exp=0;exp<n;exp++) { sum+=(a[exp]*...
  • 一维多项式求值

    2017-09-15 22:53:06
    多项式(Polynomial)是基础数学中常用到的概念,多项式就是若干个单项...一 一维多项式求值 对于一维多项式就是包含一个变量的多项式,一个普遍的一维多项式的形式如下: P(x)=an−1xn−1+an−2xn−2+⋯+a1x+a0P
  • Lagrange插值多项式算法
  • 编写求其导函数的算法,要求利用原多项式中的结 点空间存放其导函数(多项式),同时释放所有无 用(被删)结点。 实现下列函数: void Difference(LinkedPoly &pa); /* 稀疏多项式 pa 以循环链表作存储结构, ...
  • 一元多项式算法

    2020-04-11 21:42:39
    设计一个算法两个多项式 A 和 B 的乘积,结果多项式 C 存放在新辟的空间中。 (这个完全就是浙大慕课上讲的一模一样因为我认真听了,原来自己写的实在不想调试了hhh) #include<stdio.h> #include<...
  • 93.请编写函数fun,其功能是:计算并输出下列多项式值: 例如,若主函数从键盘给n输入50后,则输出为S=1.960784。 注意:n的要求大于1但不大于100。 #include <stdio.h> double fun(double n){ double s=...
  • 88.请编写函数fun,其功能是:计算并输出下列多项式值: Sn= (1-1/2) + (1/3-1/4)+…+(1/2n-1-1/2n) 例如,若主函数从键盘给n输入8后,则输出为S=0.662872。 注意:n的要求大于1但不大于100。部分源程序给出如下...
  • 多项式算法合集

    千次阅读 2019-08-06 14:20:39
    多项式乘法 FFT: const double pi=acos(-1); const int N=4000005; struct plx{ double x,y; plx(double _x=0,double _y=0):x(_x),y(_y){} friend inline plx operator +(const plx &a,const plx &...
  • 多项式求值(附C++实现)

    千次阅读 2019-03-19 23:06:52
      本文主要介绍了一维多项式求值和二维多项式求值,从算法工程师的视角出发设计更高效的代码。读者可以通过C++代码或者Python代码进一步了解这个算法。 一维多项式求值   计算多项式   显然即使是一个萌新...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,645
精华内容 2,658
关键字:

编写求多项式值的算法