利用遞歸思想求解指數連續增長的多項式的值用的是的秦九昭算法，從最里面的一層乘到最外面的一層，這個算法的效率要比一個項一個項的算的算法高出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); }

總結

以上是生活随笔為你收集整理的递归思想求解稀疏多项式的值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。