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

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

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

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

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

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

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define SIZE 20

typedef 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);
}