递归思想求解稀疏多项式的值

利用递归思想求解指数连续增长的多项式的值用的是的秦九昭算法，从最里面的一层乘到最外面的一层，这个算法的效率要比一个项一个项的算的算法高出10倍。

这里的思想同秦九昭算法基本一致，唯一的差别就是稀疏多项式相邻两项指数之间的差距不是1，而是一个不确定的数。

另外，利用递归算法计算稀疏多项式的值不建议用函数调用的方式，因为如果当最大指数很大的时候，程序会崩溃，而我们计算一个多项式的时候，就拿书本（数据结构严蔚敏版）的一个多项式来说，指数就有2000多，因而我觉得要改用循环的模式

下面的图片是我在思考用递归算法求解稀疏多项式时的草稿，本人愚钝，用了不少例子思考，下面只是其中一个，希望对你有启发。

这里是代码，最后一个函数就是递归算法了，其他函数只是帮忙构造测验的多项式，希望能帮到你吧

#include<stdio.h> #include<malloc.h> #include<assert.h> #define SIZE 20typedef struct {double ceof;int expn; }Polyterm; typedef struct PolySList {Polyterm *data;int length; }List;void initial(List *list); void insert(List *list,double ceof,int expn); void show(List *list); double calculate(List *list,double x);int main() {List list;initial(&list);printf("现在创建这个多项式，用来计算数值(依次输入系数和指数，-1结束)\n");double ceof;int expn;while(1){scanf("%lf%d",&ceof,&expn);if(ceof==-1)break;insert(&list,ceof,expn);}printf(">>>");show(&list);printf("请输入一个要计算的值\n");double x;scanf("%lf",&x);printf("结果是：%.2lf\n",calculate(&list,x));return(1); }void initial(List *list) {//本算法的功能是初始化一个顺序表list->data=(Polyterm*)malloc(SIZE*sizeof(Polyterm));assert(list->data!=NULL);list->length=0;//多项式的项数为0 }void insert(List *list,double ceof,int expn) {//本算法的前提是顺序表已经初始化并且顺序表没有满//本算法的功能是往顺序表中插入由ceof和expn组成的项//并使多项式保持指数递增排列int i=0,j;while(i<list->length && list->data[i].expn<expn)i++;if(list->data[i].expn==expn){list->data[i].ceof+=ceof;if(list->data[i].ceof==0)//如果正好抵消{for(j=i;j<list->length-1;--j){list->data[j].ceof=list->data[j+1].ceof;list->data[j].expn=list->data[j+1].expn;}list->length--;}}else{for(j=list->length;j>i;--j){list->data[j].ceof=list->data[j-1].ceof;list->data[j].expn=list->data[j-1].expn;}list->data[i].ceof=ceof;list->data[i].expn=expn;list->length++;} }void show(List *list) {//本算法的前提是多项式中至少有一项//本算法的功能是显示多项式if(list->length==0)return;//多项式长度合法性判断for(int i=0;i<list->length;i++){printf("%.2lfx^%d+",list->data[i].ceof,list->data[i].expn);}printf("\b \n"); }double calculate(List *list,double x) {//本算法的前提是多项式中至少有一项//本算法的功能是根据参数x计算多项式的值，并且返回这个值double val;int i,j;val=list->data[list->length-1].ceof;for(i=list->length-1;i>=1;--i){double t=1;for(j=list->data[i].expn-list->data[i-1].expn;j>0;--j) //递归思想计算多项式的值t*=x;val=list->data[i-1].ceof+val*t;}double t=1;for(i=list->data[0].expn;i>0;--i)t*=x;return(val*t); }

总结

以上是生活随笔为你收集整理的递归思想求解稀疏多项式的值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。