2024王道408数据结构 P92 T3

2024王道408数据结构 P92 T3

思考过程

1. 这题比较复杂做的我好**累，首先我们还是先看懂题目，让我们用一个栈来实现递归函数的非递归计算，我们先剖析一下这个表达式。
   式子展开变成图上这样。那既然让我们用非递归来计算，那我们顺理成章就想到用循环来实现。
2. 现在我们令fv1 = P0(x) fv2 = P1(x)我们如果要知道Pn(x)，就要知道Pn-1(x)和Pn-2(x)，要知道Pn-1(x)就要知道Pn-2(x)和Pn-3(x)，以此类推。现在我们再来写这个表达式。到下一步的时候我们就能再给fv1和fv2重新赋值，
   ok这时候我们就能发现表达式每次都是一样的，我们只需要不断更新fv1和fv2的值就行了。
3. 之前入栈我们都进一个元素，那这次我们都进一个结构体，结构体包括两个数据，一个是n一个是PnX
   把栈看成分为左右两半部分，左边放n，右边就放PnX，但是实际上他们只是结构体的两个数据，我们只是为了方便思考看成了这样。首先我们需要一个结构体，结构体里需包含两个数据，一个n一个PnXstruct Stack{int n; double PnX; int top;}st;然后我们要把栈的左边进行赋值，把top指针先赋值-1，让top指针从下往上遍历这个栈for (int i = n; i >= 2; i--) {top++; st[top].n = i;}当i值为0和1时就不用赋值了，因为值是已知的。
   这样就完成了左边那一栏也就是结构体数据n的赋值。
4. 其次我们要赋值右边那一栏，也就是结构体中PnX的值，此时top指针在栈顶，当top>=0时我们就开始进行入栈操作，让top指针从上往下遍历。while (top >= 0){st[top].PnX = 2 * x * fv2 - 2 * (st[top].n - 1) * fv1;//这样就完成了对栈的右边那一栏的赋值，赋值完之后要更新fv1和fv2的值 fv1 = fv2; fv2 = st[top].PnX; top--;//最后让top指针从上往下移动}这样就把结构体的PnX给赋值完了。
5. 最后我们判断此时的n的值，如果n==0的话就返回fv1的值，如果不等于就返回fv2的值，本题就写完了。

完整代码附上

//
// Created by 黎圣  on 2023/8/2.
//
#include "iostream"
#define MAX 10
struct Stack
{
    int top;
    int n;
    double PnX;
}st[MAX];

//题目主代码
double ans(int n, double x)
{
    int top = -1;
    double fv1 = 1;
    double fv2 = 2 * x;
    //初始化左边部分
    for (int i = n; i >= 2; i--)
    {
        top++;
        st[top].n = i;
    }
    //初始化右边部分
    while (top >= 0)
    {
        st[top].PnX = 2 * x * fv2 - 2 * (st[top].n - 1) * fv1;
        fv1 = fv2;
        fv2 = st[top].PnX;
        top--;
    }
    if (n == 0) return fv1;
    else return fv2;
}
int main()
{
    double ans1 = ans(0, 1.9);
    printf("%lf", ans1);
    return 0;
}

这题听起来可能有点乱，要自己推一遍才能清楚为什么fv1和fv2要这么换，也建议各位做题的时候拿上草稿纸括弧也可能是我比较菜…
最后感谢b站up主@吸血小金鱼